Loading [MathJax]/jax/output/SVG/jax.js

Математикадан облыстық олимпиада, 2015-2016 оқу жылы, 10 сынып


n қатардан және m бағаннан тұратын тіктөртбұрышты кесте берілген. Кестеде бірнеше шаршыны белгілеп, әр қатарда дәл k шаршы,ал әр бағанда дәл l шаршы белгіленген болатындай, барлық натурал (k,l) жұптарын табыңыз.
посмотреть в олимпиаде

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

пред. Правка 3   0
2 года 8 месяца назад #

Ответ: (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 каждый. Все условия при этом выполняются.

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

  2
4 года 2 месяца назад #

Из kl=mn не следует, что k=md,l=nd.

пред. Правка 2   0
2 года 8 месяца назад #

Вы правы.

  3
4 года 2 месяца назад #

Ответ: mn=kl и km,ln.

Количество отмеченных клеток равно ml=nkmn=kl=pq, где (p,q)=1. Тогда m=px,n=qx и k=py,l=qy.

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