14-ші «Жібек жолы» математикалық олимпиадасы, 2014 жыл
Комментарий/решение:
Комментарии от администратора Комментарии от администратора №1. Ответ. 2n−1. Пример можно получить, если расставить монеты во все клетки самого левого столбца и самой верхней строки.
Решение. Занумеруем все столбцы (слева направо) и строки (снизу вверх) числами 1,2,…,n. Каждая клетка при этом будет иметь свои координаты (x,y) (номер столбца, номер строки).
Далее занумеруем монеты в таблице следующим образом: рассмотрим клетку (где есть монета) с наименьшей координатой y, если таких несколько, то также выбираем с наименьшей координатой x. Выбранная монета будет первой. Оставшиеся монеты нумеруем аналогичным образом. Пусть в таблице k монет с координатами (a1,b1),…,(ak,bk). Заметим, что для всех 1≤i≤k−1 выполнено bi≤bi+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. То есть ai≤ai+1 и ai+bi<ai+1+bi+1.
Нетрудно видеть, что 2≤ai+bi≤2n. Так как ai+bi строго возрастает, то в ней не более чем 2n−1 членов.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.