Maths Olympiad Prep

Library / /42 of 63

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Japan

Let AA be the number of cases such that each cell of a 2021×20212021 \times 2021 table is filled with one of 11, 22, or 33 in such a way that any 2×22 \times 2 square in the table sums up to 88. Answer the remainder after dividing AA by 100100.

Solution

3\boxed{3}

For 1i20211 \le i \le 2021 and 1j20211 \le j \le 2021, let (i,j)(i, j) denote the cell in the ii-th row and the jj-th column, and let f(i,j)f(i, j) denote the number filled in (i,j)(i, j). We also define g(i,j)g(i, j) as
g(i,j)={f(i,j)(i+j is even),4f(i,j)(i+j is odd). g(i, j) = \begin{cases} f(i, j) & (i + j \text{ is even}), \\ 4 - f(i, j) & (i + j \text{ is odd}). \end{cases}

It is easy to check that g(i,j){1,2,3}g(i, j) \in \{1, 2, 3\} and gg satisfies, for 1i20201 \le i \le 2020 and 1j20201 \le j \le 2020,
g(i+1,j)g(i,j)=g(i+1,j+1)g(i,j+1).() g(i+1, j) - g(i, j) = g(i+1, j+1) - g(i, j+1). \quad (*)
Indeed, since f(i,j)+f(i,j+1)+f(i+1,j)+f(i+1,j+1)=8f(i, j) + f(i, j + 1) + f(i + 1, j) + f(i + 1, j + 1) = 8, if i+ji + j is even,
g(i+1,j)g(i,j)=(4f(i+1,j))f(i,j)=f(i+1,j+1)(4f(i,j+1))=g(i+1,j+1)g(i,j+1) \begin{aligned} g(i+1, j) - g(i, j) &= (4 - f(i+1, j)) - f(i, j) \\ &= f(i+1, j+1) - (4 - f(i, j+1)) \\ &= g(i+1, j+1) - g(i, j+1) \end{aligned}
and if i+ji + j is odd,
g(i+1,j)g(i,j)=f(i+1,j)(4f(i,j))=(4f(i+1,j+1))f(i,j+1)=g(i+1,j+1)g(i,j+1). \begin{aligned} g(i+1, j) - g(i, j) &= f(i+1, j) - (4 - f(i, j)) \\ &= (4 - f(i+1, j+1)) - f(i, j+1) \\ &= g(i+1, j+1) - g(i, j+1). \end{aligned}
On the other hand, if we assign g(i,j)g(i, j) for 1i20211 \le i \le 2021 and 1j20211 \le j \le 2021 in such a way that g(i,j){1,2,3}g(i, j) \in \{1, 2, 3\} and gg satisfies (*),
f~(i,j)={g(i,j)(i+j is even),4g(i,j)(i+j is odd). \tilde{f}(i, j) = \begin{cases} g(i, j) & (i + j \text{ is even}), \\ 4 - g(i, j) & (i + j \text{ is odd}). \end{cases}
satisfies the restriction of the original problem. Hence, AA equals to the number of cases of defining g(i,j)g(i, j) under the above condition.

Let MM and mm denote the maximum and the minimum of {g(1,1),,g(1,2021)}\{g(1, 1), \dots, g(1, 2021)\}, respectively. Having (*) for every 1i20201 \le i \le 2020 and 1j20201 \le j \le 2020 is equivalent to the condition that g(k+1,)g(1,)g(k+1, \ell) - g(1, \ell) is constant for 120211 \le \ell \le 2021 for each 1k20201 \le k \le 2020. We denote this constant value by dkd_k. Since 1g(i,j)31 \le g(i, j) \le 3 for every (i,j)(i, j) is equivalent to 1m+dk1 \le m + d_k and M+dk3M + d_k \le 3, or 1mdk3M1 - m \le d_k \le 3 - M, for every 1k20201 \le k \le 2020, there are (3+mM)2020(3 + m - M)^{2020} possibilities for assigning g(i,j)g(i, j) when g(1,1),,g(1,2021)g(1, 1), \dots, g(1, 2021) are given.

* Mm=0M - m = 0.

In this case we have g(1,1)==g(1,2021)g(1, 1) = \dots = g(1, 2021) and there are only 33 possibilities for (g(1,1),,g(1,2021))(g(1, 1), \dots, g(1, 2021)). For each possibility, we have 320203^{2020} ways of assigning the rest of g(i,j)g(i, j), thus the number of cases is 332020=320213 \cdot 3^{2020} = 3^{2021}.

* Mm=1M - m = 1.

In this case we have m=1m = 1 or 22. For each mm, we have 2202122^{2021} - 2 possibilities for (g(1,1),,g(1,2021))(g(1, 1), \dots, g(1, 2021)). Thus, the number of cases is 2((220212)22020)=24042220222 \cdot ((2^{2021} - 2) \cdot 2^{2020}) = 2^{4042} - 2^{2022}.

* Mm=2M - m = 2.

In this case we have 320212(220212)33^{2021} - 2 \cdot (2^{2021} - 2) - 3 possibilities for (g(1,1),,g(1,2021))(g(1, 1), \dots, g(1, 2021)). Thus, the number of cases is (320212(220212)3)12020=320212(220212)3(3^{2021} - 2 \cdot (2^{2021} - 2) - 3) \cdot 1^{2020} = 3^{2021} - 2 \cdot (2^{2021} - 2) - 3.

A=32021+(2404222022)+(320212(220212)3)=232021+2404222023+1. A = 3^{2021} + (2^{4042} - 2^{2022}) + (3^{2021} - 2 \cdot (2^{2021} - 2) - 3) = 2 \cdot 3^{2021} + 2^{4042} - 2^{2023} + 1.

To obtain the remainder after dividing AA by 100100, we compute A(mod4)A \pmod{4} and A(mod25)A \pmod{25}. Since 320213(mod4)3^{2021} \equiv 3 \pmod{4}, we have A23+00+13(mod4)A \equiv 2 \cdot 3 + 0 - 0 + 1 \equiv 3 \pmod{4}. And since 2203201(mod25)2^{20} \equiv 3^{20} \equiv 1 \pmod{25} from Euler's totient theorem,
A23(320)101+22(220)20223(220)101+16+48+13(mod25). A \equiv 2 \cdot 3 \cdot (3^{20})^{101} + 2^2 \cdot (2^{20})^{202} - 2^3 \cdot (2^{20})^{101} + 1 \equiv 6 + 4 - 8 + 1 \equiv 3 \pmod{25}.
This concludes that A3(mod100)A \equiv 3 \pmod{100}.

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 and solution reproduced as published; topic and difficulty added by this site.