Математикадан облыстық олимпиада, 2015-2016 оқу жылы, 10 сынып
Комментарий/решение:
Ответ: (md,nd), где d – общий делитель m и n.
Решение. Докажем необходимость. Общее число отмеченных клеток равно nk=ml=>kl=mn, откуда k=md,l=nd.
Докажем достаточность. В первых l строках отметим первые k клеток, в строках с l+1 по 2l отметим клетки с k+1 по 2k, и т.д. Этот процесс закончится через d шагов, т.к. m=kd,n=ld, мы будем иметь d прямоугольников из отмеченных клеток размерами l×k каждый. Все условия при этом выполняются.
Замечание. В этом решении ошибка, см. ниже.
Ответ: mn=kl и k≤m,l≤n.
Количество отмеченных клеток равно ml=nk⟹mn=kl=pq, где (p,q)=1. Тогда m=px,n=qx и k=py,l=qy.
Достаточно заполнить квадрат x×x так, чтобы в каждой строке и в каждом столбце было ровно y отмеченных клеток, а далее сделать "прямоугольник" из таких квадратов. Это легко сделать, например отметим первые y клеток 1-го столбца, потом следующие y клеток 2-го столбца и т.д. Для x=4 и y=3 это выглядит следующим образом:
◼◻◼◼
◼◼◻◼
◼◼◼◻
◻◼◼◼
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.