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

Докажем индукцией по

База для Возьмём две монетки и сравним на двух весах. Если показания одинаковые, то мы уже определили фальшивую монету, так как одни из этих весов точно рабочие. Действительно, если на обоих весах монеты равны, то третья — фальшивая. Если, не умаляя общности, на обоих весах первая монета легче, то она фальшивая.

Если же показания оказались разными, то какие-то из этих весов сломаны, а значит оставшиеся весы, которые мы не трогали, точно рабочие, взвесим на них любые две монетки и определим фальшивую так же, как в прошлом случае.

Докажем переход. Разделим монет на три кучи по монет в каждой. Возьмём две кучи и сравним их массы на двух весах.

Если показания разные, третьи весы точно рабочие. Далее работаем только с ними. Доказывая базу, мы поняли, что одно взвешивание на рабочих весах позволит определить кучу с фальшивой монетой. Поэтому сравним любые две кучи на третьих весах, определим кучу с фальшивой монетой, разделим её на три кучи по монет и продолжим делать то же самое с полученными кучами. В этом случае мы сделаем взвешиваний.

Предположим, что показания разные. По рассуждениям из базы ясно, что такая ситуация даёт нам понять, какая из кучек содержит фальшивую монету. Заметим, что теперь у нас монет и взвешивания, то мы можем использовать предположение. Что и требовалось.