Оцветяване на топки

[drago]

Дадена е правоъгълна таблица [tex]n[/tex] х [tex]m[/tex] . Във всяка от [tex]nm[/tex]-те клетки има определен брой топки. Сумата на топките във всеки ред и всеки стълб е не повече от [tex]M[/tex].
Докажете, че всяка топка може да се оцвети в един от общо [tex]M[/tex] цвята, така че във всеки ред и стълб да няма еднакво оцветени топки.

[ptj]

Мисля, че тази задача има връзка със задачата за небиещите се царици на произволна шахматна дъска с размери [tex]nxn[/tex]. Тя има универсални решения за [tex]n\ge 6[/tex]. Като ученик писах един реферат за "Обобщена задача на Ким" - подобна на спомената, но всяка царица може да бие точно по [tex]k[/tex] други [tex](0\le k\le 4)[/tex]. В нея решенията са максимални и се достигат.

[drago]

Мисля, че тази задача има връзка със задачата за небиещите се царици на произволна шахматна дъска...

Aз не виждам да има, но както казва Остап Бендер, щом казваш, че има, значи има!

[ptj]

Мда, няма пряка връзка, заради липсата на диагонали.

Една идея за решение:

Нека разгледаме квадратна дъска с размери [tex]M[/tex]x[tex]M[/tex] във всяка клетка на която има точно по една топка. Ще покажем, че съществува оцветяване в [tex]M[/tex] различни цвята, така че във всеки ред и стълб да няма топки с еднакъв цвят.

1.) В цвят 1 оцветяваме главния диагонал.
2.) В цвят 2 оцветяваме:
- успоредния на него, съдържащ (2;1);
-успоредния, минаващ през (1;M).
3.) В цвят 3 оцветяваме
-успоредния на него, съдържащ (3;1);
успоредния, минаващ през (1;M-1).
4.) В цвят 4 оцветяваме: -
-успоредния на него, съдържащ (4;1);
-успоредния, минаващ през (1;M-2).
и.т.н.

Остава да се покаже, че топките от оригиналното условие на задачата са не повече от [tex]M^2[/tex].
Тогава ще съществува разместване разполагащо ги на дъска [tex]M[/tex]x[tex]M[/tex], така че във всяка клетка да има не повече от една топка. Тъй като за тях вече съществува оцветяване, по обратния път ще могат да се оцветят и в оригиналната задача.

[drago]

Ako таблицата е [tex]M[/tex] x [tex]M[/tex] и във всяка клетка има 1 топка, оцветяването е очевидно- "шахматно", клетката [tex](i, j)[/tex] oцветяваме с цвета [tex]i+j \,\, mod(M)[/tex].

Тогава ще съществува разместване разполагащо ги на дъска x, така че във всяка клетка да има не повече от една топка. Тъй като за тях вече съществува оцветяване, по обратния път ще могат да се оцветят и в оригиналната задача.

Tова за обратния път не го разбрах?!
Задачата не е чак толкова проста.

[ptj]

Прав си, директно не е вярно. Променят се редовете и стълбовете.

[drago]

Жокер.
Да пробваме индукция по [tex]M[/tex]. Един от начините да сработи е ако можем да изберем известно количество топки, така че във всеки ред и всеки стълб да има точно една от избраните. Ако допуснем, че това сме го осигурили, тогава като ги махнем ще намалим с единица максималния брой на топките във всеки ред/стълб- той ще стане [tex]M-1[/tex]. Тях от индукционното предположение ще можем да ги оцветим в [tex]M-1[/tex] цвята. Накрая боядисваме отделените в М-тия цвят и индукцията приключва.
И така остава да проверим твърдението в подчертания шрифт...

[drago]

Забравил съм тази задача без да поствам решението.
Интересно е, че е давана на конкурса "А. Колмогоров" в Русия и в оригинала е формулирана на езика на графите: http://www.artofproblemsolving.com/Foru ... 1&t=426084

Формулировката, така както е тука ми се стори някак по нагледна и по-лесно да се търси решение. Видях бегло публикуваното решение и си помислих, че може да се избегне изпозването на Теоремата на Хол за двойките(Hall's marriage theorem). За съжаление в това, което написах, имаше грешка, която обаче можеше да се изправи, но пък с използването пак на тази теорема. Повече подробности тук:
http://www.artofproblemsolving.com/Foru ... 4#p2415204