В конце месяца все наместники Фараону платят собраный налог. У всех он одинаковый: 1 мешок золотых монет. Разведка донесла, что один наместник фальшивками расплатился. Фальшивые золотые монеты на 20г весят меньше нормальных монет. Зная вес монет, как определить кто лгун за одно взвешивание?
Определимся с условиями: 1. Все нормальные монеты по весу одинаковые 2. Все фальшивые легче на 20г 3. Есть N мешков, один из них фальшивый. Количество монет в мешке больше чем число мешков? Если да, то алгоритм прост: 1. Берем из первого мешка одну монету, из второго две монеты, из третьего три и так далее 2. Взвешиваем, вычисляем недостачу в граммах 3. Делим недостачу на 20 определяем номер мешка, в котором находятся фальшивые монеты Если количество монет в мешке меньше, чем количество мешков - задача получается гораздо интереснее UPDATE: Если количество монет в мешке на один мешьше чем количество мешков, то задача все равно решаема - из одного мешка не берем вообще ни одной монеты. Тогда если недостачи не будет, то фальшивый мешок тот, из которого не брали.
