МАЛЫЙ МЕХМАТ МГУ

Кружок 6 класса

Занятие 6. Алгоритмы

1.

В трёх кучках лежит 11, 7 и 6 спичек соответственно. Разрешается перекладывать из одной кучки в другую столько спичек, сколько там уже есть. Как за три операции сравнять число спичек во всех кучках?

Решение

Решение. 11, 7, 6 → 4, 14, 6, → 4, 8, 12 → 8, 8, 8.

2.

В мешке 64 килограмма семечек. Как, пользуясь только чашечными весами без гирь, отвесить:

а)

1 килограмм семечек;

б)

23 килограмма семечек?

Решение

Решение.

а) Заметим, что мы можем разделить любую кучу семечек на таких весах пополам: будем пересыпать часть семечек с одной чаши весов на другую до тех пор, пока они не уравновесятся. Разделим таким способом 64 килограмма пополам. Получим две кучи по 32 кг. Одну из них отложим в сторону, а вторую опять разделим пополам. Так будем делать до тех пор, пока у нас не получатся две кучи по 1 кг каждая. Одна их них и есть искомая.

б) В процессе взвешиваний в пункте а мы получили кучи семечек весом 1, 2, 4, 8, 16 и 32 кг. Из них можно набрать 23 кг = 16 кг + 4 кг + 2 кг + 1 кг.

3.

Три человека со стиральной машиной хотят переправиться через реку. У них есть катер, который вмещает либо двух человек и стиральную машину, либо трёх человек. Беда в том, что стиральная машина тяжёлая, поэтому погрузить её в катер или вытащить из него можно только втроём. Смогут ли они переправиться?

Ответ Решение

Ответ. Смогут.

Решение. Все трое грузят машину в катер, и двое плывут с ней к другому берегу (оставив третьего дожидаться возвращения катера). Там один из них высаживается, а другой плывёт обратно за третьим (стиральную машину они пока не выгружают). Наконец, в катер на свободное место садится третий, и катер в последний раз пересекает реку. Теперь все трое оказались на другом берегу и могут выгрузить стиральную машину из катера.

4.

а)

На тропинке с интервалом в 10 см поставлены 10 отметок. По этим отметкам прыгает лягушонок, который умеет прыгать только на 3 отметки вперед или на 2 отметки назад и больше никак. Как ему проскакать по всем отметкам, побывав на каждой ровно один раз?

б)

А если отметок не 10, а 1000?

Решение

Решение.

а) Нетрудно заметить, что лягушонок может пропрыгать от отметки 1 до отметки 5, побывав на каждой из них ровно один раз: 1 – 4 – 2 – 5 – 3. С отметки 3 можно прыгнуть на отметку 6 и аналогичным образом побывать по одному разу на отметках от 6 до 10: 6 – 9 – 7 – 10 – 8.

б) Из пункта а лягушонок уже знает, как посетить все отметки от 1 до 10 (после чего он оказывается на отметке 8). С отметки 8 он может прыгнуть на отметку 11, а затем, прыгая так же, как в пункте а, побывать на всех отметках от 11 до 20 (после чего он окажется на отметке 18 и сможет прыгнуть на отметку 21, и т.д.). Повторив аналогичные действия еще 98 раз, лягушонок сможет посетить все отметки от 1 до 1000. Его путь при этом завершится на отметке под номером 998.

5.

Давным-давно в стране СССР имелись в обращении 3-копеечные и 5-копеечные монеты. Докажите, что можно было набрать любую сумму более 7 копеек только такими монетами.

Решение

Решение.

Первый способ.
Сначала заметим, что суммы в 8, 9 и 10 копеек набрать можно: 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5. Если добавить по одной трёхкопеечной монете к каждой из трёх сумм, то мы получим числа 11, 12 и 13 соответственно. Если ещё по одной — числа 14, 15 и 16, и так далее.

Теперь допустим, что нам назвали какую-то сумму, выраженную целым числом рублей. Как набрать эту сумму трёх- и пятикопеечными монетами? Поделим её на 3 с остатком. Если остаток 0, то требуемая сумма набирается одними трёхкопеечными монетами; чтобы узнать их количество, надо взять частное от деления нашего числа на 3. Если остаток 1, то такой же остаток при делении на 3 имеет число 10. Значит, если мы вычтем из нашего числа 10, то разность будет делиться на три. Теперь наша сумма представлена в виде «10 + что-то, что делится на три». Как набрать 10, мы уже знаем; как набрать что-то, что нацело делится на три, тоже знаем. Если остаток 2, то такой же остаток при делении на 3 имеет чсило 8. Значит, если мы вычтем из нашего числа 8, то разность будет делиться на три. Теперь наша сумма представлена в виде «8 + что-то, что делится на три». Как набрать 8, мы уже знаем; как набрать что-то, что нацело делится на три, тоже знаем.

Замечание. Обратите внимание, что 8, 9 и 10 — минимальные числа, которые имеют соответствующие остатки при делении на 3 и при этом больше 7. Именно поэтому мы можем набрать любое другое число, просто прибавив к одному из этих чисел несколько троек. Если бы мы научились набирать, к примеру, число 20, из этого ещё не следовало бы, что мы можем набрать число с тем же остатком при делении на 3, но меньшее его. Например, если мы набрали 20 как 5 + 5 + 5 + 5, то мы не сможем вычесть из этого представления 20 тройку, чтобы набрать 17 (потому что мы не можем взять отрицательное число монет). Именно поэтому хотя и можно набрать трёхкопеечными и пятикопеечными монетами число 10, но нель-зя такими монетами набрать число 7, имеющее тот же остаток при делении на 3.

Второй способ.
Заметим, что можно набрать суммы от 8 до 17 копеек включительно: 8 = 3 + 5; 9 = 3 + 3 + 3; 10 = 5 + 5; 11 = 3 + 3 + 5; 12 = 3 + 3 + 3 + 3; 13 = 3 + 5 + 5; 14 = 3 + 3 + 3 + 5; 15 = 5 + 5 + 5; 16 = 3 + 3 + 5 + 5; 17 = 3 + 3 + 3 + 3 + 5.

Заметим, что числа от 8 до 17 имеют все возможные последние цифры. Поэтому для любой большей суммы можно найти такое число от 8 до 17, у которого такая же последняя цифра, что и у этой суммы (а значит, разность нашей суммы и этого числа оканчивается на ноль). Например, для суммы в 84 копейки таким числом будет 14, а для суммы в 139 копеек таким числом будет 9. Таким образом, мы разложили требуемую сумму на два слагаемых: то, которое мы уже знаем, как оплатить трёх- и пятикопеечными монетами (это число от 8 до 17), и то, которое оканчивается на 0, то есть делится на 10. Раз число делится на 10, то оно делится и на 5, а значит, представимо в виде суммы нескольких пятёрок. Таким образом, мы можем набрать любую требуемую сумму из трёхкопеечных и пятикопеечных монет.

6.

Три жулика, каждый с двумя чемоданами, находятся на одном берегу реки, через которую они хотят переправиться. Есть трёхместная лодка, каждое место в ней может быть занято либо человеком, либо чемоданом. Никто из жуликов не доверит свой чемодан спутникам в своё отсутствие, но готов оставить чемоданы на безлюдном берегу. Смогут ли они переправиться?

Ответ Решение

Ответ. Смогут.

Решение. Обозначим жуликов буквами А, Б и В, а их чемоданы — буквами а, а, б, б, в, в соответственно. Река будет обозначаться «—», а лодка — буквой «Л». Слева от реки будет расположен один берег, а справа — другой.
АааБббВвв Л —
БббВвв — Л Ааа
АБббВвв Л — аа
ббвв — Л АааБВ
БббВвв Л — Ааа
Ввв — Л БббАаа
АБВвв Л — аабб
вв — Л АааБббВ
Ввв Л — АааБбб
— Л АааБббВвв

7.

а)

Программист Индусов работает с таблицей 2011×2013, в клетках которой произвольным образом расставлены числа 0 и 1. Он умеет за один шаг заменять одновременно все цифры в одном столбце или строке на ту цифру, которая там встречается чаще всего. Как ему сделать так, чтобы во всех клетках таблицы стояло одно и то же: только нули или только единицы?

б)

А сумеет ли Индусов добиться этого для таблицы 2012×2012?

Решение

Решение.

а) В каждой строке от 1-й до 2011-й заменим все значения на то, которое в данной строке встречается чаще. (Поскольку в каждой строке 2013 символов, единиц и нулей в ней не может быть поровну, а значит, одно из чисел встречается чаще, чем другое.) Таким способов Индусов получит 2011 строк, каждая из которых состоит либо из одних нулей, либо из одних единиц. Теперь посмотрим на столбцы: они все стали одинаковыми. Поскольку каждый столбец имеет нечётную высоту (2011), то либо нулей, либо единиц в нём больше. А поскольку все столбцы одинаковые, то либо в каждом из них больше нулей, либо в каждом из них больше единиц. Так что если теперь заменить все числа в каждом столбце на то, которое там встречается чаще, то вся таблица будет заполнена одинаковыми числами.

б) Не обязательно. Например, если первые 1006 строк заполнены единицами, а остальные — нулями, то Индусов не сможет изменить ни одно значение в таблице.

8.

Даны пять одинаковых по виду шаров массами 1000 г, 1001 г, 1002 г, 1004 г и 1007 г, а также весы со стрелкой, на которых можно взвесить произвольный груз (то есть узнать его массу). Определите шар массой 1000 г за три взвешивания.

Решение

Решение.

Сначала отметим, что если суммарный вес двух шаров оканчивается на 00, 01, 04 или 07 (важны именно две последние цифры), то один из этих шаров имеет вес 1000 г, а второй — соответственно, 1001, 1002, 1004 или 1007 г.

Взвесим два любых шара. Если их суммарный вес оканчивается на 00, 01, 04 или 07, то один из них весит 1000 г. Тогда вторым взвешиванием определим вес одного из этих шаров и узнаем, какой из них весит 1000 г. В этом случае нам хватило двух взвешиваний.

Если же общий вес первых двух шаров оканчивается не на 00, 01, 04 или 07, то среди них нет шара в 1000 г. Взвесим два из оставшихся трёх шаров. Если их суммарный вес оканчивается на 00, 01, 04 или 07, то один из них весит 1000 г, и тогда последним взвешиванием мы определим вес одного из этих шаров и узнаем, какой из них весит 1000 г. Если же и у этих двух шаров суммарный вес оканчивается не на 00, 01, 04 или 07, то среди них нет шара в 1000 г, и тогда массу 1000 г имеет пятый шар, который мы ещё ни разу не клали на весы.

9.

У Антона Евгеньевича работает четверо сотрудников: Дима, Женя, Миша и Стёпа. Каждый день он повышает зарплату на 1 рубль ровно троим (по своему выбору). Как Антону Евгеньевичу повышать зарплаты, чтобы в какой-то момент сделать их одинаковыми, если изначально у сотрудников такие зарплаты:

а)

Дима — 100 руб., Женя — 99 руб., Миша — 99 руб., Стёпа — 100 руб.?

б)

Дима — 1007 руб., Женя — 1006 руб., Миша — 1005 руб., Стёпа — 1008 руб.?

в)

Дима — 2025 руб., Женя — 1930 руб., Миша — 1857 руб., Стёпа — 1919 руб.?

г)

Дима — a руб., Женя — b руб., Миша — c руб., Стёпа — d руб.?

Решение

Решение.

а) 100, 99, 99, 100 → 101, 100, 100, 100 → 101, 101, 101, 101.

б) 1007, 1006, 1005, 1008 → 1010, 1009, 1008, 1008 → 1010, 1011, 1010, 1010 → 1011, 1011, 1011, 1011 (здесь при некоторых переходах зарплата повышается сразу на несколько рублей; это происходит за несколько дней).

в) 2025, 1930, 1857, 1919 → 2025, 2098, 2025, 2087 → 2098, 2098, 2098, 2160 → 2160, 2160, 2160, 2160.

г) Заметим, что наша цель — уравнять зарплаты. Поэтому неважно, каковы сами зарплаты, важно, какова разница между ними. Кроме того, повышая зарплату на один рубль троим сотрудникам, мы изменяем разницу между их зарплатами так же, как если бы мы понизили на рубль зарплату четвёртому. Поэтому последовательность ходов можно описать, указывая не тех, кому мы повысили зарплату, а того, кому на очередном ходу мы зарплату не повысили.

Теперь допустим, что a ≤ b ≤ c ≤ d. Чтобы уравнять их зарплаты, нам нужно будет «понизить» зарплаты каждого до уровня a. Это можно делать, например, в таком порядке: «понизить» зарплату d до уровня a, затем «понизить» зарплату c до уровня a и, наконец, «понизить» зарплату b до уровня a.