Hard Cube Puzzle

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?

I dont really know how to approach this, only result I have so far: Upper bound of N=29 and a trivial strategy for N<10.

I'm also looking for a solution for the general case of an S-sided dice.

Update: Lower bound of N=18 given here: http://math.stackexchange.com/questions/18134/guessing-a-hidden-number-on-a-cube

-
There are 24 ways the friend can place the cube (6 faces to place on the floor and 4 orientations given the face on the floor) so this is an upper bound to the number that can be correctly guessed. –  Anthony Quas Jan 19 '11 at 20:36
@Anthony, there is additional information: you don't observe the orientation of just an abstract cube, but rather a cube with labelled sides. –  L Spice Jan 19 '11 at 20:54
It should be clarified that the integers are 1..N or some other KNOWN set of N integers. –  Per Alexandersson Jan 19 '11 at 21:02
@unknown: based on a moderator flag you left, you're having an account problem, but your account has no contact information, so I can't get in touch with you to fix it (and your profile doesn't contain enough information to dictate a course of action). Please email moderators@mathoverflow.net (or me directly if you prefer). –  Anton Geraschenko Apr 19 '11 at 16:18

This is a variation on a classic card trick (audience pick 5 cards, magician A removes a card of his choosing and hands the rest to magician B, who then names the missing card.)

There are two ways you can view the process - from the point of view of the cube-orienter, or from the point of view of the final guesser.

It turns out to be more useful to consider the cube-orienter's job.

Given a cube, he has to pick an orientation to leave it in. Let's view this as a function from the set of possible cubes to the set of 'visible orientations', i.e. we ignore what's on the bottom face. Then this function must be a bijection, and it must satisfy the constraint that the image of a cube under this function does give a valid 'visible orientation' of that cube.

This constraint can be represented as a bipartite graph, where there are $\frac{1}{24}n(n-1)(n-2)(n-3)(n-4)(n-5) = 30\binom{n}{6}$ vertices on the left representing the different cubes, $n(n-1)(n-2)(n-3)(n-4)$ vertices on the right representing the 'visible orientations', and each cube has $24$ edges linking it to its valid 'visible orientations'. Conversely, each 'visible orientation' has $n-5$ edges linking back to the cubes it could have arisen from. In this context, the bijective function we seek is a matching in this graph.

Hence the original problem is equivalent to the existence of a matching in this bipartite graph. A necessary and sufficient condition for such a matching to exist is given by Hall's Marriage Theorem. We need to check that for any set of $k$ cubes, the cardinality of the union of 'visible orientations' linked to these cubes is greater than or equal to $k$. But $k$ cubes give rise to $24k$ edges, which give rise to at least $24k/(n-5)$ 'visible orientations', which is greater than or equal to $k$ for $n \leq 29$.

So there is a strategy for $n = 29$, and conversely this is the best possible just by comparing the number of vertices on either side.

Update: An explicit strategy was requested, so here is an adaptation of the standard card trick strategy:

Let's assume we're working with numbers from $0$ to $28$ for convenience.

The cube-orienter adds up the numbers on all the faces of the cube modulo $6$. Call the result $i$, with $0 \leq i \leq 5$. Now if $i=0$, put the smallest face face-down, if $i=1$, put the second smallest face-down, and so on. Later on, the guesser will be able to add up all the visible faces modulo $6$, and a little thought shows that the hidden face will be congruent to the negative of this modulo $6$, provided the guesser renumbers the unseen numbers from $0$ to $23$. This means the guesser will know the answer is one of $4$ cards, and these remaining $4$ degrees of freedom can be communicated by the $4$ possible rotations the cube-orienter can leave the cube in (with a fixed face down). E.g. of the side-faces, the largest can be pointing left/forward/right/backward.

-
Wow, that was unexpected! Strategy part still stands. –  user12265 Jan 19 '11 at 21:18
Note that the 29 here is $|S_4| + 5$, where $S_4$ is the orientation-preserving symmetry group of a cube. In the card trick, the corresponding largest $n$ is 124, which is of course $|S_5| + 4$, where $S_5$ is the symmetry group of 5 labelled cards. So one can answer these questions as quickly as one can work out the order of the relevant symmetry group :) –  ndkrempel Jan 19 '11 at 21:20
The update has a tiny bit more group theory in: the Orbit-Stabilizer Theorem. –  ndkrempel Jan 19 '11 at 22:11
See also mathoverflow.net/questions/9754/… . –  Qiaochu Yuan Jan 19 '11 at 22:27