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

14-ші «Жібек жолы» математикалық олимпиадасы, 2014 жыл


Әр тиын, калған басқа тиындарға қарағанда, бір уақытта төмен және оң жағында болмайтындай етіп, өлшемі n×n болатын тақтаның шаршыларында (тақтаның әр шаршысында бірден көп емес) ең көп дегенде қанша тиын қоюға болады? ( Ильясов С. )
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. 2n1. Пример можно получить, если расставить монеты во все клетки самого левого столбца и самой верхней строки.
Решение. Занумеруем все столбцы (слева направо) и строки (снизу вверх) числами 1,2,,n. Каждая клетка при этом будет иметь свои координаты (x,y) (номер столбца, номер строки).
Далее занумеруем монеты в таблице следующим образом: рассмотрим клетку (где есть монета) с наименьшей координатой y, если таких несколько, то также выбираем с наименьшей координатой x. Выбранная монета будет первой. Оставшиеся монеты нумеруем аналогичным образом. Пусть в таблице k монет с координатами (a1,b1),,(ak,bk). Заметим, что для всех 1ik1 выполнено bibi+1.
Если для некоторого i, bi=bi+1, то монеты с номерами i,i+1 лежат в одной строке. Значит, ai<ai+1 и ai+bi<ai+1+bi+1.
Если же bi<bi+1, то неравенство ai>ai+1 невозможно так как иначе монета i будет одновременно правее и ниже чем монета i+1. То есть aiai+1 и ai+bi<ai+1+bi+1.
Нетрудно видеть, что 2ai+bi2n. Так как ai+bi строго возрастает, то в ней не более чем 2n1 членов.