Докажите, что на шахматной доске, где каждая клетка окрашена в черный или белый цвет в случайном порядке, всегда можно

Докажите, что на шахматной доске, где каждая клетка окрашена в черный или белый цвет в случайном порядке, всегда можно найти группу клеток, образующих прямоугольник такой, что угловые клетки разного цвета.
Akula_9332

Akula_9332

Конечно! Для того чтобы доказать данное утверждение, использовать будем метод доказательства от противного. Предположим, что на шахматной доске невозможно найти группу клеток, образующую прямоугольник, у которого угловые клетки будут разного цвета.

Рассмотрим случай, когда хотя бы одна из сторон прямоугольника состоит из нечетного числа клеток. Без потери общности, предположим, что это сторона, идущая по горизонтали. Тогда в этой стороне должны присутствовать как клетки черного, так и белого цвета. Пусть первая клетка этой строки – черная. Тогда каждая чередующаяся по цвету клетка в этой строке также будет иметь черный цвет. Следовательно, когда мы доходим до последней клетки этой строки, она также должна быть черной. Но тогда у нас должна быть на одну черную клетку больше, чем на белую, что противоречит условию. Полученное противоречие говорит о том, что предположение о невозможности такой группы клеток противоречит действительности.

Теперь рассмотрим случай, когда все стороны прямоугольника состоят из четного числа клеток. Предположим, что клетка в левом верхнем углу доски — черная. Тогда в первой строке должно быть четное число клеток, иначе клетка в правом верхнем углу будет черной, что противоречит условию. Аналогично, в первом столбце должно быть четное число клеток. Рассмотрим теперь первые две строки и первые два столбца. Получим четыре клетки, и по условию они обязаны быть одного цвета. Допустим, что они все белые. Тогда добавляя к этим двум строкам и двум столбцам по одной клетке справа и снизу, мы не сможем сохранить одноцветность. Следовательно, в этой группе должна быть хотя бы одна черная клетка. Тогда возникает две ситуации: или первый столбец содержит две черные клетки, или первая строка содержит две черные клетки. В обоих случаях у нас образуется прямоугольник с угловыми клетками разного цвета. Это противоречит условию.

Таким образом, в обоих случаях мы приходим к противоречию, что доказывает наше утверждение. На шахматной доске, где каждая клетка окрашена в черный или белый цвет в случайном порядке, всегда можно найти группу клеток, образующих прямоугольник такой, что угловые клетки будут разного цвета.
Знаешь ответ?
Задать вопрос
Привет!
hello