Japan 2013 Initial Round

$$2^{(n+1{)}^3-1}+2^{3n}+2\text{ ways}$$ A lattice square with its sides directed is congruent in the sense of the problem with one of the four types of such lattice square shown above. For each of these types we determine a number of ways of giving directions to every lattice segment contained in the region $0\le x,y,z\le n$ so that all the lattice squares in the region become congruent to the lattice square of that type.

a. Let $O=(0,0,0)$, $X=(1,0,0)$, $Y=(0,1,0)$, $Z=(0,0,1)$. Suppose the lattice segment $OX$ is assigned the direction $O\to X$. Then, since the lattice square containing $O,X,Y$ is congruent to the type (A) lattice square, we see that the lattice segment $OY$ must be given the direction $O\leftarrow Y$. Similarly, we see that the lattice segment $OZ$ must have direction $O\leftarrow Z$. But then the lattice square containing $O,Y,Z$ cannot be congruent to the type (A) lattice square. In the same way, we obtain the fact that if the lattice segment $OX$ is given the direction $O\leftarrow X$ there exists a lattice square not congruent with type (A) lattice square. Therefore, we conclude that there is 0 way of giving directions to all the lattice segments to get all the lattice squares to be congruent to the type (A) lattice square.

b. When a lattice square is congruent to the type (B) lattice square, then if you decide the direction of one of the sides of the square, the directions of other three sides are determined uniquely. Therefore, if you just assign a direction to any one lattice segment, then there is at most 1 way of assigning directions to all the lattice segments in the region so as to make all the lattice squares congruent to the type (B) lattice square. Thus, the number of ways to assign directions to all lattice segments to get all the lattice squares to be congruent to the type (B) lattice squares is at most 2. Now for a lattice square with one vertex having the coordinates $(x,y,z)$, then other end points of the two sides of the square sharing the vertex $(x,y,z)$ have the coordinates whose sum has the even-odd parity different from $x+y+z$. So, if you give a direction to each lattice segment by assigning a positive direction to the segment starting with a point having coordinates with an even sum ending with the point having coordinates with an odd sum, then the resulting orientations of all the lattice segments yield the situation where all the lattice squares are congruent to the type (B) lattice square. The same is also true if you give a direction to each lattice segment in such a way that a segment starting with a point having coordinates with an odd sum and ending with a point having coordinates with an even sum receives a positive direction. Therefore, there are exactly 2 ways of assigning directions to all the lattice segments to satisfy the requirement of the problem in this case.

c. We can see that the statement that a lattice square is congruent to the type (C) lattice square is equivalent to the statement that parallel sides of a square have the same direction. Consequently, if all the lattice segments are assigned directions so as to satisfy the condition that all the lattice squares are congruent to the type (C) lattice square, then the directions given to lattice segments parallel to the x-axis and having the same x-coordinate must be the same. The same statement holds for all the lattice segments parallel to the y-axis (z-axis) and having the same y-coordinate (z-coordinate, respectively). Conversely, if we give directions to all the lattice segments in such a way that all the parallel segments with the same relevant coordinates have the same direction, then the resulting orientations of the sides of lattice squares show that all of the lattice squares have parallel sides with the same direction so that they are all congruent to the type (C) lattice square. Therefore, we can assign directions arbitrarily to the lattice segments on x, y and z-axis to get the desired assignment of directions to all the lattice segments to so as to satisfy the condition of the problem in this case. There are $2^{3n}$ different ways of assigning directions to lattice segments in the region lying on one of the coordinate axes. So, $2^{3n}$ is the desired number in this case.

d. It is easy to see that the statement that a lattice square is congruent to the type (D) lattice square is equivalent to the following statement: With respect to the perpendicular axis through the center of a square the number of sides of the square assigned with counter-clockwise direction minus the number of sides assigned with clockwise direction is either -2 or 2. Note that the condition stated above does not depend on the fact how the directions of the sides of the square are observed, either from the positive side of the central axis or from the negative side. We now need two lemmas to complete the argument of the assertion in this case.

Lemma 1. If a lattice square is congruent to the type (D) lattice square, then once the directions of 3 of its sides are specified, the orientation of the remaining side is uniquely determined.

Proof: With respect to the perpendicular axis through the center of a lattice square, for any given 3 sides of the square the number of those having the counter-clockwise direction minus the number of those having the clockwise direction is -3, -1, 1 or 3. If we give the counter-clockwise direction to the remaining side, then this difference increases by 1, while if we assign clock-wise direction, then this difference decreases by 1. Therefore, one and only one choice of the assignment of direction for the remaining side satisfies the equivalent statement given above in order for the square to be congruent to the type (D) lattice square.

Lemma 2. For a cube with unit side length, if 5 of the 6 faces are all congruent to the type (D) lattice square, then the remaining face also is congruent to the type (D) lattice square.

Proof: If we observe the cube from outside, we see that each edge of the cube is contained in two adjacent faces and the direction assigned to an edge has the counter-clockwise direction with respect to one of the faces and the clockwise direction with respect to the other. Therefore, if we add the differences between the number of sides with the counter-clockwise orientation and the number of sides with the clockwise orientation for all 6 faces of the cube, we get the value 0. Furthermore, if we observe from outside each of the 5 faces of the cube which are congruent to the type (D) lattice square, then we have the difference between the number of sides with the counter-clockwise orientation and the number of sides with the clockwise orientation to be -2 or 2. Therefore, the sum of these differences for the five congruent faces must take value in the set $\{-12,-6,-2,2,6,12\}$.

For the remaining 6-th face of the cube the same difference must take the value greater than or equal to -4 and less than or equal to 4. Since the sum of these differences over all 6 faces must equal 0, we conclude that this difference for the 6-th face must be 2 or -2, which implies that the 6-th face is also congruent to the type (D) lattice square.

In view of Lemma 1, there is at most one way of assigning a direction to all of the lattice segments to get the configuration resulting with all lattice squares being congruent with the type (D) lattice square, if we start by assigning a direction to each of the lattice segments parallel to the x-axis, and then assign to each of the lattice segments lying on the yz-plane and parallel to the y-axis, and finally assign a direction to all of the lattice segments on the z-axis. Conversely, if we assign directions to these lattice segments mentioned above in the way specified, then by Lemma 1, we see that there is a way to assign directions to all the remaining lattice segments lying on the yz-plane in such a way that all the lattice squares lying on the yz-plane become congruent to the type (D) lattice square. Furthermore, we can determine directions of all the lattice segments which are perpendicular to the x-axis in such a way that all the lattice squares parallel to the x-axis becomes congruent to the type (D) lattice square. The Lemma 2 now guarantees that all the remaining lattice squares perpendicular to the x-axis are congruent to the type (D) lattice square. Thus, we conclude that the number of ways to assign directions to all of the lattice segments to satisfy the requirement of the problem in the case we are considering is given by $2^{n(n+1{)}^2+n(n+1)+n}=2(n+1{)}^3-1$.

Summing the numbers of possible ways of assigning the directions to lattice segments in the cases (a)~(d), we obtain $2^{(n+1{)}^3-1}+2^{3n}+2$ as the desired answer.