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

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

Занятие 18 (19 марта 2016 года). Алгоритмы

0.

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

0.

Губке Бобу срочно нужно налить из водопроводного крана 6 л воды. Но он имеет лишь два сосуда: 5-литровый и 7-литровый. Как ему это сделать?

1.

Трое учеников пошли на рыбалку, взяв с собой лодку, выдерживающую нагрузку до 100 кг. Как перебраться ученикам с берега реки на остров, если их массы равны 40 кг, 50 кг, 70 кг?

2.

В подвале лаборатории растут мандрагоры и имеется неограниченный запас мандрагорового экстракта. Как при помощи мензурок объёмом 5 и 7 миллилитров отмерить 4 миллилитра мандрагорового экстракта? Но берегитесь! Если ни на одном из этапов ни в одной из мензурок не окажется ровно 3 миллилитра экстракта, мандрагоры закатят истерику и криками разрушат лабораторию!

Решение

Решение. 0 0, 5 0, 0 5, 5 5, 3 7, 3 0, 0 3, 5 3, 1 7, 1 0, 0 1, 5 1, 0 6, 5 6, 4 7 (первое число - это сколько сейчас налито в 5-миллилитровую мензурку, второе - сколько налито в 7-миллилитровую)

3.

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

4.

На камнях сидит шесть лягушек (как на картинке). Лягушки-мальчики хотят пересесть на камни, где сидят лягушки-девочки, а лягушки-девочки хотят пересесть на камни, где сидят лягушки-мальчики. Каждая лягушка может прыгнуть либо на соседний камень (если он свободен), либо перепрыгнуть на камень сразу за соседней лягушкой (если он свободен). Как лягушкам поменяться местами?

5.

Решите предыдущую задачу при дополнительном условии: лягушки не могут прыгать назад, только вперёд!
Эту задачу можно решать, например, вот тут.

6.

Шли два маляра, навстречу — еще двое. У каждого руки испачканы своей краской, и никому не хочется пачкаться чужой. Маляры хотят поздороваться друг с другом (каждый из первой пары с каждым из второй и наоборот) рукопожатием, но на всех есть только две перчатки. Как им можно решить эту проблему? Перчатки не выворачиваются.

Решение

Решение. Пусть есть маляры 1 и 2 и маляры А и Б. 1 надевает обе перчатки друг на друга и здоровается с А. Потом снимает верхнюю и здоровается с Б. 2 надевает снятую перчатку и сдоровается с А. Потом надевает ту, которая сейчас на 1, и здоровается с Б.

7.

Семья супергероев ночью подошла к мосту. Бабушка-Молния может перейти его за 1 минуту, Железный Малыш — за 2 минуты, Криптонитовая Мама — за 5 минут, а Папа-Енот — за 10 минут. У них есть один фонарик. Мост выдерживает только двоих. Как им перейти мост за 17 минут? (Если переходят двое, то они идут с меньшей из их скоростей. Двигаться по мосту без фонарика нельзя. Светить издали нельзя. Носить друг друга на руках нельзя. Летать нельзя.)

Решение

Решение. Сначала переправляются Бабушка и Малыш, Бабушка возвращается. Потом идут вместе Мама и Папа, Малыш возвращается. Бабушка и Малыш снова переправляются. final:

Дополнительные задачи

8.

Есть 10-этажное здание. Есть обезьянка. У обезьянки есть два кокоса. Она может залезть на любой этаж и скинуть один кокос. Если этаж высокий – кокос разобьется и его нельзя будет больше кидать. Как, потратив не больше 4 бросков, гарантированно установить, начиная с какого этажа кокосы начинают разбиваться?

Решение

Решение. Сначала надо кинуть кокос с 4 этажа. Если не разбился, то с 7. Если не разбился, то с 9. Если не разбился, с 10 (мы подразумеваем, что возможна ситуация, когда кокосы вообще не разбиваются).

9.

У императора Палпатина работает 10 сотрудников. Каждый месяц император повышает зарплату на 1 рубль ровно девятерым (по своему выбору). Как Палпатину повышать зарплаты, чтобы сделать их одинаковыми? (Зарплата - целое число рублей.)

Решение

Решение. Для начала можно предложить решить эту задачу для конкретных зарплат: 1,2,3,4,….,10 рублей. После этого станет понятней идея решения.
Тот, кому не добавили рубль, относительно других сотрудников этот рубль теряет. Не будем доплачивать сотруднику с самой большой зарплатой до тех пор, пока его зарплата не сравняется с той, которая была самой маленькой (если сотрудников с наибольшей зарплатой - несколько, то выберем любого из них). Таким образом, наименьшую зарплату будут иметь, по крайней мере, двое сотрудников. Затем, снова выберем сотрудника с самой большой зарплатой и не будем ему доплачивать, пока его зарплата не сравняется с той, которая была самой маленькой, и получим не менее трех сотрудников с одинаковой зарплатой. Проделав такую операцию не более девяти раз, Палпатин сможет уравнять все зарплаты.

10.

Неуловимый Джо никогда не проигрывает на рулетке больше четырех раз подряд и никогда не ставит больше 10 долларов. Как ему выиграть 1000 долларов? (В случае выигрыша на рулетке возвращается удвоенная ставка; вначале Джо имеет 100 долларов.)

Решение

Решение. Пусть Джо поставит вначале 50 центов. Если выиграет, пусть он скажет "хорошо" и снова поставит 50 центов. Если проиграет, то в следующей ставке он ставит 1 доллар. Если он выигрывает, то его выигрыш покроет предыдущий проигрыш, и по сумме двух ставок он выиграет 50 центов. После этого пусть Джо снова скажет "хорошо" и в новой ставке ставит 50 центов. Если он проиграет и во второй раз, в третий раз он поставит 2 доллара, чтобы в случае выигрыша покрыть предыдущие проигрыши. Если проигрывает в третий раз, то в четвертый раз ставит 4 доллара, если проигрывает и в четвертый, то в пятый раз ставит 8 долларов. По условию он не проигрывает пяти раз подряд, значит играя таким образом до первого выигрыша, он заработает 50 центов не более, чем за 5 ставок. После этого он скажет "хорошо" и будет ставить также, как вначале. Итак, после 2000 "хорошо" Джо выиграет 1000 долларов. Для этого ему потребуется сделать не более 10000 ставок.