June 2014 - Solution
| Using 31 different numbers, we can get 31 cubes by using the projective plane of order 5 (see http://mathworld.wolfram.com/ProjectivePlane.html) that has 31 points and 31 lines. Each line contains exactly six points, and any two distinct lines have exactly one point in common: 0 1 2 3 4 5 0 6 7 8 9 10 0 11 12 13 14 15 0 16 17 18 19 20 0 21 22 23 24 25 1 6 11 16 21 26 1 7 12 18 23 28 1 9 15 17 25 29 1 10 14 20 24 27 2 6 13 18 24 29 2 7 11 17 22 27 2 8 14 16 25 28 2 10 15 19 23 26 3 6 12 19 25 27 3 8 11 20 23 29 3 9 14 18 22 26 3 10 13 17 21 28 4 7 13 20 25 26 4 8 15 18 21 27 4 9 11 19 24 28 4 10 12 16 22 29 5 6 15 20 22 28 5 7 14 19 21 29 5 8 12 17 24 26 5 9 13 16 23 27 0 26 27 28 29 30 1 8 13 19 22 30 2 9 12 20 21 30 3 7 15 16 24 30 4 6 14 17 23 30 5 10 11 18 25 30 If we throw away the last six lines that pass through the last point, we get 25 lines (cubes) using 30 points (numbers). To prove that this is the best solution attainable note that if a solution existed that used less than 30 different numbers, then by the pigeonhole principle at least one of the numbers must be used six times (150/29) and these six cubes would have 31 different numbers. |