# Mock AIME 2 2006-2007 Problems/Problem 15

## Problem

A $4\times4\times4$ cube is composed of $64$ unit cubes. The faces of $16$ unit cubes are colored red. An arrangement of the cubes is "intriguing" if there is exactly $1$ red unit cube in every $1\times1\times4$ rectangular box composed of $4$ unit cubes. Determine the number of "intriguing" colorings.

## Solution

In order to solve this we must first look at the 2D problem using a $4 \times 4$ grid.

In order to have exactly one red in each column and exactly one red in each row of the 4x4 grid, one can select any of the 4 squares as a red in the first column.

For the second column we can only chose from 3 squares to paint red as we can't select a red square from a square that is on the same row as the first column.

For the third column we can only chose from 2 squares to paint red as we can't select a red square from a square that is on the same row as the first and second columns.

For the fourth column we can only chose from 1 square to paint red as we can't select a red square from a square that is on the same row as the first, second, and third columns.

Therefore the total numbers of squares that can have exactly one red square in each column and exactly one red square in each row and one red in each row is exactly $4 \times 3 \times 2 \times 1$ which is $4!$ configurations in $2D$.

Now we can use this information for the 3D problem by looking at each of these $4 \times 4$ grids as levels of the cube.

Starting with the first level we can chose from any of the $4!$ configurations in $2D$.

For the second level, no red square can have the same row and column location as any of the red squares of the first level and it must be one of the $4!$ configurations in $2D$

For the third level, no red square can have the same row and column location as any of the red squares of the first and second levels and it must be one of the $4!$ configurations in $2D$.

For the fourth level, no red square can have the same row and column location as any of the red squares of the first, second and third levels and it must be one of the $4!$ configurations in $2D$.

When all levels are taken into consideration we will have all positions on a 4x4 grid with exactly one red square.

Starting with the first level configuration with one of the $4!$ configurations as shown above, this configuration has three possible paths to the next level where the red square of the first column is the the one in the 3rd row as shown. Each of these three paths were drawn following the rule that no red squares can be in any of the four red square locations from the previous level.

Not shown in the image this configuration will also have three more possible paths where the red square of the first column is the the one in the 2nd row, and three more possible paths where the red square of the first column is the the one in the 1st row. That is a total of $3 \times 3$ possible paths. Other configurations of the second level from the initial level are impossible because those other configurations will have at least a red square in any of the locations of the red squares of the previous level.

Then each of these configurations on the 2nd level will have 2 paths each to the 3rd level as shown.

Only one path is left from the 3rd level to the 4th level for each of the configurations.

Therefore the total number of "intriguing" colorings will be the product of all paths: $$(4!)(3 \times 3)(2)(1)=\boxed{432}$$

That gives a total of 432 "intriguing" colorings.

Here is an example of one of those "intriguing" colorings:

~Tomas Diaz. orders@tomasdiaz.com