Обобщённая задача о фальшивых монетах

Имеются N мешков и в каждом из них достаточное количество монет. Все мешки, кроме одного, содержат одинаковые «нормальные» монеты, в одном же мешке все монеты фальшивые. Известен вес нормальной монеты и известно, что фальшивая монета на 1 грамм легче нормальной. Требуется при помощи одного взвешивания на весах с разновесками обнаружить мешок с фальшивыми монетами.

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

Пусть имеются N мешков и в каждом достаточное количество монет. Имеются монеты разных сортов, но в каждом мешке содержатся монеты только одного сорта. Количество мешков с монетами данного сорта произвольное, и нам оно неизвестно. Монеты разных сортов отличаются друг от друга по весу, причём на целое число граммов. Вес монеты каждого сорта нам известен. Требуется при помощи одного взвешивания на весах с разновесками определить, к какому сорту принадлежат монеты в каждом мешке.

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

Перенумеруем последовательно мешки от 0 до N – 1. Обозначим вес самой лёгкой монеты через m. Пусть мешок под номером j содержит монеты веса m + ?j, то есть ?j определяет сорт монеты в j-м мешке. Пусть в зависимости от сорта монеты величины ? могут принимать (целые) значения 0, 1, 2, , меньшие k, то есть количество сортов монет равно k.