bit-player

I messed up a kenken the other day, carelessly forgetting that 2, 3, 4 and 6 are not the only divisors of 12. Later, mulling over my mistake, I realized that it’s the presence of the multiplicative identity that gives a kenken puzzle much of its combinatorial variety. If we played kenken without 1′s, the three-cell “cage” below would have only the single solution shown.

But because 1 is included in the set of candidate numbers, the cage could also be filled in with various permutations of 1 × 3 × 4 and 1 × 2 × 6, thereby increasing the entropy of the puzzle.

[For those of you who don't fritter away enough of your time on the puzzles page at the back of the newspaper, here's a kenken résumé. You are given a k × k grid to be filled in with the integers from 1 through k, observing certain constraints. Each integer must appear exactly once in each column and each row (thus making the grid a Latin square). And the numbers within each thickly outlined cage must combine to produce the target number in the upper left corner of the cage, using the operation shown there (+, –, × or ÷). For the noncommutative and nonassociative operations, the requirement is merely that some ordering of the operands yields the target value.]

If having the multiplicative identity among the candidate numbers makes the puzzle more interesting, an obvious idea is to include the additive identity as well. This would be easy to arrange: Just shift from the set {1, 2, …, k} to the set {0, 1, …, k–1}. Then a target value of 3+ would no longer have the unique solution 1 + 2; it could also be 0 + 3. Moreover, a target value of 0× would be a kind of wild card, with very high entropy indeed!

Other sets of candidate numbers might produce even harder (and weirder) puzzles. How about a 5 × 5 kenken with the set {–2, –1, 0, 1, 2}? Or, venturing a little farther afield, we might try a 4 × 4 puzzle with the candidates {1, –1, i, –i}.

(Roll your mouse over the grid above to see a valid solution—but I’m not at all sure the solution is unique or that it can be found by a purely deductive process. At best this is a jokenken.)

Looking in the opposite direction, certain candidate sets should lower the entropy of the system and thus can be expected to make the puzzle easier. In particular, a grid to be filled in only with prime numbers would have unambiguous solutions (except for order) in all multiplicative cages. (If we stick with the convention that target values are always integers, there could be no division cages in such a puzzle.)

Following up on this line of thought, I began to wonder about candidate sets for which all operations would yield unambiguous results. If we choose any two distinct numbers from such a set, and combine them with any of the kenken operations +, –, ×, ÷, we would get a result different from what we would see with any other pair of numbers or any other operation. Do such sets exist? Yes, an example is {2, 8, 10, 11}, for which the four arithmetic operations yield these results:

Following kenken convention, we take only numbers from the lower triangle of each table, and in the case of division we ignore any noninteger quotient. Thus the full set of results are the numbers circled in red. It’s easy to see there are no duplicated values. Sorted by magnitude, the set is: {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 16, 18, 19, 20, 21, 22, 80, 88, 110}.

A cute property of such sets is that they allow the construction (and solution!) of kenken puzzles like this one:

Note that the target values in the cages do not indicate which operation is to be performed. There’s no need to specify an operator, because each of the target values can be generated in only one way from the set of numbers given. If a set allows such an operatorless puzzle grid, I’m going to call it a kenken-friendly set, or a kkf set.

[According to Wikipedia, operatorless kenkens are nothing new:

More complex KenKen problems are formed ... omitting the symbols +, −, × and ÷, thus leaving them as yet another unknown to be determined.

I've never seen such a kenken in the wild. Are they based on kenken-friendly sets of the kind defined here? I rather doubt it if the puzzles are meant to be harder than normal. (The example above is quite easy.)]

A few things I know about kenken-friendly sets:

1. No kkf set can include either 0 or 1 among its members.
2. No three elements of a kkf set can form an arithmetic progression. It follows that if {m, …, n} is a kkf set of k elements, then n–m is at least k(k–1)/2. (Let’s call this the minimum span of the set.)
3. Every kkf set defines a Golomb ruler, a set of integers in which all differences are unique. But of course only some Golomb rulers also satisfy the constraints that sums, products and quotients be unique.
4. Among sets made up entirely of small numbers, kkf sets are rare, but when you select sets of k integers from the range [1, n], and n is much larger than k, nearly every set has the kkf property.

A few things I don’t know about kenken-friendly sets:

1. For each value of k, what are the smallest kkf sets?
2. Before we can address question 1, we have to answer this: What is the best measure of size in a kkf set? In sets of the form {m, …, n}, should we work to minimize m, minimize n, or perhaps minimize the span from m to n? Or maybe the right measure is the sum or product of all the elements of the set? (This question doesn’t come up for Golomb rulers, where it’s customary to set m=0, then look for the set with the smallest n, which is designated the optimal ruler for a given k.)
3. One way to search for small kkf sets is to take a known Golomb ruler {0, … n}, then slide it along the number line, adding a constant c to each element. This preserves Golomb-ruler-ness, and at each c you can test for kkf-ness. The question is: Does every Golomb ruler become a kkf set for some finite value of c? The answer is yes for the 35 known optimal Golomb rulers, and I have not found a counterexample among various larger rulers. (I’ve tried a sampling of those listed by James B. Shearer.) But I have no clue to a proof, one way or the other.
4. The special treatment of division in these sets may make sense for a puzzle printed in the newspaper, but mathematically it’s a bit of a wart. There’s no good rationale for accepting quotients when they happen to be integers and ignoring them otherwise. So what’s the proper formulation of the problem? Should we open the door to the whole field of rational numbers? Or, on the contrary, should we exclude division altogether and just work with +, – and ×? Another option is to replace division with the remainder operation. (This last approach looks intriguing. Sets that have all-unique sums, products, differences and remainders seem to be rare, but they do exist. One example is {3, 6, 16, 47}, which yields the result set {0, 1, 2, 3, 4, 5, 9, 10, 13, 15, 18, 19, 22, 31, 41, 44, 48, 50, 53, 63, 96, 141, 282, 752}).
5. Have all these questions been answered already, perhaps in some other context?

Finally, some data. Here are a few small (by some measure) kkf sets, along with the result sets they generate from the operations {+, –, ×, ÷}:

k=4:

{2, 8, 9, 11} ⇒ {1, 2, 3, 4, 6, 7, 9, 10, 11, 13, 16, 17, 18, 19, 20, 22, 72, 88, 99}
{3, 6, 10, 11} ⇒ {1, 2, 3, 4, 5, 7, 8, 9, 13, 14, 16, 17, 18, 21, 30, 33, 60, 66, 110}
{4, 6, 9, 10} ⇒ {1, 2, 3, 4, 5, 6, 10, 13, 14, 15, 16, 19, 24, 36, 40, 54, 60, 90}
{5, 6, 9, 11} ⇒ {1, 2, 3, 4, 5, 6, 11, 14, 15, 16, 17, 20, 30, 45, 54, 55, 66, 99}

k=5:
{2, 5, 13, 18, 19} ⇒ {1, 3, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 23, 24, 26, 31, 32, 36, 37, 38, 65, 90, 95, 234, 247, 342}
{9, 11, 16, 19, 20} ⇒ {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 20, 25, 27, 28, 29, 30, 31, 35, 36, 39, 99, 144, 171, 176, 180, 209, 220, 304, 320, 380}}

k=6:
{2, 3, 17, 19, 26, 29} ⇒ {1, 2, 3, 5, 6, 7, 9, 10, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 31, 32, 34, 36, 38, 43, 45, 46, 48, 51, 52, 55, 57, 58, 78, 87, 323, 442, 493, 494, 551, 754}
{7, 11, 13, 16, 23, 24} ⇒ {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 17, 18, 20, 23, 24, 27, 29, 30, 31, 34, 35, 36, 37, 39, 40, 47, 77, 91, 112, 143, 161, 168, 176, 208, 253, 264, 299, 312, 368, 384, 552}
{13, 17, 19, 22, 29, 30} ⇒ {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 17, 30, 32, 35, 36, 39, 41, 42, 43, 46, 47, 48, 49, 51, 52, 59, 221, 247, 286, 323, 374, 377, 390, 418, 493, 510, 551, 570, 638, 660, 870}}

k = 7:
{6, 13, 17, 18, 27, 33, 35} ⇒ {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 27, 29, 30, 31, 33, 35, 39, 40, 41, 44, 45, 46, 48, 50, 51, 52, 53, 60, 62, 68, 78, 102, 108, 162, 198, 210, 221, 234, 306, 351, 429, 455, 459, 486, 561, 594, 595, 630, 891, 945, 1155}

---

Update 2016-12-15: A 2010 comment from David Nacin settled my questions about the 4×4 kenken filled with complex numbers. Nacin elaborates on those solutions and goes on to ask and answer a bunch of further interesting questions about similar kenkens in a talk delivered in the Experimental Math Seminar at Rutgers. Video: Part 1 and Part 2.