Продолжаем серию публикаций о кружковском мышлении. Первые двенадцать частей:
1. Об осмысленности и автоматизме;
2. Кружковская задача;
3. Кружковская задача 2;
4. Шахматематика;
5. Кружковская задача 3;
6. Уровни очевидности;
7. Комплексный тест;
8. Кружковская задача 4;
9. Кружковская задача 5;
10. Разрезания и замощения;
11. Кружковская задача 6;
12. Кружковская задача 7.
Задача
У турецкого паши 40 жён, каждая живёт в своей комнате. Утром во время завтрака жёны заново дружатся и ругаются. В итоге каждая весь день дружит с пятью другими жёнами и враждует с семью другими. Каждый день паша приходит в гости к жене, потом идёт к её подруге, затем к подруге второй жены, и так далее. Если в течение дня паша побывал у какой-то жены, то в этот день он не приходит к её врагам. Какое наибольшее число жён может посетить паша в течение дня?
Комментарий
Редкая птица долетит до середины Днепра условия этой задачи... Но если несколько раз внимательно прочитать условие и понять, что написано, то это типичная оценка+пример на графах. На втором-третьем году кружка подобные задачи легко решают даже не самые сильные школьники.
Решение
Если бы паша посетил за ночь хотя бы 21 жену, то у этих жён должно быть не менее 21 жены-врага, откуда всего жён не меньше 42, а их 40.
Пример на 20 построить несложно. Пронумеруем жён от 1 до 40 и разделим их на две группы: с 1 по 20 и с 21 по 40. В каждой группе расставим их по кругу и подружим каждую с двумя предшественницами, двумя последовательницами и одной напротив. Вражды распределим следующим образом: первая будет враждовать с первыми семью из второго круга (21-27), вторая - со следующими семью (28-34), и так далее. Несложно убедиться, что в таком примере у каждой жены по 7 врагов. При этом паша легко посетит всех жён с 1 по 20.
История
Задачу в такой формулировке я придумал десять лет назад для олимпиады "Математика и алгоритмы". Многожёнство не прошло цензуру, и в вариант задача пошла в варианте магнитиков, которые притягиваются друг к другу или отталкиваются друг от друга. Полгода спустя исходная формулировка сыграла на турнире математических боёв в Костроме. Статистика взятия у этой задачи плохая, потому что длинное условие не располагает читать его и решать задачу. Однако опытные кружковцы справляются - в конце концов, их этому учат.
#математическийкружок #олимпиаднаязадача #задачанавнимательность
P.S. Не забывайте прочитать об истории математических кружков в Ленинграде/Санкт-Петербурге и обо мне.