Калейдоскоп в калейдоскопе

Калейдоскоп в калейдоскопе

Калейдоскоп «Кванта» этого номера посвящен… калейдоскопу! Название происходит от греческих слов $\kappa \alpha \lambda ος$ – красивый, $\varepsilon \iota \delta ος$ – вид, $\sigma \kappa ο\pi \varepsilon \omega$ – смотрю, наблюдаю. Этот оптический прибор-игрушка был придуман в начале XIX века и быстро стал любимой забавой во многих странах, включая Россию.

Внутри цилиндрической тубы калейдоскопа расположены три длинных прямоугольных зеркала, образующих зеркальную призму. За треугольником в основании призмы расположена «засыпка». При вращении калейдоскопа она пересыпается, составляя случайную картинку. Образовавшаяся в треугольнике картинка отражается в зеркалах и заполняет все поле зрения красивым узором.

В обычных калейдоскопах используются одинаковые зеркала, а значит, треугольник в основании призмы равносторонний.

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

34

КВАНТ 2015/№1

(Начало см. на с. 30)

также 2014 различных точек. Петя выписал на доске все расстояния от этих точек до прямых. Могли ли числа на доске образовывать в некотором порядке арифметическую прогрессию? А.Грибалко

12. Из 6 палочек разной длины сложили два треугольника одинакового периметра. Длины палочек отличаются не более чем в 7 раз. Всегда ли из них можно сложить два треугольника разного периметра? А.Шаповалов

Комбинаторные задачи

13. В пещере лежали в ряд 100 мешков массами 1 кг и 2 кг. В некоторых мешках разбойники хранили золото, в остальных – серебро. Рядом с каждым двухкилограммовым мешком лежали два мешка с серебром, а рядом с каждым килограммовым – хотя бы один мешок с серебром. Али-Баба унес из пещеры все золото. Какое наибольшее количество золота ему могло достаться? А.Шаповалов

14. Алиса и Базилио делят добытую кучу из 100 кошельков, в которых лежат 1, 2, …, 100 золотых соответственно. Ходят по очереди, начинает Алиса. За один ход можно вынуть из кучи любой кошелек и либо взять его себе, либо отдать напарнику. Как только у кого-то наберется 50 кошельков, другой забирает из кучи все остальные. Какое наибольшее количество золотых может обеспечить себе Алиса, как бы ни действовал Базилио? А.Шаповалов

15. Петя отметил на окружности 20 красных и 20 синих точек. Затем Вася проводит хорды так, чтобы концы каждой хорды были одного цвета и чтобы эти хорды не пересекались (даже в вершинах). Какое наибольшее количество хорд Вася гарантированно сможет провести, как бы ни отметил точки Петя? Е.Бакаев

16. Есть $n^{3}$ единичных кубиков. Петя раскрашивает их в два цвета (возможно, по-разному), причем каждую грань – в один цвет. Вася победит, если сможет сложить из всех кубиков куб со стороной n, у которого каждая грань одноцветна. При каком наименьшем n Петя не сможет ему помешать? А.Шаповалов

17. В каждую из n одинаковых пробирок налито не более половины пробирки раствора разной концентрации. Химик знает, где что, и может перелить из одной пробирки в другую любое нужное ему количество раствора (лишь бы пробирка не переполнилась). За какое наименьшее число переливаний он гарантированно может добиться, чтобы раствор в каждой пробирке был одинаковой концентрации (при этом некоторые пробирки, возможно, опустеют)? А.Шаповалов

18. В королевстве Кривых Весов запрещены чашечные весы, показывающие равновесие при равенстве масс грузов на чашах. Однако для любого a > 1 разрешены неравноплечие весы, показывающие равновесие, если вес груза на левой чаше в a раз больше веса на правой. Имея всего одни весы, Толя за два взвешивания может из 8 монет выявить одну фальшивую (более легкую). Чему равно a у Толиных весов? (Все настоящие монеты весят одинаково.) А.Шаповалов

19. Шесть команд в однокруговом турнире набрали 10, 7, 6, 6, 3 и 3 очка. Сколько очков (не обязательно целое число) начислялось за победу, если за ничью давали 1 очко, а за поражение 0? А.Шаповалов

20. В шахматном турнире участвуют 14 игроков. В каждом туре они разбиваются на пары случайным образом, но два шахматиста, игравшие друг с другом раньше, второй раз играть не могут. Турнир заканчивается, когда такое разбиение произвести невозможно. Найдите минимально возможное число туров. А.Блинков

21. Клетчатая полоска 1 ¥ n разбита на единичные клетки. Можно ли стороны клеток раскрасить в три цвета так, чтобы при выкидывании отрезков любого из цветов по оставшимся отрезкам можно было пройти из каждой вершины в любую другую? А.Шаповалов

22. Андрей закрасил некоторые клетки квадрата 100 ¥ 100. Далее ему разрешается закрашивать клетки по следующему правилу: если в квадрате 2 ¥ 2 закрашены три клетки, то он закрашивает четвертую. Какое наименьшее количество клеток Андрей должен закрасить изначально, чтобы в дальнейшем он сумел закрасить весь квадрат? А.Гаркавый

23. Квадратная таблица 5 ¥ 5 заполнена числами. Петя переставил ее столбцы так, что никакой столбец не остался на месте. В получившейся таблице Вася переставил строки так, что никакая строка не осталась на месте. В итоге получилась исходная таблица. Каково наибольшее возможное количество различных чисел в ней? Б.Френкин

24. На клетчатой доске 100 ¥ 100 стоит невидимая ладья. За один вопрос можно указать любой набор клеток и узнать, сколько из них побиты ладьей. Сколько таких вопросов нужно, чтобы наверняка узнать положение ладьи? (Считается, что ладья бьет поле, на котором стоит.) А.Шаповалов

Публикацию подготовили Л.Медников, А.Грибалко

45

МАТЕМАТИЧЕСКИЙ

C > 0 такое, что сумма чисел в любом столбце не меньше C, а сумма чисел в любой строке не больше C. Тогда можно из каждого столбца выбрать клетку с положительным числом так, что выбранные клетки будут стоять в различных строках. Таким образом, можно выбрать представителей столбцов из клеток с положительными числами. То, что числа неотрицательные, важно: для произвольных чисел утверждение задачи 4а неверно. Проверьте это. Классической задачей о представителях является задача о свадьбах. Задача 5. Рассмотрим некоторое конечное множество юношей, каждый из которых знаком с несколькими девушками. Спрашивается, при каких условиях можно женить юношей так, чтобы каждый из них женился на знакомой ему девушке? Теорема (Филип Холл, 1935). Решение задачи о свадьбах существует тогда и только тогда, когда любые K юношей из данного множества из N юношей знакомы в совокупности по меньшей мере с K девушками $( 1 \le K \le N ).$ Необходимость очевидна. Если какие-то K юношей знакомы с менее чем K девушками, то кому-то из них не найдется пары. Докажем достаточность от противного. Пусть N – наименьшее натуральное число, для которого теорема неверна. Очевидно, что N > 1. Может быть так, что каждые K юношей $( 1 \le K < N )$ знакомы более чем с K девушками, а может быть, что есть подмножество из K юношей, знакомых ровно с K девушками. В первом случае первый юноша может жениться на любой знакомой девушке, и тогда условие теоремы по-прежнему будет выполняться для оставшихся юношей и девушек. Действительно, пусть каждые K юношей знакомы более чем с K девушками. Одна из этих девушек, возможно, вышла замуж за первого юношу. Но без нее юношам знакомы не менее K девушек. Значит, после женитьбы любой пары остается N – 1 юноша и M – 1 девушка (где М – начальное число девушек), для которых условие теоремы по-прежнему выполняется. Но N было самым маленьким, для которого теорема неверна, значит, всех юношей можно женить. Во втором случае есть K юношей, знакомых ровно с K девушками. Так как K < N, мы можем женить этих юношей на этих девушках. Покажем, что остальных юношей тоже можно женить. Рассмотрим произвольное подмножество из оставшихся N – K юношей. Пусть в нем L юношей. Тогда, по условию теоремы, K женатых юношей плюс эти L юношей знакомы не менее чем с K + L девушками. Так как K женатых юношей не знакомы с незамужними девушками, остальные L юношей должны быть знакомы с не менее чем L незамужними девушками. Значит, для оставшихся N – K юношей выполнено условие теоремы, и они смогут жениться. Теорема доказана. Теорема Холла позволяет решить задачу 4 другим способом. Назовем школьников юношами, а тарелки – девушками. Знакомыми школьника будем считать тарелки, на которых лежит кусочек пирога, который принес школьник. Условие теоремы Холла выполнено, так как любые K школьников принесли не менее K килограммов пирогов и для них потребуется не менее K тарелок. Теорема (Д.Кёниг, 1931). Пусть задана прямоугольная таблица, в клетках которой стоят нули и единицы. Линией в таблице назовем как строку, так и столбец этой таблицы. Тогда минимальное число линий, содержащих все единицы, равно максимальному числу единиц, которые могут быть выбраны так, чтобы среди них не нашлось двух, расположенных на одной и той же линии. Существуют прямые способы доказать теорему Кёнига, но проще воспользоваться теоремой Холла. Пусть m –

КРУЖОК

минимальное число линий, содержащих все единицы, а M – максимальное число единиц, никакие две из которых не лежат на одной линии. Очевидно, что $m \ge M$. Докажем, что $m \le M$. Пусть минимальное покрытие m линиями состоит из r строк и s столбцов, где r + s = m. Так как перестановка строк и столбцов не влияют на m и M, можно так переставить строки и столбцы, чтобы линии покрытия были первыми r строками и s столбцами. Назовем юношами первые r строк таблицы, а девушками – столбцы с номерами, большими s (рис. 2). Юношу и девушку будем считать знакомыми, если на пересечении соответствующих строки и столбца стоит единица. Условия теоремы Холла выполнены в силу минимальности числа линий, иначе можно заменить какие-то K строк покрытия на K – 1 столбцов и все единицы останутся вычеркнутыми. Следовательно, можно женить юношей, т.е. выбрать в каждой из первых r строк по единице так, что никакие две единицы не лежат в одном столбце и ни одна не лежит в первых s столбцах. Рассуждая аналогично, мы можем выбрать s единиц в первых s столбцах, которые лежат в разных строках и не лежат в первых r строках. Итак, мы доказали существование m единиц, никакие две из кото-

Рис. 2

рых не лежат на одной линии. Следовательно, $m \le M$, и доказательство завершено. В свою очередь, из теоремы Кёнига следует теорема Холла. Действительно, пусть таблица из M строк и N столбцов содержит единицы в клетках, если юноша, имеющий номер столбца, знаком с девушкой, имеющей номер строки. Ясно, что все единицы в такой таблице нельзя вычеркнуть менее чем N линиями, так как после вычеркивания K столбцов в оставшихся N – K столбцов останутся единицы не менее чем в N – K строках.

Задачи для самостоятельного решения

1. На шахматной доске $8 \times 8$ пометили 16 клеток так, что на каждой вертикали и каждой горизонтали оказалось по две помеченные клетки. Докажите, что на помеченных клетках можно расставить 8 белых и 8 черных фигур так, чтобы на каждой вертикали и горизонтали стояло по одной белой и одной черной фигуре. 2. Школьники на кружке решали задачи. Оказалось, что каждый решил по 4 задачи и каждая задача решена четырьмя школьниками. Докажите, что можно организовать разбор задач так, чтобы каждый школьник рассказал ровно одну задачу и все задачи были разобраны. 3. Пусть каждый юноша знаком не менее чем с m девушками, а каждая девушка – не более чем с m юношами (m – произволь-

(Продолжение см. на с. 53)