55-я Международная Математическая OлимпиадаЮжно-Африканская Республика, Кейптаун, 2014 год

Банк Кейптауна выпускает монеты номиналом $\dfrac{1}{n}$ для каждого целого положительного числа $n$. Дан конечный набор таких монет, сумма номиналов которых не превосходит $99+\dfrac{1}{2}$ (номиналы монет не обязательно различны). Докажите, что все монеты этого набора можно разбить на 100 или меньшее число групп так, чтобы сумма номиналов монет в каждой группе не превышала 1.

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

Мы докажем результат не более чем для 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$