Московский центр непрерывного математического образования представляет книгу Питера Уинклера «Математические головоломки. Коллекция гурмана» (перевод М. Б. Преловской, под редакцией К. А. Кнопа, А. М. Петрунина, А. В. Устинова). Это сборник математических задач олимпиадного типа, популярный у преподавателей математических кружков. Теперь он выходит в русском переводе, с дополнениями и уточнениями. Отечественному читателю будет приятно отметить, что многие из задач этого сборника предлагались на всесоюзных математических олимпиадах или публиковались в журнале «Квант».
Предлагаем прочитать фрагмент книги.
Предисловие
Сомнение — это вестибюль, через который все должны пройти, прежде чем попасть во дворец Мудрости. Когда мы пребываем в сомнении и ищем истину своими собственными силами, мы приобретаем нечто, что останется с нами и будет служить нам снова и снова. Но если во избежание трудностей поиска мы воспользуемся превосходными познаниями друга, это знание не задержится у нас. Мы его не купили, а взяли взаймы.
Чарльз Калеб Колтон
Эти задачи не для всех.
Чтобы оценить и решить их, необходимо, но не достаточно быть в хороших отношениях с математикой. Вам будет нужно знать, что такое точка и прямая, что такое простое число и сколькими способами можно упорядочить пять карт, которые держит игрок в покер. Но самое важное, вы должны знать, что такое доказательство.
Вам не потребуется профессиональное знание математики. Вы знаете, что такое группа? Прекрасно, но вам это не понадобится. Компьютер, калькулятор и учебник по матанализу могут оставаться там, где лежат1, а вот переключатель сообразительности должен быть в положении «вкл».
Кто вы? Любители математики. Ученые из разных областей науки. Сильные школьники и студенты. И да, профессиональным математикам и учителям здесь тоже найдется над чем подумать. Эти задачи вы, как правило, не найдете в журнальных статьях, в списке заданий для домашней работы или в других книгах головоломок.
Так где же нашел их я? Они передаются из уст в уста. Среди математиков такие задачи распространяются как анекдоты. В некоторых случаях мне удалось отыскать опубликованный источник, такой как всесоюзные математические олимпиады, международные математические олимпиады или рубрики Мартина Гарднера в журнале Scientific American, но, конечно, это не всегда исходные источники; даже если так, задачи могли ходить в устном фольклоре задолго до этого. В некоторых случаях я могу точно назвать автора задачи (например, если это я сам). Часто решение мое собственное и необязательно то, которое предусматривалось автором задачи. Несколько решений одной задачи предлагаются, только когда я не смог устоять перед их красотой.
Формулировки задач и их решения — мои, и я беру на себя полную ответственность за ошибки и неточности. Присылайте жалобы, исправления и информацию об источнике задач на электронную почту pw@akpeters.com. (Одно исключение: как отмечено в последней главе, я не тот человек, которому надо отправлять предполагаемые решения из «Нерешенных головоломок».)
На момент написания этой книги я уже 28 лет являюсь профессиональным математиком (14 лет в академии и 14 лет в коммерческой компании). Собирать математические головоломки я начал еще в школе, в 60-е годы. В этой книжке представлена примерно сотня моих любимых задач. Чтобы попасть в эту книгу, задача должна была удовлетворять большинству из следующих требований.
Занимательность. Задача должна доставлять удовольствие. Задания с математических олимпиад Уильяма Лоуэлла Патнема, проводящихся ежегодно для студентов колледжей в США и Канаде, созданы для проверки способностей студентов. Это прекрасная цель, но она не всегда сочетается с занимательностью. (Тем не менее в книге представлены несколько задач с олимпиад Патнема.)
Универсальность. Задача должна говорить о некой общей математической истине. Сложные логические задачи, алгебраические задачи типа «Через два года Алиса будет в два раза старше, чем Боб, когда он был...», задачи, основывающиеся на свойствах конкретных больших чисел, и множество других типов искусно придуманных задач исключены.
Красота. Задача должна элементарно и легко формулироваться. Ведь чтобы задача передавалась устно, нужно, чтобы она легко запоминалась! Еще лучше, когда в формулировке присутствует элемент неожиданности.
Трудность. Должно быть неочевидно, как решить задачу.
Решаемость. У задачи должно найтись хотя бы одно элементарное и понятное решение.
Последние два пункта порождают противоречие: задача должна иметь простое решение, однако непросто решаться. Как бывает в хороших загадках, в задаче должно быть трудно отгадать ответ, но легко его понять. Конечно, для нерешенных задач из последней главы трудность очевидна, а последнее требование мы им не выдвигаем.
О формате книги. Для удобства задачи довольно свободно разделены по типу условия или решения по главам, соответствующим той или иной области математики. Решения приводятся в конце каждой главы (за исключением последней). Конец решения отмечен сердечком (♡). Если известны происхождение и история задачи, то они представлены там же. Условие задачи не повторяется перед ее решением. Я хотел бы, чтобы читатели пробовали решить задачи самостоятельно, прежде чем заглядывать в ответы.
Эти задачи трудны. Несколько из них долгое время существовали как нерешенные проблемы, пока кто-то не нашел (красивое) решение, которое вы здесь прочтете. Нерешенные задачи в конце книги, представляющие как бы логическое завершение коллекции, возможно, только немногим сложнее, чем все остальные.
Если вы сами решили какую-то из этих задач, то можете по праву гордиться, особенно если ваше решение лучше моего.
Удачи!
Замечание к русскому изданию. Поскольку многие из моих любимых головоломок родом из России, издавать эту книжку на русском языке в некотором смысле то же самое, что ехать в Тулу со своим самоваром. Тем не менее я уверен, что большинство читателей найдут здесь множество замечательных и новых для них задач; кроме того, благодаря работе переводчиков перед их глазами будет текст, в котором исправлены многие ошибки английского оригинала.
Успешного головоломания!
Питер Уинклер
Погружение
Когда напряженная умственная работа сменяется периодами отдыха, интуиция словно берет верх и порождает кристально ясные откровения, привносящие в процесс научного исследования неповторимое удовольствие и наслаждение.
Фритьоф Капра, физик
Эта глава предназначена для разминки и содержит задачи, не относящиеся к какой-либо специфической теме или методу. Однако, как часто бывает в таких случаях, некоторые ключевые идеи могут помочь в дальнейшем. Вот для начала одна из подобных задач.
Монеты в ряд
На столе выложен ряд из пятидесяти монет различного достоинства. Алиса берет монету с одного конца и кладет себе в карман, затем Боб берет монету с одного из концов, и так они продолжают по очереди, пока Боб не забирает последнюю монету.
Докажите, что при правильной игре Алиса сможет собрать не меньше денег, чем Боб.
Попробуйте сыграть в эту игру сами, для начала с несколькими монетами (или случайными числами), начните с 4 или 6 монет вместо 50. Совсем не очевидно, как играть оптимально, не так ли? Но, может, Алисе и не нужна оптимальная стратегия?
Сейчас подходящий момент установить себе правило — пытаться решить задачу до того, как продолжить чтение.
Решение. Пронумеруем все монеты числами от 1 до 50 и заметим, что, независимо от того, как ходит Боб, Алиса может забрать, по своему выбору, все монеты с четными номерами или все монеты с нечетными номерами. В одном из этих двух случаев она заведомо получит не менее половины общей суммы. ♡
Эту задачу я узнал от математика Нóги Алóна; говорят, что ее давали при приеме на работу в одной израильской IT-компании. Вообще говоря, у Алисы есть и лучшие стратегии, чем выбор всех монет с четными или нечетными номерами. Заметим, однако, что если у нас 51 монета вместо 50, то вполне может оказаться, что Боб (игрок, который ходит вторым) выигрывает, несмотря на меньшее, чем у Алисы, число собранных монет. Кажется парадоксальным, что четность общего количества монет так сильно влияет на результат игры, в которой всё действие происходит на концах цепочки.
Ну что ж, попробуйте теперь сами. Начнем с двух менее математических задач, а затем перейдем к вещам посерьезнее. Доверьтесь вашей интуиции!
Братья Биксби
В первый день занятий миссис Фельдман, войдя в класс, увидела сидящих за первой партой двух абсолютно одинаковых учеников, Дональда и Рональда Биксби.
— Вы двойняшки, не так ли? — спросила она.
— Нет, — ответили они хором.
Миссис Фельдман проверила записи в журнале и убедилась, что у мальчиков одни и те же родители и родились они в один и тот же день. Как такое может быть?
Свет на чердаке
На первом этаже имеются три выключателя, один из них включает свет на чердаке — но который? Ваша задача — после одного похода на чердак определить, какой выключатель относится к чердачной лампочке. Предварительно можно совершить какие угодно действия с выключателями.
Топливный кризис
Представим, что у нас дефицит бензина, так что заправочные станции, расположенные на кольцевой дороге, все вместе содержат количество бензина, достаточное лишь, чтобы проехать один раз по кольцу. Докажите, что можно выбрать такую заправку, что, заправившись на ней с первоначально пустым баком и далее заправляясь по пути, вы сможете проехать по всей кольцевой дороге.
Бикфордовы шнуры
Имеются два бикфордовых шнура, каждый из них сгорает ровно за одну минуту; скорость горения может быть неравномерна по длине шнура. Можно ли при помощи этих двух шнуров отмерить 45 секунд?
Числа и прямоугольники
Большой прямоугольник на плоскости разбит на меньшие, у каждого из которых либо высота, либо основание, либо и то и то — целые числа. Докажите, что большой прямоугольник также обладает этим свойством.
Весы и гири
На столе у учителя стоят чашечные весы, правая чашка весов перевешивает. На весах стоят гири (не обязательно одного веса), на каждой из которых написаны фамилии одного или нескольких учеников. Ученик, входя в класс, переставляет на другую чашку весов каждую гирю, на которой написана его фамилия. Докажите, что можно впустить в класс некоторую группу учеников, чтобы в результате перевесила левая чашка весов.
Часы на столе
На столе лежат пятьдесят точных ручных часов. Докажите, что существует момент времени, когда сумма расстояний от центра стола до кончиков минутных стрелок больше, чем сумма расстояний от центра стола до центров часов.
Путь по шахматной доске
Алиса начинает игру и ставит фишку в угол шахматной доски размером n × n. Боб передвигает фишку на соседнее поле, имеющее общую сторону с тем, на котором стоит фишка. Второй раз ходить на поле, где уже побывала фишка, нельзя. Алиса и Боб ходят по очереди. Проигрывает тот, кому некуда ходить.
При каких n у Алисы есть выигрышная стратегия? При каких n она выигрывает, если она делает первый ход не на угловое поле, а на соседнее с ним?
Решения и комментарии
Братья Биксби. Классическая головоломка. Конечно же, это были тройняшки. Третий близнец (Арнольд?) учился в другом классе.
Свет на чердаке. Эта задача пронеслась по миру, как эпидемия гриппа, где-то лет десять тому назад; я не знаю ее источника.
Действительно, невозможно определить, какой выключатель подключен к лампочке на чердаке, если всё, что вы имеете, — это один бит информации, полученный от вашего похода на чердак. Однако можно добыть больше сведений, если использовать ваши руки!
Включите выключатели 1 и 2, подождите несколько минут, затем выключите выключатель 2 и идите на чердак. Если лампочка не горит, но горячая, значит, выключатель 2 — это то, что мы ищем. ♡
Если вы не можете дотянуться до лампочки, но обладаете воистину огромным терпением, то можно добиться того же результата, включив выключатель 2 и затем, подождав пару месяцев, включить первый выключатель и посетить чердак. Если лампочка перегорела, то виноват в этом выключатель 2.
Топливный кризис. Эта задача была известна довольно давно, ее можно найти, например, в чудесной книге Ласло Ловаса2.
Трюк заключается в следующем: представьте, что вы начинаете на автозаправке, скажем, № 1 с большим запасом бензина и затем продолжаете свой путь, опустошая каждую автозаправку на кольцевой дороге. Когда вы вернетесь к заправке № 1, у вас будет столько же бензина, как и в начале пути.
Во время поездки записывайте, сколько остается бензина перед каждой заправочной станцией. Предположим, что это количество минимально перед автозаправкой № k. Значит, если начать с автозаправки № k с пустым баком, то нет риска оказаться без бензина между заправками. ♡
Математический факт, лежащий в основе этой задачи, называется леммой Рени3. Эта лемма утверждает, что если <x1, x2, , xm> — любая последовательность целых чисел, сумма которых равна +1, то ровно у одного из ее циклических сдвигов <x1, x2, , xm>, <x2, , xm, x1>, , <xm, x1, , xm-1> все частичные суммы положительные.
Замечательная книга Ласло Ловаса, упомянутая в решении, не является первоисточником задачи. Формулировка с кольцевой автодорогой и заправками встречалась в Задачнике «Кванта» 1971 года (М82) и в сборнике «Математические соревнования»4, но еще раньше она появилась на Пекинской математической олимпиаде5 1964 года. — Прим. ред.
Бикфордовы шнуры. Подожгите одновременно оба конца первого шнура и один конец второго. Когда первый шнур сгорит (через полминуты), подожгите незажженный конец второго шнура. К моменту, когда он догорит полностью, пройдет 45 секунд. ♡
Несколько лет назад эта и другие задачи о бикфордовых шнурах распространились по миру, как лесной пожар. Дик Хесс, эксперт по занимательной математике, собрал небольшую книжку таких задач6. Сам он впервые услышал приведенную выше задачу от Карла Морриса из Гарвардского университета.
Хесс рассматривает бикфордовы шнуры (он их зовет шнурками) различной длины, но поджигает их только с концов. Если же позволено поджигать шнур во внутренних точках и вы обладаете определенной ловкостью, то можно добиться гораздо большего. Например, можно отмерить 10 секунд с помощью одного 60-секундного шнура, если зажечь его с обоих концов и в двух внутренних точках, а затем каждый раз, когда сегмент сгорает, поджигать в новой внутренней точке. Таким образом, всё время горят три сегмента с двух концов, и шнур сгорает в шесть раз быстрее.
Будет немного суеты под конец, и, конечно же, для абсолютной точности понадобится бесконечное число спичек.
Целые числа и прямоугольники. Эта задача была предметом особой статьи Стэна Вэгона из колледжа Макалестер в Сент-Поле, Миннесота7.
Некоторые из решений, предложенных Вэгоном, забавным образом используют мощную математическую технику. А одно решение не из их числа таково.
Наложим на большой прямоугольник сетку, состоящую из квадратов со стороной 1/2, так, чтобы нижний левый угол прямоугольника находился в вершине клетки сетки. Раскрасив клетки сетки в белый и черный цвета в шахматном порядке, мы видим, что каждый малый прямоугольник ровно наполовину белый и наполовину черный. Следовательно, то же будет верно и для большого прямоугольника. Но, допустим, высота большого прямоугольника не целое число, тогда часть большого прямоугольника между линиями x = 0 и x = 1/2 не содержит одинаковое количество белого и черного цвета. Следовательно, основание должно быть целым. ♡
Автор книги предлагает следующее решение, которое вы не найдете в статье Вэгона. Пусть ε существенно меньше, чем наименьшая из сторон прямоугольников разбиения. Раскрасим каждый малый прямоугольник с целым основанием светло-серым цветом, кроме темных горизонтальных полосок шириной ε вдоль его верхней и нижней сторон. Раскрасим оставшиеся прямоугольники темно-серым, за исключением светло-серых вертикальных полосок шириной ε вдоль левой и правой сторон.
Поместим в нижний левый угол большого прямоугольника начало координат. Заметим, что у нас есть либо светлый путь с левой стороны большого прямоугольника до его правой стороны, либо темный путь с нижней стороны до верхней. Рассмотрим первый вариант. Каждая точка пересечения светлого пути с вертикальными сторонами малых прямоугольников имеет целую координату; таким образом, основание большого прямоугольника — целое число. Подобным же образом и темный путь снизу вверх дает целую высоту.
Весы и гири. Рассмотрим результат для каждого подмножества учеников, включая пустое. Заметьте, что каждая гиря окажется на левой чашке весов ровно в половине случаев. В частности, средний вес гирь на левой чашке для всех подмножеств учеников равен их среднему весу на правой чашке. Поскольку для пустого множества правая чашка тяжелее, для какого-то другого множества тяжелее должна быть левая. ♡
Источник: II Всесоюзная математическая олимпиада8, Ленинград, 1968.
Техника усреднения, описанная выше, будет использоваться в дальнейшем, обратите на нее внимание!
В курсе Игоря Пака9 собраны разные статьи на эту тему. — Прим. ред.
Часы на столе. Рассматривая только одни часы, мы видим, что в течение одного часа среднее расстояние от центра стола C до кончика минутной стрелки M превышает расстояние от C до центра часов W. Действительно, если провести через точку C прямую l, перпендикулярную прямой CW, то среднее расстояние от прямой l до точки M, очевидно, равно расстоянию от W до l, что, в свою очередь, равно CW. Но расстояние CM по меньшей мере равно расстоянию от M до l, а обычно больше.
Взяв сумму по всем часам, приходим к аналогичному заключению, и отсюда следует, что есть момент в течение одного часа, когда желанное неравенство выполняется. ♡
Требование точности часов обеспечивает движение каждой минутной стрелки с постоянной скоростью. Это не так уж важно, когда скорости различаются, если только наше терпение не ограничено одним часом.
Одно дополнительное замечание: если установить и расположить часы определенным образом, то можно добиться того, чтобы сумма расстояний от центра стола до кончиков минутных стрелок всегда была строго больше, чем сумма расстояний от центра стола до центров часов.
Источник: данная задача впервые появилась на X Всесоюзной математической олимпиаде10 в Душанбе, 1976.
Можно использовать более простую идею: сумма расстояний от центра стола O до концов минутных стрелок в два момента времени, отстоящие на 30 минут, больше удвоенного расстояния от O до центра часов (сумма длин двух сторон треугольника больше удвоенной длины медианы, проведенной к третьей стороне).— Прим. ред.
Путь по шахматной доске. Если n — четное число, то у Боба имеется простая выигрышная стратегия, независимо от того, где Алиса начинает. Он представляет себе, что шахматная доска покрыта доминошками, каждая доминошка покрывает две соседние клетки. Боб просто закрывает доминошку на каждом ходу, т. е. ставит фишку на вторую клетку той доминошки, куда пошла Алиса. (Заметим, что эта стратегия работает, даже если Алисе разрешено ставить фишку на любую клетку при каждом ходе!)
Если n нечетное и Алиса начинает с угла, то она выигрывает; ей надо представить, что доминошки покрывают всю доску, кроме угловой клетки, с которой она начинает.
Тем не менее Алиса проигрывает в случае нечетного n, если она должна начинать с клетки, соседней с угловой. Предположим, что угловые клетки на данной доске черные, т. е. Алиса начинает с белой клетки. Существует покрытие всей шахматной доски доминошками, за исключением одной черной клетки. Боб выигрывает, закрывая доминошки. Алиса никогда не сможет поставить фишку на незакрытую клетку, потому что все клетки, на которые она ходит, белые. ♡
Источник: XII Всесоюзная математическая олимпиада11, Ташкент, 1978.
1. В некоторых местах (например, в предпоследней главе) математический анализ всё же используется.— Прим. ред.
2. L. Lovász. Combinatorial Problems and Exercises. Amsterdam: North Holland, 1979.
3. G. Raney. Functional composition patterns and power series reversion // Trans. Amer. Math. Soc. 1960. Vol. 94. P. 441–451.
4. Е. Б. Дынкин, С. А. Станислав, А. Л. Розенталь. Математические соревнования: Арифметика и алгебра. М.: Наука, 1970. Задачи 76 и 77.
5. Зарубежные математические олимпиады / Под ред. И. Н. Сергеева. М.: Наука, 1987.
6. D. Hess. Shoelace Clock Puzzles. 1998.
7. S. Wagon. Fourteen proofs of a Result about Tiling a Rectangle // Amer. Math. Monthly. 1987. Vol. 94. P. 601–617.
8. Н. Б. Васильев, А. А. Егоров. Задачи Всесоюзных математических олимпиад. М.: Наука, 1988. Задача №110, автор не указан. — Прим. ред.
9. Раздел 5 в лекциях: I. Pack. Tilings (Math 285, Winter 2013), https://www.math.ucla.edu/~pak/courses/Tile-2013/tile2013.htm
10. Н. Б. Васильев, А. А. Егоров. Задачи Всесоюзных математических олимпиад. М.: Наука, 1988. Задача № 220, автор С. В. Фомин. — Прим. ред.
11. Там же. Задача № 262, автор не указан. — Прим. ред.
