Қалалық Жәутіков олимпиадасы 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$, которые удовлетворяют обоим условиям, что доказывает возможность раскраски прямоугольной таблицы.