van писал(а):
Клетки поля 5x5 раскрашены в 2 цвета, доказать, что найдутся такие 2 строки и 2 столбца, что на их пересечении все клетки будут одного цвета.
возможно не самое лучшее, но смог наскретсти такое доказательство.
Из условия задачи следует, что необходимо найти четыре такие клетки одного цвета которые были бы вершинами некоторого прямоугольника со сторонами параллельными сторонам квадрата(1).
Узнаем сколько нужно клеток одного цвета, что бы они удовлетворяли критерию (1). Очевидно их должно быть не меньше 4-ёх. Осталось узнать какое количество клеток должно быть достаточно что бы всегда среди них можно было найти те 4-ыре которые удовлетворяли бы критерию (1). Самая "туманная" часть доказательства: будем системно располагать клетки одного цвета по доске так что бы ни одна после закраски не отвечала критерию (1). Итого получиться картинка ниже
XO
XOO
O
XO
XO
OO
XO
X
OOO
XO
OOOO
X
очевидно, что если закрасить ещё одну любую клетку в
X, то выполняется критерий (1). Т. е. при наличии 9-и клеток одного цвета можно провести 2 вертикальные и горизонтальные прямые, на пересечении которых клетки будут иметь одинаковый цвет.
Так как всего клеток 25, и вариантов закраски 2, то всегда клеток одного из цветов будет больше или равно 9(очевидный факт(если их обеих меньше 9-и, то сумма их количества меньше 18, а их 25 по условию)). Чтд.
Вопрос почему маленьких детей качают в коляске и им от этого становиться спокойней?
Последний раз редактировалось: OceanReBorn (20 июл 2008, 12:57); всего редактировалось: 1 раз
Добавлено:
Новая тема
Ответить