Городская Жаутыковская олимпиада, 9 класс, 2011 год

Можно ли все клетки какой-нибудь прямоугольной таблицы покрасить в белый и черный цвета так, чтобы белых и черных клеток было поровну, а в каждой строке и в каждом столбце было более 3/4 клеток одного цвета?

Комментарий/решение

У нас есть два условия:

1. Общее количество клеток каждого цвета должно быть одинаковым: \( \frac{mn}{2} = x + y \) где \( x \) - количество клеток одного цвета, \( y \) - количество клеток другого цвета.

2. В каждой строке и каждом столбце должно быть более \( \frac{3}{4} \) клеток одного цвета. Это означает, что в каждой строке должно быть не менее \( \frac{3}{4} \times n \) клеток одного цвета, и в каждом столбце не менее \( \frac{3}{4} \times m \) клеток одного цвета.

Рассмотрим первое условие:

1. \( \frac{mn}{2} = x + y \) это первое условие. Мы можем выразить одну переменную через другую. Пусть \( x = \frac{mn}{2} - y \). Тогда у нас получится \( \frac{mn}{2} = \frac{mn}{2} - y + y \). Упростим это и получим \( 0 = 0 \) что верно для любых значений \( x \) и \( y \). Таким образом первое условие выполнено.

Теперь рассмотрим второе условие:

2. В каждой строке должно быть не менее \( \frac{3}{4} \times n \) клеток одного цвета. Это означает, что \( x \geq \frac{3}{4} \times n \). Подставим \( x = \frac{mn}{2} - y \) и рассмотрим неравенство: \( \frac{mn}{2} - y \geq \frac{3}{4} \times n \). Это неравенство можно решить относительно \( y \) и получить \( y \leq \frac{mn}{2} - \frac{3}{4} \times n \).

Аналогично для столбцов: \( x \geq \frac{3}{4} \times m \). Подставим \( x = \frac{mn}{2} - y \) и рассмотрим неравенство: \( \frac{mn}{2} - y \geq \frac{3}{4} \times m \). Это неравенство можно решить относительно \( y \) и получить \( y \leq \frac{mn}{2} - \frac{3}{4} \times m \).

Теперь у нас есть неравенства для \( x \) и \( y \). Чтобы обеспечить выполнение обоих неравенств, нужно выбрать значения \( m \) и \( n \), которые удовлетворяют этим неравенствам.

Таким образом, мы можем найти такие значения \( m \) и \( n \), которые удовлетворяют обоим условиям, что доказывает возможность раскраски прямоугольной таблицы.