Може ли помощ за една задача:Дадено е крайно множество от точки с цели координати.Да се докаже,че можем да ги оцветим в бяло и черно,така че на всеки ред и стълб модул -черно-бяло да е по-малко или равно на 1?
Ще наричаме „
правилно” всяко оцветяване, при което абсолютната стойност на разликата от броя на белите (Б) и броя на черните (Ч) точки във всеки ред и във всеки стълб е не по-голяма от 1, т.е. │Б – Ч│≤ 1.
Лема: При всяко правилно оцветяване, ред/стълб, който съдържа четен брой точки, трябва да съдържа по равен брой бели и черни точки.
Доказателство: Нека имаме ред/стълб, който съдържа 2T (Т ≥ 1) на брой точки, като Ч от тях са черни (0 ≤ Ч ≤ 2Т). Тогава, броят на белите точки в този ред/стълб е Б = 2Т – Ч и следователно │Б – Ч│=│2Т – Ч – Ч│=│2Т – 2Ч│= 2│Т – Ч│≤ 1. Понеже числото │Т – Ч│е цяло, то единствената възможност е │Т – Ч│= 0 и следователно Т = Ч = Б.
Доказателството на задачата ще извършим с индукция по броя на точките от множеството.
База на индукцията: Ако множеството се състои само от една точка – А, оцветяваме А в бяло и получаваме правилно оцветяване.
Стъпка на индукцията: Да допуснем, че за някое естествено число Т > 1, всяко множество от точки с целочислени координати може да се оцвети правилно. Ще докажем, че всяко множество от Т + 1 точки с целочислени координати също може да се оцвети правилно.
Случай 1: Има ред/стълб, който съдържа нечетен брой точки. Без ограничение на общността може да приемем, че това е ред. Нека А е най-лявата точка от този ред. Според индукционната хипотеза, останалите Т точки от множеството (без А) могат да се оцветят правилно. Понеже в реда, който съдържа А оцветените точки са четен брой то, според лемата, белите и черните точки в този ред са по равен брой (Б = Ч).
Разглеждаме колоната, която съдържа А. Ако в нея Б – Ч = 1, оцветяваме А в черно и получаваме правилно оцветяване на Т + 1 на брой точки (след оцветяването на А в черно, в реда Б – Ч = –1, а в колоната Б – Ч = 0). Ако в колоната Б – Ч = –1, оцветяваме А в бяло и получаваме правилно оцветяване. Ако в колоната Б – Ч = 0, оцветяваме А в черно или бяло и получаваме правилно оцветяване.
Случай 2: Няма ред/стълб, който съдържа нечетен брой точки, т.е. всички редове и стълбове съдържат четен брой точки. Нека А е най-лявата точка от най-долния ред (в случая може да изберем произволна точка). Според индукционната хипотеза, останалите Т точки от множеството (без А) могат да се оцветят правилно.
Според лемата, във всички редове, които не съдържат А и във всички стълбове, които не съдържат А има по равен брой бели и черни точки. В реда, който съдържа А и в стълба, който съдържа А са оцветени нечетен брой точки (всички без А), т.е. в този ред и в този стълб │Б – Ч│= 1.
Нека в реда, който съдържа А за оцветените точки имаме Б – Ч = 1. Понеже във всички останали редове броя на белите и черните точки е равен, то броя на всички бели точки от множеството е с едно повече от броя на всички черни точки от множеството. Нека разгледаме стълба, който съдържа А. Понеже във всички останали стълбове броя на белите и черните точки е равен, то в стълба, който съдържа А броя на белите точки трябва да бъде с едно повече от броя на черните точки, т.е. за този стълб Б – Ч = 1. Оцветяваме точка А в черно и получаваме правилно оцветяване на Т + 1 на брой точки (след оцветяването на А в черно, в реда и в стълба Б – Ч = 0).
С аналогични разсъждения, ако в реда, който съдържа А имаме Б – Ч = –1, то и в стълба, който съдържа А трябва да имаме Б – Ч = –1 и тогава, ако оцветим А в бяло ще получим правилно оцветяване.
С това индукцията е завършена.