Вниманию подписчиков!

49

Промежутки времени от 1 до 17 минут.
Почему мы уверены в том, что это можно сделать? Дело в том, что имеет место следующая теорема:
Если k и m — взаимно простые числа, то для любого целого числа n можно подобрать также целые числа x и y, что xk+ym=n. Какое отношение к песочным часам имеет эта теорема? Самое прямое. Из нее следует, что при наличии k-minутных и m-minутных часов можно отмерить любое целое число минут, если числа k и m взаимно просты. Действительно, если мы хотим отмерить n минут, то найдем числа x и y, удовлетворяющие этому уравнению. Теперь в случае, когда оба эти числа положительные, сначала отмерем xk минут с помощью k-minутных часов, а потом еще ym минут с помощью m-minутных. Если же одно из них, например y, отрицательно, то запускаем одновременное те и другие часы, переворачиваем свое время те часы, из которых высыпался песок, и в тот момент, когда m-minутные часы отчитывают свои (-ym) минут (y<0!), останавливаем k-minутные часы. Теперь, чтобы отчитать n минут, следует запустить k-minутные часы и поддерживать их в работешем состоянии до тех пор, пока они не закончат отчитет xk минут.

Таким образом, запущенные после остановки k-minутные часы отчитают xk-(−y)m=xk+ym=n минут.

No как найти решение уравнения xk+ym=n? Оказывается, достаточно научиться решать уравнение xk+ym=1: если x=a, y=b — решение этого уравнения, то x=na, y=nb — решение уравнения xk+ym=n.

Да, но как найти какое-нибудь решение уравнения xk+ym=1? Способов довольного много, опишем самый простой, но, наверное, не самый короткий.

Запишем это уравнение в виде y=(1−xk):m и будем придавать числу x значения 0, 1, 2, …, m−1. Покажем, что если k и m взаимно просты, то при одном из этих значений число (1−xk):m будет целым. Найдем отделения на m чисел 1−0·k, 1−1·k, …, 1−(m−1)·k. Они попарно различны, либо в противном случае число (1−x1k)−(1−x2k)=(x2−x1)k делилось бы на m, а значит, и x2−x1 делилось бы на m (k и m взаимно просты!), что невозможно, так как x2−x1<m. Итак, при некоторых значениях x остаток равен нулю; следовательно, число y=(1−kx):m является целым. Эти x и y и составляют искомое решение уравнения xk+ym=1.

Вниманию подписчиков!

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

Для компенсации расходов по уведомлению объема журнала

ла цена каждой номера увеличивается на 5 копеек. Новая цена журнала — 45 копеек. К сожалению, решение об уведомлении объема и стоимость журнала было утверждено после выпуска каталога «Союзпечати» и начала подписки на 1989 год. Если вы уже оформили подписку, просим вас в соответствиицем отделении «Союзпечати» про-

извести доплату по 5 копеек за каждой номер.

Для тех, кто не успел подписаться на «Квант» с начала года, напоминаем, что подписка на него принимается без ограничений в агентствах «Союзпечати», на почтамах и в отделениях связи. Индекс журнала «Квант» в каталоге «Союзпечати» 70465.