14th Chinese 1999 Problem B3 How many ways can you color red 16 of the unit cubes in a 4 x 4 x 4 cube, so that each 1 x 1 x 4 cuboid (and each 1 x 4 x 1 and each 4 x 1 x 1 cuboid) has just one red cube in it? Solution
: 576. The key is that there is a bijection between admissible arrangements of the red cubes and 4 x 4 Latin squares. On the top face of the cube write 1, 2, 3 or 4 in each square according to how far down the red cube is. Note that there must be at least one red cube in the column under each square. There are 16 squares, and only 16 red cubes, so there must be exactly one red cube in each column. Now there must be a 1 in each row of the square, otherwise there would not be a red cube in the corresponding 1 x 1 x 4 cuboid. Similarly, there must be a 2, 3, and 4. So each row must be a permutation of 1, 2, 3, 4. Similarly each column. So the square must be a Latin square. Conversely, a Latin square corresponds to an admissible arrangement. So we have to count Latin squares. It is easy to check that there are just four Latin squares with the pattern shown at the left: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 2 x x x 2 3 4 1 2 1 4 3 2 1 4 3 2 4 1 3 3 x x x 3 4 1 2 3 4 2 1 3 4 1 2 3 1 4 2 4 x x x 4 1 2 3 4 3 1 2 4 3 2 1 4 3 2 1 In each case we can permute the columns arbitrarily (to give any permutation of 1, 2, 3, 4 as the first row) and then permute rows 2, 3, 4 arbitrarily. Conversely any Latin square can be put in the form shown at the left by such permutations. Hence there are just 4 x 24 x 6 = 576 possibilities. 14th Chinese 1999 (C) John Scholes jscholes@kalva.demon.co.uk 19 June 2002