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

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

Руководители Екатерина и Евгений Адищевы
2006/2007 учебный год

Листок 21. Алгоритмы

0.
Три ёжика делили три кусочка сыра массами 5 г, 8 г и 11 г. Лиса стала им помогать. Она может от любых двух кусочков одновременно отрезать и съесть по 1 г сыра. Сможет ли лиса оставить ёжикам равные кусочки сыра?
1.
Квадрат 8×8 раскрашен в два цвета: черный и белый (произвольным образом, но строго по квадратикам 1×1). Можно любой прямоугольник 1×3 перекрашивать в преобладающий в нем цвет. Доказать, что такими операциями можно сделать весь квадрат одноцветным.
2.
Крестьянину надо перевезти через речку волка, козу и капусту. Лодка вмещает одного человека, а с ним либо волка, либо козу, либо капусту. Если без присмотра оставить козу и волка, волк съест козу. Если без присмотра оставить капусту и козу, коза съест капусту. Как крестьянину перевезти свой груз через речку?
3.
Вася загадал число от 1 до N. Петя задает ему вопросы, на которые тот может отвечать «да» или «нет». Может ли Петя отгадать число, если N=15, задав a) 4 вопроса; b) 3 вопроса; c*) какое минимальное число вопросов должен задать Петя, чтобы наверняка отгадать Васино число, если N=65535?
4.
Первоначально на доске написано натуральное число A. Разрешается прибавить к нему один из его делителей, отличных от него самого и единицы. С полученным числом разрешается проделать аналогичную операцию, и т. д.
a)
Докажите, что для любого составного числа A, на доске будут появляться только составные числа.
b)
Докажите, что из числа A=4 можно с помощью таких операций прийти к любому наперёд заданному составному числу.
5.
На столе стоит 128 стаканов с водой. Разрешается взять любые два стакана и уравнять в них количества воды, перелив часть воды из одного стакана в другой. Докажите, что с помощью таких операций можно добиться того, чтобы во всех стаканах было поровну воды.
6.
На консультации было 20 школьников и разбиралось 20 задач. Оказалось, что каждый из школьников решил две задачи и каждую задачу решили два школьника. Докажите, что можно так организовать разбор задач, чтобы каждый школьник рассказал одну из решённых им задач и все задачи были разобраны.
7.
Неуловимый Джо никогда не проигрывает на рулетке больше четырех раз подряд и никогда не ставит больше 10 долларов. Вначале Джо имеет 100 долларов. Как ему выиграть 1000 долларов? (В случае выигрыша на рулетке возвращается удвоенная ставка.)