Solution
The question can be formulated as: What is the smallest number of rooks on an n × n × n board that attack all squares? It is also related to the topic of "covering codes." The answer is 32 (and a proof of optimality for 32 is in my source, the Honsberger book cited). This was solved by Nick Meyer, Stephen Morris, and James Guilford by hand; and by Rob Pratt by ILP. Four readers obtained 48.
Suppose the unlocking combination is (a, b, c). The trick is dividing the 8 possibilities into {1, 2, 3, 4} and {5, 6, 7, 8}. Focus first on the case that two of (a, b, c) are in the first group (since it must be that two are in the first group, or two in the second).
Then consider the simple Latin square A
|
1
|
2
|
3
|
4
|
|
4
|
1
|
2
|
3
|
|
3
|
4
|
1
|
2
|
|
2
|
3
|
4
|
1
|
For the (i, j)th entry in A, form the triple (i, j, A(i, j)), getting 16 triples. Then take these 16 and increase all numbers by 4. The resulting set of 32 triples covers all the combinations.
The set is
{{1, 1, 1}, {1, 2, 2}, {1, 3, 3}, {1, 4, 4},
{2, 1, 4}, {2, 2, 1}, {2, 3, 2}, {2, 4, 3},
{3, 1, 3}, {3, 2, 4}, {3, 3, 1}, {3, 4, 2},
{4, 1, 2}, {4, 2, 3}, {4, 3, 4}, {4, 4, 1},
{5, 5, 5}, {5, 6, 6}, {5, 7, 7}, {5, 8, 8},
{6, 5, 8}, {6, 6, 5}, {6, 7, 6}, {6, 8, 7},
{7, 5, 7}, {7, 6, 8}, {7, 7, 5}, {7, 8, 6},
{8, 5, 6}, {8, 6, 7}, {8, 7, 8}, {8, 8, 5}}
Stephen Morris found a different solution by looking at all triples out of {1, 2, 3, 4} whose sum is divisible by 4, and adding in the triples from {5, 6, 7, 8} with sum divisible by 4.
More generally, with n choices of numbers in place of 8, let g(n) be the domination number of the graph in question. Then
g(n) ≥ Ceiling[n³/(3n − 2)]
because there are n³ points to cover and each point can cover at most 3n, but with 2 duplicates. James Guilford and I worked a bit on some values n < 8, but then Joe Buhler found a 1969 paper, which proves that the correct formula is
g(n) = Ceiling[n²/2].
Lovely.
The relevant paper is "A combinatorial problem in matching" by Kalbfleisch and Stanton (1969, J London M Soc), and more info on this sequence is available at the On-Line Encyclopedia of Integer Sequences. A proof in French can be found in Chapter 7 of Mathématiques venues d'ailleurs : divertissements mathématiques en U.R.S.S..
So the full sequence looks like
1, 2, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, 85, 98, 113, 128, 145,...
[Back to Problem 1167]
© Copyright 2013 Stan Wagon. Reproduced with permission.