Математикадан 55-ші халықаралық олимпиада, 2014 жыл, Кейптаун

Кейп Таунның Банкі кез келген натурал $n$ саны үшін $\dfrac{1}{n}$ мәні бар тиындарды шығарады. Осындай тиындарының (мәндері бірдей болуы мүмкін) ең көп $99+\dfrac{1}{2}$ сомасы болатын шекті жиынтығы бар. Осы жиынтығын әрқайсысының сомасы 1-ден аспайтындай 100 немесе одан аз топқа бөлуге болатынын дәлелдеңдер.

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

Мы докажем результат не более чем для k − k/2k+1 с k группами. Сначала выполните следующее

оптимизации.

• Если какая-либо монета размера 1/2m появляется дважды, замените ее одной монетой размера 1/m.

• Если какая-либо монета размера 1/2m+1 появляется 2m + 1 раз, сгруппируйте ее в одну группу и

вводить вниз.

Применяйте эту операцию несколько раз, пока ее больше нельзя будет выполнить.

Теперь построим ящики B0, B1, ..., Bk−1. В ящик В0 положите любые монеты размера 1/2 (четко

существует не более одного). В остальные коробки Bm положите монеты размера 1/2m+1 и 1/2m+2 (максимум 2m+1 2m+2

2 м первого и максимум одного второго). Обратите внимание, что общий вес в коробке меньше 1. Наконец, сложите в стопку оставшиеся «легкие» монеты размером не более 1.

Затем просто бросайте монеты из кучки в коробки произвольно, кроме оговорки.

что ни один ящик не должен иметь вес, превышающий 1. Мы утверждаем, что при этом израсходуются все монеты в стопке.

Предположим, что нет, и что некоторое количество монет останется в куче, когда все коробки заполнены.

Тогда во всех ящиках должно быть не менее 1 − 1/2k+1, что означает общую сумму в ящиках.

строго больше, что является противоречием.

k(1-1/2k+1)>k-1/2

Замечание. Это дает более сильную оценку $k(1-1/2k+1)$, чем запрошенное $k-1/2$