Азия-тынық мұхит математикалық олимпиадасы, 2012 жыл

Өлшемі $2012 \times 2012$ тақтаның әр шаршысына бір уақытта 0-ден кем емес және 1-ден үлкен емес нақты сандар жазылған. Тақтаны горизонталь немесе вертикаль тор сызықтарымен екі бос емес тіктөртбұрыштарға бөлуді қарастырайық. Осындай кез келген бөлуде кемінде бір тіктөртбұрыштағы сандар қосындысы 1-ден аспасын. $2012 \times 2012$ тақтаның барлық сандар қосындысының ең үлекен мүмкін мәнін табыңыз.

Комментарий/решение

Действительно, легко обобщить сетку $n \times n$ для $n \ge 3$ и получить $5$ как максимально возможную сумму. Сначала я запутался, потому что думал, что нельзя использовать $0$, но после того, как я понял, что можно, это стало легко.

Чтобы показать, что $5$ достижимо, поместите $1$ в $(2,1), (2,2), (2,3), (1,2), (3,2)$, а затем $0$ во что-нибудь еще.

Теперь мы показываем, что $5$ — это круто. Предположим, что сумма $S$ достижима. Тогда следует, что сумма некоторого столбца не меньше $S-2$, поскольку пусть сумма столбца $m^{th}$ равна $C_m$. Тогда как только $C_1 + C_2 + ... + C_k > 1$, нам, очевидно, понадобится $C_1 + C_2 + ... + C_k \ge S-1$. Затем, используя аналогичные аргументы, в этом столбце есть элемент размером не менее $S-4$, но это означает $S-4 \leq 1 S \le 5$, и мы закончили.