На белой доске 5×5 петя закрасил какие-то клетки синим цветом, а какие-то – красным (каждым цветом закрашена хотя бы одна клетка). никакие две клетки красного и синего цвета не имеют общей стороны. какое наибольшее число клеток могло быть закрашено?
Обозначим буквой К красные клетки, а буквой С - синие. Наибольшее число закрашенных клеток (например, красных) равно 13. При этом получается 12 синих. Всего закрашено 25 клеток К С К С К С К С К С К С К С К С К С К С К С К С К
Или наоборот:
С К С К С К С К С К С К С К С К С К С К С К С К С
Получается 13 синих, 12 красных, а всего 25 закрашенных клеток.
Попробуем доказать по индукции. 5^(5x+1) + 4^(5x+2) + 3^(5x) = 5*5^(5x) + 16*4^(5x) + 3^(5x) При x = 0 будет 5*5^0 + 16*5^0 + 3^0 = 5 + 16 + 1 = 22 = 2*11 - делится на 11. Пусть при каком-то x это верно, докажем, что это верно и при x+1 5^(5x+5+1) + 4^(5x+5+2) + 3^(5x+5) = 5^(5x+6) + 4^(5x+7) + 3^(5x+5) = = 5^6*5^(5x) + 4^7*4^(5x) + 3^5*3^(5x) = 15625*5^(5x) + 16384*4^(5x) + 243*3^(5x) Вычтем из него нашу сумму 5*5^(5x) + 16*4^(5x) + 3^(5x), которая делится на 11, и проверим, делится ли на 11 разность. 15625*5^(5x) + 16384*4^(5x) + 243*3^(5x) - 5*5^(5x) - 16*4^(5x) - 3^(5x) = = 15620*5^(5x) + 16368*4^(5x) + 242*3^(5x) = = 11*1420*5^(5x) + 11*1488*4^(5x) + 11*22*3^(5x) Все три коэффициента делятся на 11, значит, и разность делится на 11, и следующий член последовательности 5^(5x+6) + 4^(5x+7) + 3^(5x+5) делится на 11.
Наибольшее число закрашенных клеток (например, красных) равно 13. При этом получается 12 синих. Всего закрашено 25 клеток
К С К С К
С К С К С
К С К С К
С К С К С
К С К С К
Или наоборот:
С К С К С
К С К С К
С К С К С
К С К С К
С К С К С
Получается 13 синих, 12 красных, а всего 25 закрашенных клеток.