Hard Cube Puzzle

Question

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 it's 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 sent 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 don't really know how to approach this, the only result I have so far: An 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: a lower bound of $N=18$ is given here: Guessing a hidden number on a cube.

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