Summary: Some companion calculations handling simpler cases than the standard Krypto problems. These extend downward the calculuations made elsewhere for five-card problems: cards formulas values f <= Catalan(n)*4^(c-1) v <= f * n! 5 500 27142 3584 60000 4 97 1170 320 2328 3 18 68 32 108 2 4 6 4 8 1 1 1 1 1 dave rusin@math.niu.edu http://www.math.niu.edu/~rusin/uses-math/games/krypto n = 2 What numbers can one make, Krypto-style, with two numbers x1, x2 ? There are four operations, two commutative and two not. So we have four "fourmulas" x1+x2, x1-x2, x1*x2, x1/x2, and when we substitute both permutations of {x1, x2} we get six "values", t1+t2, t1-t2, t2-t1, t1*t2, t1/t2, t2/t1. The "formulas" are the equivalence classes of the "values" under the action of the symmetric group, here Sym(2). We can partition the formulas into two groups: those two with symmetry group Sym(2) (x1+x2 and x1*x2) and those with trivial symmetry group (x1-x2 and x1/x2); the former give one value each, the latter give two values each. Taking t1=2, t2=3 makes all 6 take different values: {-1,1,5,6,3/2,2/3}. n = 3 How about with three numbers? This time we must worry not only about the commutative law but the associate law too. Given any choice of two operations "@" and "%" we have two formulas (x1 @ x2) % x3 x1 @ (x2 % x3) With four choices for each operation that appears to be 32 "formulas" but in fact in view of the the commutative law etc. these are algebraically equivalent to these 18 only; again, these are representatives of the equivalence classes of "values" under Sym(3): formulas := [ x1*x2*x3, x1+x2+x3, #symmetry group is all of Sym(3): 1 value each (x1+x2)-x3, x3-(x1+x2), (x1*x2)+x3, x1*x2-x3, x3-x1*x2, (x1+x2)*x3, (x1+x2)/x3, x3/(x1+x2), (x1*x2)/x3, x3/(x1*x2), #symmetry group is Sym(2): 3 values each (x1-x2)*x3, (x1-x2)/x3, x1+(x2/x3), x1-(x2/x3), (x2/x3)-x1, x1/(x2-x3) #symmetry group is trivial: 6 values each ]: Writing out the full equivalence classes we get these 68 possible "values": values:= { t1*t2*t3, t1+t2+t3, t1+t3-t2, t2+t3-t1, t1+t2-t3, t1-t2-t3, t2-t1-t3, t3-t1-t2, t1+t2*t3, t1*t3+t2, t1*t2+t3, t2*t3-t1, t1*t3-t2, t1*t2-t3, t1-t2*t3, t2-t1*t3, t3-t1*t2, (t1+t3)*t2, (t1+t2)*t3, (t2+t3)*t1, (t1+t3)/t2, (t1+t2)/t3, (t2+t3)/t1, t1/(t2+t3), t2/(t1+t3), t3/(t1+t2), t1*t2/t3, t2*t3/t1, t1*t3/t2, t3/t1/t2, t2/t1/t3, t1/t2/t3, (-t3+t2)*t1, (-t2+t3)*t1, (-t1+t3)*t2, (t1-t3)*t2, (t2-t1)*t3, (t1-t2)*t3, (t1-t2)/t3, (t2-t1)/t3, (t1-t3)/t2, (-t3+t2)/t1, (-t2+t3)/t1, (-t1+t3)/t2, (t1*t3+t2)/t1, (t1*t2+t3)/t1, (t1+t2*t3)/t2, (t1*t2+t3)/t2, (t1*t3+t2)/t3, (t1+t2*t3)/t3, (t1*t3-t2)/t1, (t1*t2-t3)/t1, (t1*t2-t3)/t2, (t2*t3-t1)/t2, (t2*t3-t1)/t3, (t1*t3-t2)/t3, -(t1*t2-t3)/t1, -(t1*t3-t2)/t1, -(t2*t3-t1)/t2, -(t1*t2-t3)/t2, -(t2*t3-t1)/t3, -(t1*t3-t2)/t3, t1/(t3-t2), t1/(t2-t3), t2/(t3-t1), t2/(t1-t3), t3/(t2-t1), t3/(t1-t2) } Check: 2+10+6 = 18, and 2*1 + 10*3 + 6*6 = 68. Setting the variables to be T=[5,7,9] will show 68 different values. Note that the denominators vanish iff some t_i is zero or two are either equal or negatives of each other; thus there are 4+6+6=16 "bad denoms". n = 4 Now let's see what happens when we have four numbers to combine. This is more complicated than above but easier than the five-input case considered in separate files; the latter has more details about what is being claimed here. The RPN string is a list of 4 numbers with 3 operations interspersed, such that when reading left to right there are always more numbers than operations. There are only 5 possible such sequences: NNNNOOO, i.e., (N1 op4 (N2 op3 (N3 op2 N4 ))) NNNONOO NNNOONO NNONNOO NNONONO, i.e., (((N1 op1 N2) op2 N3) op3 N4) . That is, we have not 1 or 2 but 5 ways to parenthesize here (14 for 5 cards). Many of these are the same when the operations are + or * because of commutativity, but distinct when using - or / . Thus given a 4-card hand and an objective card, there are at most 5 x (4^3 sequences of 3 operations) x (4! permutations of the hand)=7680 possible ways to combine them (many of which will certainly yield the same value), making it quite feasible to run an exhaustive check to solve any particular hand. A Maple program to do this is included. In its present form it can decide in a minute or less whether a four-card hand is playable. There are, after the fact, only 1170 possible values using 97 formulas. Here is how we generate them in Maple: #Create nominal formulas: S:=[`+`,`-`,`*`,`/`]: for i to 4 do for j to 4 do for k to 4 do lprint(`(`,x1,S[i],`(`,x2,S[j],`(`,x3,S[k],x4,`)))`,`,`): lprint(`(`,x1,S[i],`((`,x2,S[j],x3,`)`,S[k],x4,`))`,`,`): lprint(`((`,x1,S[i],`(`,x2,S[j],x3,`))`,S[k],x4,`)`,`,`): lprint(`((`,x1,S[i],x2,`)`,S[j],`(`,x3,S[k],x4,`))`,`,`): lprint(`(((`,x1,S[i],x2,`)`,S[j],x3,`)`,S[k],x4,`)`,`,`): od:od:od: #Run, then paste output into a file like this: A:=[ ( x1 + ( x2 + ( x3 + x4 ))) , ( x1 + (( x2 + x3 ) + x4 )) , [316 lines deleted] (( x1 / x2 ) / ( x3 / x4 )) , ((( x1 / x2 ) / x3 ) / x4 ) ]: #Capture and paste back into Maple to get A. But under the laws of algebra, #(e.g. associative and commutative laws) many of these are clearly equal: B:={op(factor(A))}: # 176 formulas instead of 320 in A. Now while these are distinct rational # functions, these are not all in different orbits under Sym(4). # Let's look for coincidences, after partitioning B to help. #(This can be done more automatically, e.g. by actually computing and #factoring the 176 orbits and then asking Maple to check for set equality, #but I will take these steps to segregate the B's a bit.) B0:=[]:for i to 176 do if denom(B[i])=1 then B0:=[op(B0),B[i]]:fi:od:nops(B0); #69 of these B1:=[]:for i to 176 do xx:=denom(B[i]): if xx=x1 or xx=x2 or xx=x3 or xx=x4 then B1:=[op(B1),B[i]]:fi:od:nops(B1); #59 B2:=[]:for i to 176 do xx:=denom(B[i]):if xx=x2*x3 or xx=x2*x4 or xx=x3*x4 then B2:=[op(B2),B[i]]:fi:od:nops(B2); #15 B3:=[x1/x2/x3/x4]: # just 1 of these! C:=[]:for i to 176 do if not member(B[i],B0) and not member(B[i],B1) and not member(B[i],B2) and not member(B[i],B3) then C:=[op(C),B[i]]:fi:od:nops(C); #32 B4:=[]:for i to 32 do xx:=denom(C[i]):if xx=x2+x3 or xx=x2+x4 or xx=x3+x4 then B4:=[op(B4),C[i]]:fi:od:nops(B4); #8 B5:=[]:for i to 32 do xx:=denom(C[i]):if xx=x2-x3 or xx=x2-x4 or xx=x3-x4 or -xx=x2-x3 or -xx=x2-x4 or -xx=x3-x4 then B5:=[op(B5),C[i]]:fi:od:nops(B5); #8 E:=[]:for i to 32 do if not member(C[i],B4) and not member(C[i],B5) then E:=[op(E),C[i]]:fi:od:nops(E); #16 B6:=[]:B7:=[]:for i to 16 do if numer(E[i])=x1 or numer(E[i])=-x1 then B6:=[op(B6),E[i]] else B7:=[op(B7),E[i]]:fi:od:nops(B6), nops(B7); #12,4 #Now scan for duplicates; replace B* by BB*. The union of #these is the final set of formulas BB7:=[x3*x1/(x2+x3*x4), x3*x1/(x2-x3*x4), x3*x1/(-x2+x3*x4)]: BB6:=[x1/(x2-x3-x4), x1/(x2+x3+x4), x1/(x2-x3+x4), x1/(x2-x3*x4), x1/(x2*x3+x4), x1/(x2*x3-x4), x1/(x2+x3)/x4, x1/(x2-x3)/x4]: BB5:=[x1/(x2-x3)*x4, (x1+x4)/(-x3+x2), (x1-x4)/(-x3+x2), (x1+x4*x2-x3*x4)/(x2-x3), (x1-x4*x2+x3*x4)/(x2-x3)]: BB4:=[(x1+x2)/(x3+x4), (x1-x2)/(x3+x4), x1*x2/(x3+x4), (x3*x1+x1*x4+x2)/(x3+x4), (x3*x1+x1*x4-x2)/(x3+x4), (-x3*x1-x1*x4+x2)/(x3+x4)]: BB3:=[x1/x2/x3/x4]: BB2:=[x1*x2/x3/x4, (x1+x2)/x3/x4, (x1-x2)/x3/x4, (x1*x4+x2*x3)/x4/x3, (x1*x4-x2*x3)/x4/x3, (x2*x3-x1)/x4/x3, (x1+x2*x3)/x4/x3, (x1-x2*x3)/x4/x3, (x1+x2*x3*x4)/x3/x4, (x1-x2*x3*x4)/x4/x3, (-x1+x2*x3*x4)/x4/x3]: BB1:=[(x1+x2+x3)/x4, (x1+x2-x3)/x4, (x1-x2-x3)/x4, x1*x2*x3/x4, x1*(x2-x3)/x4, x1*(x2+x3)/x4, (x1*x2-x3)/x4, (x1*x2+x3)/x4, (x1-x2*x3)/x4, (x1-x2-x3*x4)/x4, (x1-x2+x3*x4)/x4, (x1+x2-x3*x4)/x4, (x1+x2+x3*x4)/x4, (-x1-x2+x3*x4)/x4, (x1*x2*x4-x3)/x4, (x1*x2*x4+x3)/x4, (-x1*x2*x4+x3)/x4, (x1-x2*x3*x4)/x4, (x1+x2*x3*x4)/x4, (x2*x3*x4-x1)/x4, (x3*x1-x4*x2)/x4, (x3*x1+x4*x2)/x4, (-x3*x1+x4*x2)/x4, x1*(x4*x2+x3)/x4, x1*(x4*x2-x3)/x4, x1*(-x4*x2+x3)/x4, (x1*x4+x2*x4+x3)/x4, (x1*x4+x2*x4-x3)/x4, (-x1*x4-x2*x4+x3)/x4, (x1*x4-x2*x4+x3)/x4, (x1*x4-x2*x4-x3)/x4]: BB0:=[x1*x2*x3*x4, x1+x2+x3+x4, x1+x2+x3-x4, x1+x2-x3-x4, x1-x2-x3-x4, x1*x2*(-x3+x4), x1*x2*(x3+x4), x1*x2+x3+x4, x1*x2+x3-x4, x1*x2-x3-x4, -x1*x2+x3-x4, -x1*x2+x3+x4, x1+x2*x3*x4, x1-x2*x3*x4, -x1+x2*x3*x4, (x1+x2+x3)*x4, (x1+x2-x3)*x4, (x1-x2-x3)*x4, (x1*x2+x3)*x4, (x1*x2-x3)*x4, (-x1*x2+x3)*x4, (x1+x2)*(x3+x4), (x1-x2)*(x3+x4), (x1-x2)*(x3-x4), x1*x2+x3*x4, x1*x2-x3*x4, x1*x2+x3*x1+x4, x1*x2-x3*x1+x4, -x1*x2-x3*x1+x4, x1*x2+x3*x1+x4, x1*x2+x3*x1-x4, x1*x2-x3*x1-x4]; BB:=[seq(op(BB.k),k=0..7)]: #I get 97 formulas. #Exercise for the reader: re-sort these 97 formulas by size of #symmetry group. There are just two formulas with symmetry group Sym(4). #Looks like 1170 possible values. with(combinat): T:=permute([t1,t2,t3,t4]): ALL:=[op({seq(op(factor(subs({seq(x.k=T[i][k],k=1..4)},BB))),i=1..24)})]: nops(%); #makes 1170... #Well, that's 1170 formulas. They all LOOK different, but you never #know what simplifies to what! However, taking T:=[17,25,29,31]; #we find that indeed we obtain 1170 distinct values. (This is the #simplest such set T .) #That particular example provides only 139 integer values, 85 of them #positive. We can obtain many more (positive) integer values for some T: #I have tested all sets T of positive integers with max(T) <= 53 and could # not exceed about 243 positives among 398 integers: {11,22,44,52}. #Good combinations seem to have t3/t1 and t2/t1 small integers. We can #actually get 1170 values when these ratios are {2,7} or {3,7}, at least #for most t1 . For example, n,2n,7n is OK for (most? all?) n >= 9. #E.g. n=10, t4=1980 gives 1170 and 478 integers, 291 of them positive; #nothing better when t4<2000 and n<16. #n,3n,7n is also OK if n >= 8; the same range of t4 and n gives nothing better #n,4n,7n is also OK; t4/t1 integer as well is only OK if it's 23, 33, 34, 40,.. #(respectively for n=27,35,..., or n=29,37,38,..., or ... # Well, {10,20,70,1980} are "small}; surely for larger T we can get, say, # half of the 1170 to be integer?... #(The possible denominators are permutations of 1, # x4, x3+x4, x2-x3, x2+x3+x4, x2-x3+x4, x2-x3-x4, # x2-x3*x4, x2*x3+x4, x2*x3-x4, x2+x3*x4, x3*x4, (x2+x3)*x4, (x2-x3)*x4, # x2*x3*x4, #Now, how can we use this list of 1170 values? #Run these preparatory commands into Maple: with(combinat): sol:=proc(a,b,c,d,e) local T,t,bb,nn,dd: T:=permute([a,b,c,d]): for t in T do for bb in BB do nn:=subs({x1=t[1],x2=t[2],x3=t[3],x4=t[4]},numer(bb)): dd:=subs({x1=t[1],x2=t[2],x3=t[3],x4=t[4]},denom(bb)): if dd <> 0 then if nn/dd=e then lprint(t,bb,nn/dd):fi:fi: od:od: end: #Sample attempt to solve a hand: 17, 25, 29, 31 -> 2 #Use like this: sol(17,25,29,31,2); #Note that apparently-multiple solutions are redundant: [17, 25, 31, 29] (x1-x4)/(x2-x3) 2 [29, 31, 25, 17] (x1-x4)/(x2-x3) 2 #This reflects the stabilizer group of the particular formula:<(14)(23)>. #A different formula with smaller group can have a truly unique solution #e.g. target=9 has only this solution: [17, 31, 29, 25] x1*x2-x3*x1-x4 9 #i.e. (31 - 29) * 17 - 25 = 9 #There can be unique solutions for _some_ objective values but not #_all_ objectives, using only cards in a regular Krypto hand, e.g. #[23, 19, 13,7]-> 15: (x1-x2)*x4-x3 (23-19)*7-13=15. By the way this also 'solves' the four fours game: We can evaluate all but six of the 97 elements of BB with x1=x2=x3=x4 = 4 and get these 56 combinations ONLY: [-60, -48, -28, -16, -15, -12, -8, -7, -4, -15/4, -7/2, -3, -2, -4/3, -1, -3/4, -1/3, 0, 1/16, 1/8, 1/5, 1/3, 1/2, 3/4, 4/5, 1, 5/4, 4/3, 2, 3, 7/2, 15/4, 4, 17/4, 9/2, 5, 6, 7, 8, 9, 12, 15, 16, 17, 20, 24, 28, 32, 36, 48, 60, 64, 68, 80, 128, 256] In particular: no 10,11,13,14,18,19,etc. We can also use this for the game '24'; e.g. I was asked about [10,10,4,4]; > sol(10,10,4,4,24); [10, 10, 4, 4] (x1*x2-x3)/x4 24 n = 5 Finally we should see what happens when we have five numbers to combine. But this is much more laborious than the cases above and it treated in separate files....