Question

Кощей подарил Бабе Яге двое песочных часов: одни на p минут, а другие - на q минут. Числа p и q - целые. Оказалось, что НОД(p;q) = 1. Правда ли, что Баба Яга может отмерить с их помощью любое количество минут (целое), если она имеет право переворачивать часы только тогда, когда песок из них полностью высыпется. (Засекать отмериваемое время Баба Яга может в любой момент, не обязательно при первом переворачивании часов)

Answer 1

Это правда

Любые два целых взаимно-простых (то есть те, для которых НОД = 1) числа p и q удовлетворяют свойству: существуют такие целые положительные k и n, что kp-nq=1. Тогда в правой части последнего равенства можно получить любое целое положительное число, умножая равенство на это число и Баба Яга может отмерить любое целое число минут

Answer 2

Да, Баба Яга может отмерить любое количество минут (целое число) с помощью данных песочных часов, при условии, что у неё есть право переворачивать часы только тогда, когда песок из них полностью высыпется.

Это возможно потому, что НОД(p;q) = 1, что означает, что числа p и q являются взаимно простыми. Когда два числа взаимно просты, это означает, что их наибольший общий делитель (НОД) равен 1, и у них нет общих делителей, кроме 1.

Для решения этой задачи, давайте рассмотрим пример:

Пусть у нас есть два песочных часа на 7 минут и 11 минут, соответственно. НОД(7;11) = 1, что означает, что у них нет общих делителей, кроме 1.

Теперь, допустим, Баба Яга перевернула оба часа одновременно. Через 7 минут песок в первом часе закончится, и она перевернет только первый час. Когда песок во втором часе закончится через 4 минуты (11 - 7), она перевернет только второй час.

На этом этапе прошло 11 минут. Затем она продолжит смотреть только второй час. Когда песок во втором часе закончится через еще 7 минут, она перевернет только второй час.

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

В общем случае, поскольку p и q являются взаимно простыми числами, Баба Яга сможет отмерить любое целое количество минут, используя только эти два песочных часа и правила переворачивания.