Numbers $0, 1$ and $2$ are placed in a table $2005 \times 2006$ so that total sums of the numbers in each row and in each column are factors of $3$. Find the maximal possible number of $1$'s that can be placed in the table. (6 points)
Problem
Source: Spring 2006 Tournament of Towns Junior A-Level #5
Tags:
21.03.2022 22:59
Answer:$2005\cdot2006-2\cdot1337$
22.03.2022 01:09
Rephrase: Rephrased Problem wrote: The numbers $0, 1$ and $2$ are placed in a $2005 \times 2006$ table so that the total sum of the numbers in each row is $1 \pmod{3}$ and the total sum of the numbers in each column is $2 \pmod{3}.$ Find the minimal possible $1$s and $2$s that can be placed in the table. Let there be $m$ $1$s and $n$ $2$s. Each row must have one $1$ or two $2$s. Each column must have two $1$s or one $2$. So $m + n/2 \ge 2005,$ and $n + m/2 \ge 2006.$ Summing these up gives $m+n \ge \frac{2}{3} (2005+2006) = 2674.$ To achieve equality, extend this construction for $7 \times 8$: [asy][asy] unitsize(1cm); defaultpen(font("OT1","cmss","m","n")); defaultpen(fontsize(48pt)); for (int i=0; i<8; ++i) { draw((i,0)--(i,7)); draw((0,i)--(8,i)); } draw((8,0)--(8,7)); label(scale(1)*"2",(0.5,6.5)); label(scale(1)*"2",(1.5,6.5)); label(scale(1)*"2",(2.5,5.5)); label(scale(1)*"2",(3.5,5.5)); label(scale(1)*"2",(4.5,4.5)); label(scale(1)*"2",(5.5,4.5)); label(scale(1)*"1",(6.5,3.5)); label(scale(1)*"1",(6.5,2.5)); label(scale(1)*"1",(7.5,1.5)); label(scale(1)*"1",(7.5,0.5)); [/asy][/asy] So our actual answer is $2005 \cdot 2006 - 2674= \boxed{4022030}.$