2-ші халықаралық Жәутіков олимпиадасы, 2006 жыл

100 тастан тұратын үйме берілген. Осы үймені жаңа $k$ үймеге бөлуді ерекше дейміз, егер, біріншіден, әртүрлі үймедегі тастардың саны әртүрлі болса, және, екіншіден, ары қарай осы үймелердің кез келгенін екі үймеге бөлсек, пайда болған бөлудің жаңа $k+1$ үймесінің ішінен тас саны бірдей екі үйме табылса (әр үймеде кемінде бір тас бар).
а) Берілген 100 тастан тұратын үймені $k$ үймеге ерекше бөлуге болатындай $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 $