Таблица с числа, Турнир на градовете 2012

[drago]

Дадена е таблица с [tex]2011[/tex] реда и [tex]2012[/tex] стълба, във всяка клетка на която е написано едно от числата: [tex]0[/tex], [tex]1[/tex] или [tex]2[/tex], така че сбора от числата във всеки ред и всеки стълб се дели на [tex]3[/tex].
Да се намери най-големия възможен брой на единиците в клетките на таблицата.

[mdelyakova]

Не можем в един ред или стълб да имаме само единици, защото 2011 и 2012 не се делят на 3=> във всяка колона и във всеки ред ни трябва поне едно различно число от 1. Имаме 2012 колони и 2011 реда, но не можем да използваме пресечните полета на колони и редове,запълнени с единици, защото в колоните различното от 1 число е 0, а в редовете е 2-ка. => трябват ни 2011+2012 числа различни от 1, но ако "изместим" различните от 1 числа в първия ред и последната колона, т.е., ако целият ни първи ред е покрит с 0, а последната колона има 1 нула и 2010 двойки можем да спестим 1 число различно от единица (спестяването е възможно, защото редът и колоната не са запълнени само с единици)=> числата различни от 1 са минимум 2011+2012-1=4022 и 2011*2012-4022=4042110?

[drago]

Aми някак не ме удовлетворява това обяснение!

[drago]

Не ме удовлетворява, защото никак не е строго, не ми пасва и най-вече не е вярно.
Всъщност чак сега реших задачата и е по-красива отколкото си мислех в началото.
Сега една конструкция, която показва, че може да се мине с по-малко числа различни от [tex]1[/tex] от [tex]2012+2011-1[/tex].
Слагаме [tex]1[/tex] в първите [tex]1006[/tex] реда и първите [tex]2010[/tex] стълба. В последните [tex]2[/tex] стълба и първите [tex]1006[/tex] реда слагаме [tex]1[/tex] или [tex]2[/tex] като ги редуваме шахматно. В последните [tex]2[/tex] стълба и последните [tex]1005[/tex] реда слагаме единици. Остават последните [tex]1005[/tex] реда и първите [tex]2010[/tex] стълба. В тази таблица [tex]1005 \times 2010[/tex] поставяме във всеки ред по 2 нули и всичкото друго [tex]1[/tex], така че и във всеки стълб да има само една нула. (това е възможно).
Досега сме използвали само единици с изключение на [tex]2.1005[/tex] нули и [tex]1006[/tex] двойки. И така различните от единица числа са [tex]2.1005+1006[/tex], което е по-малко от [tex]2012 + 2011 -1[/tex].
Но това не е оптималното, оценката може да се подобри още.
Основната идея е, че ако вземем едно число различно от 1 то в реда или стълба(поне едно от двете), на който лежи това число задължително трябва да има още едно различно от 1.

[drago]

И така решението:
Нека запълним цялата таблица с единици. Ясно е, че сумата във всеки ред и стълб не се дели на [tex]3[/tex]. Ще слагаме последователно на мястото на единиците [tex]0[/tex] или [tex]2[/tex]-ки, така че да стигнем до конфигурация удовлетворяваща условието. За краткост да наречем редовете или стълбовете линии, а когато поставим [tex]0[/tex] или [tex]2[/tex] вместо някоя единица, така че сумата в линията(реда или стълба) да стане кратно на [tex]3[/tex] ще казваме, че това оправя линията. Например ако сложим някъде [tex]2[/tex] то тя ще оправи реда в който е, а ако сложим [tex]0[/tex] тя ще оправи стълба. И така каквото и да сложим може да оправим най-много една линия- или реда или стълба, но не и двете. Да, но ако сложим две нули в един ред ще оправим 3 линии- реда, в който са и двата стълба. Ако сложим две двойки в един стълб това също ще оправи 3 линии- стълба и двата реда. И така две числа, различни от [tex]1[/tex], сложени подходящо оправят 3 линии. Линиите общо са [tex]2012+2011=4023[/tex] и тъй като две числа оправят 3 линии, то за да оправим всичките [tex]4023[/tex] линии ще са необходими поне [tex]\frac{2}{3}.4023=2682[/tex] числа различни от [tex]1[/tex].
И това е екстремума, а ако горното разсъждение се струва на някой недостатъчно строго, за седми клас толкова .
Конструкция с [tex]2682[/tex] числа различни от [tex]1[/tex] можем да построим лесно, имайки горното предвид. Слагаме две нули в произволен ред, те оправят 3 линии- реда и двата стълба. Зачеркваме тези линии. Слагаме 2 двойки в произволни незачеркнати клетки от един и същи стълб. Те оправят 3 линии- стълба и двата реда. Зачеркваме тези линии. И така, зачеркнали сме три реда и три стълба. Като повторим тази операция [tex]670[/tex] пъти ще сме зачеркнали [tex]2010[/tex] реда и [tex]2010[/tex] стълба. В пресечните клетки на останалия един ред и два стълба слагаме [tex]0[/tex] и така всичко е ОК, т.е. сумата на числата във всеки ред и стълб се дели на [tex]3[/tex].
Значи максималния брой единици, които могат да стоят в клетките на таблицата са [tex]2012.2011 - 2682[/tex].

[drago]

Малко продължение...
Чистата идея заложена в тази задача, изчистена от елементите на теория на числата, таблици,... звучи така:

Дадено е множество от [tex]n[/tex] елемента.(в нашия случай [tex]n= 4023[/tex] и се интерпретират като линиите в таблицата).
[tex]A_1, A_2,\ldots, A_m[/tex] са [tex]m[/tex] подмножества на [tex]S[/tex], състоящи се от два елемента със следните свойства:
1) [tex]A_1 \cup A_2 \cup \ldots \cup A_m = S[/tex] .
2) за всяко [tex]i,\, 1\leq i \leq m[/tex] съществува [tex]j,\, j\neq i[/tex] ,така че [tex]A_i \cap A_j \neq \emptyset[/tex].

Да се докаже, че [tex]m \geq \lceil \frac{2}{3} n \rceil[/tex].

И тъй като това може го четат седмокласници пояснявам: [tex]\lceil x \rceil[/tex] означава най-малкото цяло число по-голямо от [tex]x[/tex].
[tex]A_i[/tex] се интерпретира като двете линии, които определя всяко число в таблицата различно от 1. Точка 1) се интерпретира като: във всяка линия(ред или стълб) има поне едно число различно от 0, т.е. ако зачеркнем всички редове и стълбове на всяко различно от 1 число ще покрием всички линии.
Точка 2) се интерпретира така: не може да има число различно от 1 самичко в реда и стълба, който определя.

[drago]

Сега да напишем горното твърдение на езика на графите.
Твърдение 2.
Даден е граф [tex]G[/tex] с [tex]n[/tex] върха и [tex]m[/tex] ребра. Ако е известно, че всеки свързан компонент на [tex]G[/tex] е с повече от [tex]2[/tex] върха (т.е. поне с [tex]3[/tex] върха), да се докаже че [tex]m \geq \lceil \frac{2}{3} n \rceil[/tex].
Доказателство.
Първо ще докажем, че ако [tex]G_1[/tex] e едносвързан граф с [tex]n_1[/tex] върха и [tex]m_1[/tex] ребра то [tex]m_1 \geq n_1-1[/tex].
Да се убедим, че можем да подредим върховете на [tex]G_1[/tex] като [tex]v_1,v_2,\ldots,v_{n_1}[/tex], така че [tex]v_i[/tex] да е свързано с някой от [tex]v_1,v_2,\ldots,v_{i-1}[/tex]. Разсъждаваме индуктивно. С [tex]v_1[/tex] означаваме произволен връх на [tex]G_1[/tex]. Нека сега [tex]v_1,v_2,\ldots,v_i[/tex] са избрани, че да удовлетворяват искането. Нека [tex]v[/tex] е един различен от тези върхове. Тъй като [tex]G_1[/tex] е свързан, то има път в графа, който свързва [tex]v[/tex] с [tex]v_1[/tex]. Toгава с [tex]v_{i+1}[/tex] означаваме последния рзличен от [tex]v_1,v_2,\ldots,v_i[/tex] връх в този път преди той окончателно да влезе във [tex]v_1,\ldots,v_i[/tex].
Това подеждане лесно дава [tex]m_1 \geq n_1-1[/tex].
Сега нека [tex]G_1,G_2,\ldots,G_k[/tex] са свързаните компоненти на [tex]G[/tex], които имат съответно [tex]n_1,n_2,\ldots,n_k[/tex] върхове и [tex]m_1,m_2,\ldots,m_k[/tex] ребра. Тогава [tex]n_i \geq 3[/tex] и [tex]m_i \geq n_i - 1[/tex], от което следва [tex]m_i \geq \lceil \frac{2}{3} n_i \rceil[/tex], oткъдето пък следва:
[tex]m=m_1+\ldots\ + m_k \geq \lceil \frac{2}{3}n_1 \rceil +\ldots + \lceil \frac{2}{3}n_k \rceil \geq \lceil \frac{2}{3}(n_1+\ldots + n_k) \rceil = \lceil \frac{2}{3}n \rceil[/tex].

Това е. Има една приказка "Защо просто като може сложно", ха-ха .
Иначе задачата е давана на 7 клас на турнира в Созопол 17-20.09.2012.

[drago]

И тъй като ми са интересни и други подходи, преди 2 дни пуснах задачата в арт-а.
Досега няма няма постове. Интересно...
http://www.artofproblemsolving.com/Foru ... 2&t=501949