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

Докажем индукцией по , что можно так выкладывать гири.

База: . Для одной гири, очевидно, верно. Кладем ее на ту чашу, которая должна перевесить.

Переход: Предположим, что задача доказана для . Докажем для . Назовем алгоритмом заранее известную последовательность перевешивания чаш, в соответствии с которой мы должны выкладывать гири. Первым шагом положим гирю веса 1 на чашу, которая должна перевесить на первом шаге алгоритма.

Теперь представим, что весы сейчас находятся в равновесии (забудем про гирю веса 1), а веса всех оставшихся гирь деленные на 2, то есть 1, 2, 4, …, . Будем выкладывать гири по предположению индукции в нужном порядке, в соответствии с оставшимся алгоритмом (его первый шаг мы уже выполнили).

Докажем, что получающаяся последовательность перевешивания чаш (вспомнили про гирю веса 1 и вернули все исходные веса оставшихся гирь) соответствует алгоритму, то есть если чаша перевешивала, когда мы использовали оставшиеся гири и считали их вес вдвое меньшим, то чаша будет перевешивать и в реальной ситуации. Предположим, что когда мы вспомнили про первую гирю и вернули веса оставшимся, чаша, которая перевешивала, перестала перевешивать (или весы оказались в равновесии, или перевешивает другая чаша). Когда мы вернули веса (обратно удвоили) последовательность перевешивания чаш не изменилась. То есть чаша перестала перевешивать тогда, когда на одну из чаш добавили гирю веса 1. Но такого не может быть, так как до добавления этой гири веса двух чаш были четными (используются только гири весов 2, 4, …, ), то есть отличались между собой хотя бы на 2, тогда после добавления гири веса 1 весы не могли прийти в равновесие, а тем более начать перевешивать другая чаша.

Следовательно, выложили гири в соответствии с алгоритмом. Переход доказан.