Project Euler Problem 997

There are xyz dice arranged in an x times y times z box such that touching faces have the same value.

eulermathematicscompetitive-programming

Project Euler Problem 997

Solution

Answer: 5765993594880

Let the three opposite face-pairs of a standard die be denoted by

$$A={1,6},\qquad B={2,5},\qquad C={3,4}.$$

For every die, each coordinate axis ($x,y,z$) carries exactly one of these three pairs.

Step 1: Describe only the opposite-pair assignment

For a die at position $(i,j,k)$, define:

  • $X_{j,k}$: the pair used on the $x$-axis,
  • $Y_{i,k}$: the pair used on the $y$-axis,
  • $Z_{i,j}$: the pair used on the $z$-axis.

Why do these depend on only two coordinates?

Because neighboring dice touching along (say) the $x$-direction must have the same touching value, hence they must use the same opposite pair on the $x$-axis. Therefore the $x$-axis pair is constant along every $x$-line, so it depends only on $(j,k)$. Similarly for the others.

At every cube, the three assigned pairs must be all different, hence:

$${X_{j,k},Y_{i,k},Z_{i,j}}={A,B,C}.$$

Step 2: Structure theorem for the pair assignments

Fix $k$.

For every $i,j$, $X_{j,k}\neq Y_{i,k}$.

Thus the set of values used by the $X_{j,k}$'s is disjoint from the set used by the $Y_{i,k}$'s.

Since there are only three symbols $A,B,C$, exactly one of the following happens:

  1. all $X_{j,k}$ are constant,
  2. all $Y_{i,k}$ are constant.

Running the same argument cyclically across dimensions shows that globally exactly one of these three families may vary:

  • $X$-family varies,
  • or $Y$-family varies,
  • or $Z$-family varies.

Suppose the varying family is $X$.

Then:

  • all $Y_{i,k}$ are equal to one fixed symbol,
  • all $Z_{i,j}$ are equal to another fixed symbol,
  • each $x$-line independently chooses between those two symbols.

Hence there are

$$2^{x-1}$$

distinct possibilities in this case.

Similarly:

  • varying $Y$ gives $2^{y-1}$,
  • varying $Z$ gives $2^{z-1}$.

The completely constant configuration was counted three times, so the number of opposite-pair patterns is

$$6\left(2^{x-1}+2^{y-1}+2^{z-1}-2\right),$$

where the factor $6$ comes from permuting $A,B,C$.

Thus

$$N_{\text{pair}} = 6\left(2^{x-1}+2^{y-1}+2^{z-1}-2\right).$$

Check with $(2,3,4)$:

$$6(2+4+8-2)=72.$$

Step 3: Count orientations for a fixed pair pattern

Once the opposite-pair pattern is fixed:

  • each die still has a binary “sign” freedom along each axis,
  • consistency along touching faces forces these signs to propagate independently along coordinate directions.

The number of compatible sign assignments is

$$2^{x+y+z-1}.$$

Therefore

$$f(x,y,z) = 2^{x+y+z-1} \cdot 6\left(2^{x-1}+2^{y-1}+2^{z-1}-2\right).$$

Step 4: Verify the given examples

Example 1

$$f(1,1,1) = 2^2\cdot 6(1+1+1-2) = 4\cdot 6 = 24.$$

Correct.

Example 2

$$f(2,3,4) = 2^8\cdot 6(2+4+8-2) = 256\cdot 72 = 18432.$$

Correct.

Step 5: Compute $f(9,10,11)$

$$2^{9-1}=256,\qquad 2^{10-1}=512,\qquad 2^{11-1}=1024.$$

So

$$f(9,10,11) = 2^{29}\cdot 6(256+512+1024-2).$$

$$256+512+1024-2=1790.$$

$$6\cdot 1790=10740.$$

$$f(9,10,11)=10740\cdot 2^{29}.$$

Since

$$2^{29}=536{,}870{,}912,$$

we get

$$f(9,10,11) = 5765993594880.$$

Answer: 5765993594880