Имеются два пустых флакона: ** 5 капель и ** 7. Рядом источник воды. Никаких других...

0 голосов
50 просмотров
Имеются два пустых флакона: на 5 капель и на 7. Рядом источник воды. Никаких других приспособлений нет. За какое наименьшее кол-во ходов можно отметить три капли? Доказать.

Информатика (42 баллов) | 50 просмотров
Дан 1 ответ
0 голосов

Если один ход это одно переливание, то ответ 2:
1. перельем из 5 в 7
2. перельем из полной 5 в 7 недостающие 2 капли, получим 3

нужно доказать что нет ответа с числом 1. Для этого просто рассмотреть возможные варианты того что получится: 5 капель, 7 капель, (7-5) капель. Они не равны трем.

В общем случае, поскольку оперируем остатками от деления чисел 7*k на 5 и 5*k на 7, то нужно разложить наш ответ в сумму таких остатков, и посмотреть длину суммы.

(3.8k баллов)