7
$\begingroup$

You are and your friend are given a list of N distinct integers and are told this:

Six distinct integers from the list are selected at random and placed one at each side of a cube. The cube is placed in the middle of a rectangular room in front of its only door, with one face touching the floor, its 6 sides parallel to the walls of the room. Your friend must enter the room and is allowed to alter the orientation of the cube, with the restriction that afterwards its in the same place with one face touching the floor and its 6 sides kept parallel to the walls of the room. Your friend will then be sendt away, after which you can enter the room and are allowed to observe the 5 visible sides of the cube.

What is the largest N that guarantees you to be able to determine the number on the bottom of the cube and what should you instruct your friend to do with the cube for that N?

N=29 is possible see! still in need of strategy https://mathoverflow.net/questions/52541/hard-cube-puzzle

  • 0
    @solomoan: I think this is the right forum. It's more of a puzzle than a research topic. (And most MO members are active here too.)2011-01-19

1 Answers 1

8

A straightforward upper bound is $N=29$. For a given $N$, you are trying to select one of the possible assignments of numbers to the six sides (up to rotation of the cube), of which there are $ {N \choose 6}\frac{6!}{24} = \frac{N!}{24(N-6)!}. $ The number of different states you can see when you enter the room, on the other hand, is $ {N \choose 5}5! = \frac{N!}{(N-5)!} = \frac{N!}{(N-5)(N-6)!}. $ The number of outputs (i.e., assignments of numbers to the cube) is greater than the number of inputs (i.e., different states you can see) whenever $N-5 > 24$, and so there can't be a surjective mapping from inputs to outputs unless $N \le 29$.


A lower bound of $N=18$ is given by the following strategy. Your friend will place the cube so that the largest face and its largest neighbor are visible. There are 16 such ways to orient the cube, all distinguishable by the visible faces: 4 where the largest face is on top; 4 where its largest neighbor is on top; and 8 where both the largest face and its largest neighbor are on the side. Order these 16 arbitrarily in advance, corresponding to the integers $0$ through $15$. Similarly, rank the 16 numbers that are not equal to the largest face or its largest neighbor, from $0$ to $15$. Your friend will place the cube in the position corresponding to the sum of the other four faces' ranks, modulo 16. By subtracting the ranks of the three faces you can see, you can deduce the rank, and hence the value, of the hidden face.

  • 1
    Your "upper bound" can actually be attained. The MO answer states this in terms of a perfect matching for a bipartite graph, using Hall's Thm. Since for N = 29 the graph from numbered cubes to possible orientations of 5 visible sides is regular of degree 24, König's Thm. could also be applied (to guarantee a perfect matching). http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory\)2011-01-20