Backstory and Goal

Belfry Books has several projects that need to be translated into English from various foreign languages. Using only the clues that follow, match each project to its translator, publication year and determine the length of each (in pages).

Partitioned 3×4 = 12 element set, D = {Delia = 0, Martha = 1, Rodney = 2, Suzanne = 3 | Year2004 = 4, Year2005 = 5, Year2010 = 6, Year2011 = 7 | Pages150 = 8, Pages175 = 9, Pages200 = 10, Pages225 = 11}

Clues

1. The 175 page project is either Martha's assignment or the book published in 2010.

2. The book published in 2004 is 25 pages longer than the book published in 2010.

3. Of Dalia's assignment and Rodney's assignment, one is 225 pages long and the other was published in 2004.

4. Of the 225 page project and the 175 page assignment, one was published in 2010 and the other is assigned to Dalia.

5. The book published in 2004 is shorter than the book published in 2005.

Clues parsed into statements of a Free Boolean Algebra (Ring) generated from the Cartesian product D×D

Let for example generator (Delia ~ Year2005) = (0~5) = R[0,5] = X[0*12+5] etc. Let * denote AND, and + denote XOR

1. Exactly one of the statements R[9,1], R[9,6] is true so R[9,1] + R[9,6] = 1

2. Exactly one of the statements R[4,11]*R[6,10], R[4,10]*R[6,9], R[4,9]*R[6,8] is true.

3. Exactly one of the statements R[11,6]*R[9,0], R[11,0]*R[9,6] is true so R[11,6]*R[9,0] + R[11,0]*R[9,6] = 1

4. Exactly one of the statements R[0,11]*R[2,4], R[0,4]*R[2,11] is true so R[0,11]*R[2,4] + R[0,4]*R[2,11] = 1

5. Exactly one of the statements R[5,11]*R[4,10], R[5,11]*R[4,9], R[5,11]*R[4,8], R[5,10]*R[4,9], R[5,10]*R[4,8], R[5,9]*R[4,8] is true.

Clues 2 and 5 are more complicated Boolean ring expressions than a simple XOR of the arguments for example if exactly one of 3 alternatives X0, X1, X2 is true then X0*X1*X2 + X2 + X1 + X0 = 1, and if one of five alternatives then

X0*X1*X2*X3*X4 + X2*X3*X4 + X1*X3*X4 + X1*X2*X4 + X1*X2*X3 + X0*X3*X4 + X0*X2*X4 + X0*X2*X3 + X0*X1*X4 + X0*X1*X3 + X0*X1*X2 + X4 + X3 + X2 + X1 + X0 = 1. More compactness can be obtained using the NOT operator

Python Program for SAGE:

rel_classes = 4

types = 3

objects = rel_classes*types; print('objects = ' + str(objects))

print('types = ' + str(types))

print('rel_classes = ' + str(rel_classes))

print(str(objects^2) + ' Free Boolean Algebra generators: X0 = R[0,0], X1 = R[0,1], X2 = R[0,2],..., X' + str(objects^2-1) + ' = R[' + str(objects-1) + ',' + str(objects-1) + ']')

BPR = BooleanPolynomialRing(objects^2,'X',order='degneglex')

#X = BPR.gens()

KDELTA = lambda N, M: BPR(N == M)

NOT = lambda A: BPR(1) + A

XOR = lambda A, B: A + B

OR = lambda A, B: A + B + A*B

IF = lambda A, B: BPR(1) + A + A*B

IFF = lambda A, B: BPR(1) + A + B

AND = lambda A, B: A*B

NAND = lambda A, B: BPR(1) + A*B

NOR = lambda A, B: BPR(1) + A + B + A*B

ALT = lambda mylist: reduce(XOR,[reduce(AND,[[mylist[i]+NOT(KDELTA(i,j)) for i in range(len(mylist))] for j in range(len(mylist))][k]) for k in range(len(mylist))])

#REL = lambda i, j: X[i*objects + j]

R = matrix(BPR, objects, objects, BPR.gens())

relation = []

for i in range(0, objects): #reflexive

poly = R[i,i]

relation.append(poly + 1)

for i in range(0,objects): #symmentric

for j in range(i, objects):

#poly = IF(R[i,j],R[j,i])

poly = IFF(R[i,j],R[j,i])

if poly != 1:

relation.append(poly + 1)

for j in range(0, objects): #transitive given symmetric and reflexive

for i in range(0, objects - 1):

for k in range(i + 1, objects):

poly = IF(AND(R[i,j],R[j,k]),R[i,k])

if poly != 1:

relation.append(poly + 1)

for i in range(0, types): # distinct objects of the same type are not related

iobj = i*rel_classes

for j in range(0, rel_classes):

iobjj = iobj + j

for k in range(0, rel_classes):

if j!=k:

iobjk = iobj + k

poly = NOT(R[iobjj,iobjk])

if poly != 1:

relation.append(poly + 1)

#for i in range(types): # each object is related to exactly one object of each other type

# for j in range(rel_classes):

# for k in range(types):

# if k != i:

# poly = ALT([R[i*rel_classes + j, k*rel_classes + l] for l in range(rel_classes)])

# if poly != 1:

# relation.append(poly + 1)

#for i in range(types-1): # another way to do the same but placing either here exceeds size limitations for quotient ring and groebner basis algorithms

# for j in range(rel_classes):

# for k in range(i+1,types):

# poly = ALT([R[i*rel_classes + j, k*rel_classes + l] for l in range(rel_classes)])

# if poly != 1:

# relation.append(poly + 1)

# poly = ALT([R[i*rel_classes + l, k*rel_classes + j] for l in range(rel_classes)])

# if poly != 1:

# relation.append(poly + 1)

relation.append(ALT([R[9,1],R[9,6]]) + 1) # clue 1

relation.append(ALT([AND(R[4,11],R[6,10]), AND(R[4,10],R[6,9]), AND(R[4,9],R[6,8])]) + 1) # clue 2

relation.append(ALT([AND(R[11,6],R[9,0]), AND(R[11,0],R[9,6])]) + 1) # clue 3

relation.append(ALT([AND(R[0,11],R[2,4]), AND(R[0,4],R[2,11])]) + 1) # clue 4

relation.append(ALT([AND(R[5,11],R[4,10]), AND(R[5,11],R[4,9]), AND(R[5,11],R[4,8]), AND(R[5,10],R[4,9]), AND(R[5,10],R[4,8]), AND(R[5,9],R[4,8])]) + 1) # clue 5

REI = ideal(relation); print('REI.gens() = ' + str(len(REI.gens())))

GB = REI.groebner_basis()

QR = BPR.quotient_ring(REI)

QRG = QR.gens()

quo = len(QRG) // objects

rem = len(QRG) % objects

if len(QRG) == objects^2:

A = matrix(BPR, objects, objects, 0)

for i in range(quo):

A[i,0:objects] = matrix(QRG[i*objects: (i + 1)*objects])

print('A 1st pass')

relation2 = []

for i in range(types-1): # more hidden assumptions -- each object is related to exactly one oject in each other type

for j in range(i+1,types):

A2=A[i*rel_classes:(i+1)*rel_classes,j*rel_classes:(j+1)*rel_classes]

print('type '+ str(i) + ' to type ' + str(j));print(A2);print(' ')

for k in range(rel_classes):

poly = BPR(ALT([A2[k,l] for l in range(rel_classes)]))

if poly != 1:

relation2.append(poly + 1)

poly = BPR(ALT([A2[l,k] for l in range(rel_classes)]))

if poly != 1:

relation2.append(poly + 1)

stuff=[relation2[l].variables() for l in range(len(relation2))]

stuff2 = set(stuff[0])

for i in range(1,len(stuff)):

stuff2 = stuff2.union(set(stuff[i]))

print('number of variables left to be determined: ' + str(len(stuff2)))

relation = relation + relation2

REI = ideal(relation); print('REI.gens() = ' + str(len(REI.gens())))

GB = REI.groebner_basis()

QR = BPR.quotient_ring(REI)

QRG = QR.gens()

quo = len(QRG) // objects

rem = len(QRG) % objects

if len(QRG) == objects^2:

A3 = matrix(BPR, objects, objects, 0)

for i in range(quo):

A3[i,0:objects] = matrix(QRG[i*objects: (i + 1)*objects])

print('A 2nd pass')

for i in range(types-1):

for j in range(i+1,types):

A2=A3[i*rel_classes:(i+1)*rel_classes,j*rel_classes:(j+1)*rel_classes]

print('type '+ str(i) + ' to type ' + str(j));print(A2);print(' ')

Output:

load('Puzzle8.sage')

objects = 12 types = 3 rel_classes = 4 144 Free Boolean Algebra generators: X0 = R[0,0], X1 = R[0,1], X2 = R[0,2],..., X143 = R[11,11] REI.gens() = 779 A 1st pass type 0 to type 1 [ 0 1 0 0] [ 0 0 0 X19] [ 1 0 0 0] [ 0 0 X42 X43] type 0 to type 2 [ 0 0 0 1] [X20 0 0 0] [ 0 0 1 0] [X44 X42 0 0] type 1 to type 2 [ 0 0 1 0] [ 0 0 0 1] [ 0 1 0 0] [X92 0 0 0] number of variables left to be determined: 6 REI.gens() = 789 A 2nd pass type 0 to type 1 [0 1 0 0] [0 0 0 1] [1 0 0 0] [0 0 1 0] type 0 to type 2 [0 0 0 1] [1 0 0 0] [0 0 1 0] [0 1 0 0] type 1 to type 2 [0 0 1 0] [0 0 0 1] [0 1 0 0] [1 0 0 0]

web counter