MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 987 characters in body

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.

1

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 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.