2-я Международная Жаутыковская олимпиада, 2006 год

Имеется куча из 100 камней. Разбиение этой кучи на $k$ новых куч назовем особым , если, во-первых, количества камней в разных кучах разные, и, во-вторых, при любом дальнейшем разбиении любой из этих куч на две новые среди новых $k+1$ куч полученного разбиения найдутся две кучи с одинаковым числом камней (любая куча состоит, по крайней мере, из одного камня).
а) Найдите наибольшее число $k$, при котором для данной кучи из 100 камней существует особое разбиение на $k$ куч.
б) Найдите наименьшее число $k$, при котором существует особое разбиение данной кучи на $k$ куч.

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

a)Ответ: $k=13$

Сначала покажем пример: 1,2,3,4,5,6,7,8,9,10,11,15,19. Не сложно убедится, что данный пример удовлетворяет всем условиям. Теперь докажем, что больше че за 13 нельзя. Допустим, можно разбить камни на 14 или больше кучек. Поскольку кол-во камней в разных кучках разное, общее кол-во камней не меньше чем

$$1+2+\dots+14=\frac{14\times15}{2}=105>100$$

Противоречие

b)Ответ:$k=10$

Сначала покажем пример: 1,3,5,...,19. Не сложно убедится, что данный пример подходит под условия. Пусть бы разбили 100 камней в кучи $S_1,S_2,\dots S_n$.  Допустим, что для некоторого $i$ выполняется неравенство: $S_i\geq 2i+1$. Тогда есть минимум $i$ способов разбить его на две кучки. Но кучек меньше чем $S_i$ есть только $i-1$. Следовательно, найдется разбиение $S_i$ после которого нет двух кучек с одинаковым количеством камней. Противоречие. Это означает, что для всех $i$ выполняется неравенство $S_i\leq 2i$. Следовательно:

$$100=S_1+S_2\dots+S_n\leq 2(1+2+\dots+n)=n\times (n+1)$$

откуда получим $n\leq 10 $