3
For 1≤i≤2021 and 1≤j≤2021, let (i,j) denote the cell in the i-th row and the j-th column, and let f(i,j) denote the number filled in (i,j). We also define g(i,j) as
g(i,j)={f(i,j)4−f(i,j)(i+j is even),(i+j is odd).
It is easy to check that g(i,j)∈{1,2,3} and g satisfies, for 1≤i≤2020 and 1≤j≤2020,
g(i+1,j)−g(i,j)=g(i+1,j+1)−g(i,j+1).(∗)
Indeed, since f(i,j)+f(i,j+1)+f(i+1,j)+f(i+1,j+1)=8, if i+j is even,
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)
and if i+j is odd,
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).
On the other hand, if we assign g(i,j) for 1≤i≤2021 and 1≤j≤2021 in such a way that g(i,j)∈{1,2,3} and g satisfies (*),
f~(i,j)={g(i,j)4−g(i,j)(i+j is even),(i+j is odd).
satisfies the restriction of the original problem. Hence, A equals to the number of cases of defining g(i,j) under the above condition.
Let M and m denote the maximum and the minimum of {g(1,1),…,g(1,2021)}, respectively. Having (*) for every 1≤i≤2020 and 1≤j≤2020 is equivalent to the condition that g(k+1,ℓ)−g(1,ℓ) is constant for 1≤ℓ≤2021 for each 1≤k≤2020. We denote this constant value by dk. Since 1≤g(i,j)≤3 for every (i,j) is equivalent to 1≤m+dk and M+dk≤3, or 1−m≤dk≤3−M, for every 1≤k≤2020, there are (3+m−M)2020 possibilities for assigning g(i,j) when g(1,1),…,g(1,2021) are given.
* M−m=0.
In this case we have g(1,1)=⋯=g(1,2021) and there are only 3 possibilities for (g(1,1),…,g(1,2021)). For each possibility, we have 32020 ways of assigning the rest of g(i,j), thus the number of cases is 3⋅32020=32021.
* M−m=1.
In this case we have m=1 or 2. For each m, we have 22021−2 possibilities for (g(1,1),…,g(1,2021)). Thus, the number of cases is 2⋅((22021−2)⋅22020)=24042−22022.
* M−m=2.
In this case we have 32021−2⋅(22021−2)−3 possibilities for (g(1,1),…,g(1,2021)). Thus, the number of cases is (32021−2⋅(22021−2)−3)⋅12020=32021−2⋅(22021−2)−3.
A=32021+(24042−22022)+(32021−2⋅(22021−2)−3)=2⋅32021+24042−22023+1.
To obtain the remainder after dividing A by 100, we compute A(mod4) and A(mod25). Since 32021≡3(mod4), we have A≡2⋅3+0−0+1≡3(mod4). And since 220≡320≡1(mod25) from Euler's totient theorem,
A≡2⋅3⋅(320)101+22⋅(220)202−23⋅(220)101+1≡6+4−8+1≡3(mod25).
This concludes that A≡3(mod100).