Задачи на алгоритм Евклида (2)

 2016-11-04 19:00:00      

Назад ко всем статьям

1. Докажите, что два соседних числа Фибоначчи всегда взаимно просты.

 

2. а) В ведро налили 12 литров молока. Пользуясь лишь сосудами в 5 и 7 литров, разделите молоко на две равные части.

 

б) Решите общую задачу: при каких a и b можно разделить пополам литров молока, пользуясь лишь сосудами в a литров, b литров и (a + b) литров?

 

За одно переливание из одного сосуда в другой можно вылить всё, что там есть, или долить второй сосуд до верха. 

 

3. Есть шоколадка в форме равностороннего треугольника со стороной n, разделённая бороздками на равносторонние треугольники со стороной 1. Играют двое. За ход можно отломать от шоколадки треугольный кусок вдоль бороздки, съесть его, а остаток передать противнику. Тот, кто получит последний кусок – треугольник со стороной 1, – победитель. Для каждого n выясните, кто из играющих может всегда выигрывать, как бы не играл противник? 

 

4. k вершин правильного n-угольника закрашены. Закраска называется почти равномерной, если для любого натурального m верно следующее условие: если M1 — множество m расположенных подряд вершин и M2 – другое такое множество, то количество закрашенных вершин в M1 отличается от количества закрашенных вершин в M2 не больше, чем на 1. Доказать, что для любых натуральных n и k <= n почти равномерная закраска существует и что она единственна с точностью до поворотов закрашенного множества.

 

5. Периоды двух последовательностей – m и n – взаимно простые числа.

Какова максимальная длина начального куска, который может у них совпадать? 

 

6. Теорема Ламе. Пусть число m1 в десятичной системе счисления записывается при помощи t цифр. Докажите, что при любом m0 число шагов k в алгоритме Евклида для чисел m0 и m1 удовлетворяет неравенству k <= 5t.