n x n квадрат с числа, МО ИРАН 2012

[drago]

Даден е квадрат [tex]n \times n[/tex], във всяка клетка на който е записано цяло число. Да се докаже, че при достатъчно голямо [tex]n[/tex] съществува квадрат във вътрешността на дадения, такъв, че сумата от числата в клетките му се дели на [tex]2012[/tex].

[drago]

На всяка клетка да съпоставим сумата на всички числа попадащи в правоъгълника наляво и надолу от нея. Така се получава една функция [tex]F[/tex], чрез която може да се изрази сумата от числата в даден квадрат. Именно, сумата на числата попадащи в квадрат с върхове [tex]A_1, A_2,A_3, A_4[/tex] е равна на [tex]F(A_1) + F(A_3)-F(A_2)-F(A_4)[/tex].
Остава да намерим подходящите върхове, така че горното да се дели на 2012. За това е достатъчно да намерим такива върхове на квадрат, така че [tex]F(A_1), F(A_2), F(A_3), F(A_4)[/tex] да дават един и същ остатък по модул [tex]2012[/tex].
Всъщност това, което ни трябва е че ако оцветим произволно клетките в [tex]2012[/tex] цвята, при дост. голямо [tex]n[/tex] винаги има еднакво оцветени, които образуват върхове на квадрат, частен случай от теоремата на Gallai.
За по-подробно вижте тук, има и препратка към една статия: http://www.artofproblemsolving.com/Foru ... 2&t=498511

П.П. Малко съм си позволил да редактирам оригиналната задача, там вместо 2012 стоеше 1391.