Ре­ше­ние. До­ка­жем тре­бу­е­мое утвер­жде­ние ин­дук­ци­ей по ко­ли­че­ству гно­мов.

База  — один гном; утвер­жде­ние оче­вид­но.

Шаг  — пусть утвер­жде­ние верно для лю­бо­го клана из n гно­мов, до­ка­жем его для лю­бо­го клана из n + 1 гно­мов.

Рас­смот­рим про­из­воль­ный клан из n + 1 гно­мов и то, как они ме­ня­лись мо­не­та­ми. Пусть a_ij  — число монет у гнома номер i на в день номер j. Среди всех чисел a_ij есть мак­си­маль­ное  — так как все a_ij на­ту­раль­ны и огра­ни­че­ны свер­ху сум­мар­ным ко­ли­че­ством монет в клане. Пусть a_kp  — одно из мак­си­маль­ных чисел. Тогда, на­чи­ная с дня номер p, гном номер k не будет ни­ко­му да­вать мо­не­ты и ни у кого по­лу­чать мо­не­ты. Дей­стви­тель­но: гном номер k может от­дать мо­не­ты, толь­ко если найдётся гном, у ко­то­ро­го боль­ше монет. А та­ко­го гнома ни­ко­гда не найдётся из мак­си­маль­но­сти a_kp. Гном номер k не может по­лу­чить мо­не­ты, по­то­му что если ему кто-то от­даст мо­не­ты, то число монет у гнома номер k ста­нет боль­ше a_kp, что так же про­ти­во­ре­чит мак­си­маль­но­сти a_kp.

На­чи­ная со дня номер p, будем рас­смат­ри­вать всех гно­мов, кроме гнома с но­ме­ром k, как клан из n гно­мов. Это кор­рект­но, так как они не по­лу­ча­ют и не от­да­ют мо­не­ты гному с но­ме­ром k. По пред­по­ло­же­нию ин­дук­ции, на­чи­ная с ка­ко­го-то дня, гномы в этом новом клане пе­ре­ста­нут пе­ре­да­вать друг другу мо­не­ты, что и тре­бо­ва­лось до­ка­зать.