В гномьем клане некоторые знакомы между собой. Каждый гном владеет некоторым количеством монет. Днём каждый гном узнаёт, сколько монет у каждого из его знакомых. Вечером он отдаёт по монете каждому из знакомых, кто днём был богаче него. Гном не может отдать больше, чем у него есть (например, нищий гном ничего не отдаёт). Если у гнома днём было меньше монет, чем количество знакомых богаче, чем он, то он сам решает, кому отдавать монеты. Докажите, что, начиная с какого-то дня, гномы прекратят передавать друг другу монеты.
Докажем требуемое утверждение индукцией по количеству гномов.
База — один гном; утверждение очевидно.
Шаг — пусть утверждение верно для любого клана из n гномов, докажем его для любого клана из n + 1 гномов.
Рассмотрим произвольный клан из n + 1 гномов и то, как они менялись монетами. Пусть aij — число монет у гнома номер i на в день номер j. Среди всех чисел aij есть максимальное — так как все aij натуральны и ограничены сверху суммарным количеством монет в клане. Пусть akp — одно из максимальных чисел. Тогда, начиная с дня номер p, гном номер k не будет никому давать монеты и ни у кого получать монеты. Действительно: гном номер k может отдать монеты, только если найдётся гном, у которого больше монет. А такого гнома никогда не найдётся из максимальности akp. Гном номер k не может получить монеты, потому что если ему кто-то отдаст монеты, то число монет у гнома номер k станет больше akp, что так же противоречит максимальности akp.
Начиная со дня номер p, будем рассматривать всех гномов, кроме гнома с номером k, как клан из n гномов. Это корректно, так как они не получают и не отдают монеты гному с номером k. По предположению индукции, начиная с какого-то дня, гномы в этом новом клане перестанут передавать друг другу монеты, что и требовалось доказать.