Областная олимпиада по математике, 2016 год, 10 класс

Дана прямоугольная таблица, в которой $n$ строк и $m$ столбцов. Найдите все такие пары натуральных чисел $(k,l)$, что в таблице можно отметить несколько клеток таким образом, чтобы в каждой строке было отмечено ровно $k$ клеток, а в каждом столбце — ровно $l$ клеток.

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

Ответ: $(\frac m d, \frac n d)$, где $d$ – общий делитель $m$ и $n$.

Решение. Докажем необходимость. Общее число отмеченных клеток равно $nk=ml=>\frac k l=\frac m n$, откуда $k=\frac m d,l=\frac n d$.

Докажем достаточность. В первых $l$ строках отметим первые $k$ клеток, в строках с $l+1$ по $2l$ отметим клетки с $k+1$ по $2k$, и т.д. Этот процесс закончится через $d$ шагов, т.к. $m=kd,n=ld$, мы будем иметь $d$ прямоугольников из отмеченных клеток размерами $l×k$ каждый. Все условия при этом выполняются.

Замечание. В этом решении ошибка, см. ниже.

Из $\frac{k}{l}=\frac{m}{n}$ не следует, что $k=\frac{m}{d},l=\frac{n}{d}.$

Вы правы.

Ответ: $\dfrac{m}{n}=\dfrac{k}{l}$ и $k\le m,l\le n.$

Количество отмеченных клеток равно $ml=nk\implies \dfrac{m}{n}=\dfrac{k}{l}=\dfrac{p}{q},$ где $(p,q)=1.$ Тогда $m=px,n=qx$ и $k=py,l=qy.$

Достаточно заполнить квадрат $x\times x$ так, чтобы в каждой строке и в каждом столбце было ровно $y$ отмеченных клеток, а далее сделать "прямоугольник" из таких квадратов. Это легко сделать, например отметим первые $y$ клеток 1-го столбца, потом следующие $y$ клеток 2-го столбца и т.д. Для $x=4$ и $y=3$ это выглядит следующим образом:

$$\blacksquare\square\blacksquare\blacksquare$$

$$\blacksquare\blacksquare\square\blacksquare$$

$$\blacksquare\blacksquare\blacksquare\square$$

$$\square\blacksquare\blacksquare\blacksquare$$