From John Torrey comes a puzzle any sufficiently clever Bond villain would appreciate:
You have four number cubes, where each face of each cube can display one numeric digit from 0 to 9. You can make various numbers by picking three faces on three distinct cubes and lining them up. For example, you can make the number “123” by lining up three cubes to show 1-2-3, and you can make the number “7” by lining up three cubes to show 0-0-7.
Importantly, any face with a “6” can also be used to display a “9” by flipping the cube around, and vice versa. However, no other pairs of digits are interchangeable in this way.
You can choose which digits to place on the various faces of the four cubes. Your goal is to be able to make all the whole numbers from 1 to N, without skipping any numbers in between. With optimal design, what is the greatest possible value of N?
In order to achieve $001$ to $099$, two each of $0-9$ is necessary.
$24$ faces are available, which leaves six remaining.
A third $0$ is not necessary, so the remaining six must be $1-6$.
$\boxed{776}$ is the largest number as $777$ is the first impossible number to achieve.
From John Torrey also comes some Extra Credit:
How many distinct ways can you assign numbers to the four cubes that result in this greatest possible value of N?
Note that the cubes are not ordered in any way. And, very importantly, swapping digits between two faces on a single cube does not count as producing a distinct arrangement. (In other words, don’t worry about the various ways to assign six given digits to the faces of a cube.)
$0$, $7$, and $8$ have two occurences among the four dice.
$1-6$ have three occurences each.
Having two or more occurences of a number on a die does not provide solutions to the current problem.
This yields five cases:
Two of the dice each have all three of $0$, $7$, and $8$.
There are ${6 \choose 3}$ ways to choose from $1-6$ for $D_1$.
$D_2$ is defined by $D_1$.
$D_3$ and $D_4$ are always the same.
${6 \choose 3} = \boxed{20}$
One die has all three of $0$, $7$, and $8$. One die has two of them, one die has one of them, one die has none of them.
There are $3$ ways to distribute $0$, $7$, and $8$ among the four dice.
There are ${6 \choose 3}$ ways to choose from $1-6$ for $D_1$.
There are ${3 \choose 1}$ ways to choose from $1-6$ for $D_2$, as three must be the three omitted from $D_1$.
$D_3$ is defined by $D_1$ and $D_2$. $D_4$ is always the same.
$3 \times {6 \choose 3} \times {3 \choose 1} = 3 \times 20 \times 3 = \boxed{180}$
One die has all three of $0$, $7$, and $8$. The other three die have one of them.
There are ${6 \choose 3}$ ways to choose from $1-6$ for $D_1$.
There are ${3 \choose 2}$ ways to choose from $1-6$ for $D_2$, as three must be the three omitted from $D_1$.
There are ${2 \choose 1}$ ways to choose from $1-6$ for $D_3$, as four must be the three omitted from $D_1$ and the one omitted from $D_2$.
$D_4$ is defined by $D_1$, $D_2$, and $D_3$.
${6 \choose 3} \times {3 \choose 2} \times {2 \choose 1} = 20 \times 3 \times 2= \boxed{120}$
Three of the dice each have two of $0$, $7$, and $8$.
There are ${6 \choose 4}$ ways to choose from $1-6$ for $D_1$.
There are ${4 \choose 2}$ ways to choose from $1-6$ for $D_2$, as two must be the two omitted from $D_1$.
$D_3$ is defined by $D_1$ and $D_2$. $D_4$ is always the same.
${6 \choose 4} \times {4 \choose 2} = 15 \times 6 = \boxed{90}$
Two of the dice each have two of $0$, $7$, and $8$. Two of the dice each have one of $0$, $7$, and $8$.
There are $6$ ways to distribute $0$, $7$, and $8$ among the four dice.
There are ${6 \choose 4}$ ways to choose from $1-6$ for $D_1$.
There are ${4 \choose 2}$ ways to choose from $1-6$ for $D_2$, as two must be the two omitted from $D_1$.
There are ${2 \choose 1}$ ways to choose from $1-6$ for $D_3$, as four must be the two omitted from $D_1$ and two omitted from $D_2$.
$D_4$ is defined by $D_1$, $D_2$, and $D_3$.
$6 \times {6 \choose 4} \times {4 \choose 2} \times {2 \choose 1}= 6\times 15 \times 6 \times 2 = \boxed{1080}$