У каждого жителя сказочного королевства есть несколько (может быть 0) монет. Жители дружат между собой. Каждый день один из жителей отдает монету своему другу. Докажите, что этот процесс не может длиться бесконечно долго.

Мы покажем, что каждый допустимый ход (передача монеты от одного жителя своему другу) приводит к «понижению» некоей величины, определённой на состоянии системы, а поскольку число возможных состояаний конечно, процесс не может длиться бесконечно. Ниже приведём подробное рассуждение. Допустим, в королевстве ровно n жителей, состояние которого задаётся вектором (a₁, a₂, …, aₙ), где aᵢ – число монет у i–го жителя. (Обратите внимание, что общее число монет остаётся постоянным, так как монеты не создаются и не уничтожаются.) При этом жители соединены связями дружбы (эта связь симметрична, однако у...