Maths Olympiad Prep

Library / /14 of 21

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it South Korea

Consider the sixteen tiles fixed on a wall as shown below. How many ways are there to write either 00 or 11 on each tile so that the product of the two numbers written on every neighboring pair of tiles (sharing a common side) is always 00?

Figure 1

Solution

When 00 or 11 is written on each tile in such a way that the product of the two numbers written on every neighboring pair of tiles is always 00, we'll call the status a z-pattern. First, we prove a couple of lemmas.

Lemma 1. Let ana_n be the number of z-patterns for nn tiles laid in a row. Then
an=Fn+2 a_n = F_{n+2}
for all n1n \ge 1, where FnF_n is the nn-th Fibonacci number defined by F1=1F_1 = 1, F2=1F_2 = 1, and Fn+2=Fn+1+FnF_{n+2} = F_{n+1} + F_n for all n1n \ge 1.

Proof. We prove by induction on n1n \ge 1. It is clear that the lemma holds for n=1n=1 and n=2n=2. Assume the lemma for all kk, 1k<n1 \le k < n, where n3n \ge 3. If 00 is written on the tile at one end, then any number (00 or 11) can be written on the next tile and hence there are an1a_{n-1} such z-patterns. If 11 is written there, then 00 should be written on the next tile and hence there are an2a_{n-2} such z-patterns. Thus we get
an=an1+an2=Fn+1+Fn=Fn+2, a_n = a_{n-1} + a_{n-2} = F_{n+1} + F_n = F_{n+2},
which proves the lemma.

Lemma 2. Let bnb_n be the number of z-patterns for nn tiles fixed on a wall in a ring shape. Then
bn=an1+an3=Fn+1+Fn1 b_n = a_{n-1} + a_{n-3} = F_{n+1} + F_{n-1}
for all n4n \ge 4.

Proof. Let n4n \ge 4 and choose any tile among the nn tiles fixed on a wall in a ring shape. If 00 is written on the tile, then any number can be written on the neighboring tiles and hence there are an1a_{n-1} such z-patterns. If 11 is written on the tile, then 00 should be written on the neighboring two tiles and hence there are an3a_{n-3} such z-patterns. Thus we get
bn=an1+an3=Fn+1+Fn1, b_n = a_{n-1} + a_{n-3} = F_{n+1} + F_{n-1},
which proves the lemma.

We now return to the problem. Consider the 2×22 \times 2 tiles in the center. Observe that the number of 00's that can be written on these four tiles equals 44, 33 or 22.

Case 1) Four 00's:
[0000] \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}
We may apply Lemma 2 to the 1212 tiles surrounding the four tiles in the center because any number can be written on the 1212 tiles. Therefore, the number of z-patterns in this case equals
b12=F13+F11=233+89=322. b_{12} = F_{13} + F_{11} = 233 + 89 = 322.

Case 2) Three 00's:
[1000] \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}
[0100] \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}
[0010] \begin{bmatrix} 0 & 0 \\ 1 & 0 \end{bmatrix}
[0001] \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}
In each of the four subcases, only 00 can be written on two neighboring tiles of the tile marked by 11. For the remaining 1010 tiles, it is clear that the number of z-patterns equals to a9×2=F11×2=178a_9 \times 2 = F_{11} \times 2 = 178. Therefore, the total number of z-patterns in this case equals
178×4=712. 178 \times 4 = 712.

Case 3) Two 00's:
[1001] \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}
[0110] \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}
In each of the two subcases, only 00 can be written on four neighboring tiles of the two tiles marked by 11. For the remaining 66 tiles, it is clear that the number of z-patterns equals to a32×22=F52×4=100a_3^2 \times 2^2 = F_5^2 \times 4 = 100. Therefore, the total number of z-patterns in this case equals
100×2=200. 100 \times 2 = 200.

Combining the three cases, the answer is: 322+712+200=1234322 + 712 + 200 = 1234. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.