Индукция в комбинаторике

Покажем, что меньшего числа конфет может не хватить. На тот случай, если все участники решили поровну задач, число конфет необходимо сделать кратным 25. Пусть Представим себе, что 24 человека решили поровну, а 25-й решил меньше. Если каждому из первых 24 участников дать по конфет или еще меньше, то останутся лишние конфеты. Значит, каждому из них необходимо дать как минимум по конфете, откуда то есть и

Теперь докажем по индукции, что можно раздать участникам конфет так, чтобы каждый получил меньше конфет. База при очевидна: дадим единственному участнику 0 конфет.

Переход от к Пусть есть участников с самым большим результатом и, кроме них, еще участников, Менее успешным участникам по предположению индукции раздадим конфет (причём всем меньше чем по ). После этого останется

конфет, и мы раздадим их поровну «верхним» участникам. Каждый из них получит по конфет. Это число не меньше, чем поэтому больше того, что мы раздали каждому из остальных. Кроме того,

что и завершает переход.