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

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

Листок 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 долларов? (В случае выигрыша на рулетке возвращается удвоенная ставка.)