Guessing a hidden number on a cube

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 http://mathoverflow.net/questions/52541/hard-cube-puzzle

-
There's an easy strategy for up to N = 25, but I'm confident one can do better. This reminds me of a puzzle involving five cards randomly selected from a deck. One friend enters the room and arranges the five cards, removes one, and leaves the other four stacked on a desk. The other friend enters, examines the four cards left and deduces which one was removed. – hardmath Jan 19 '11 at 13:55
Are the N integers just any N not necessarily distinct integers? – Harry Stern Jan 19 '11 at 14:57
@Harry The N integers are N distinct integers – TROLLKILLER Jan 19 '11 at 15:01
@solomoan: The cube does have only 24 possible configurations, but you can rule out 5 numbers just because you can see them, so you get some extra information that way. But I'd also like to see an explicit N=25 solution posted as a "lower bound" answer to match my upper bound. – mjqxxxx Jan 19 '11 at 15:46
@Peter: Here's a solution for N=15. Consider the corner that joins the largest face, its largest neighbor, and their largest common neighbor. Your friend will place this corner on the top of the cube. There are 12 ways for him to do this (four possible positions, and three rotations per position). Associate these 12 choices with the 12 numbers that are not adjacent to this corner. – mjqxxxx Jan 19 '11 at 18:53

1 Answer

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.

-
What if the largest face and its neighbour are opposite each other? – Peter Taylor Jan 19 '11 at 19:45
@Peter: The solution uses the largest face and the largest of its four neighboring faces on the cube (not the largest face and the second-largest face, which might well be opposite each other). – mjqxxxx Jan 19 '11 at 20:01
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). en.wikipedia.org/wiki/…; – hardmath Jan 20 '11 at 16:55