Комбинаторные и топологические задачи

375. Неправильный магический квадрат. На помещенном здесь рисунке изображен правильный магический квадрат, составленный из чисел от 1 до 16 включительно. Сумма чисел, стоящих в любой строке, в любом столбце и на любой из двух больших диагоналей, равна 34. Предположим теперь, что вам запрещено использовать числа 2 и 15, но вместо этого вы можете повторить любые два числа, уже использованные ранее.

Как следует расположить числа, чтобы в новом квадрате их суммы во всех строках, столбцах и на диагоналях по-прежнему равнялись 34? Успех зависит от того, какими числами вы замените 2 и 15.

376. Недоразумение с магическим квадратом. Перед вами магический квадрат пятого порядка. Я обнаружил, что подавляющее большинство людей, не знакомых глубоко с теорией магических квадратов, убеждены, будто в квадратах пятого порядка в центре непременно должно стоять число 13. Один читатель, на протяжении многих лет забавлявшийся этим квадратом, был просто поражен, когда узнал от меня, что в центре такого квадрата может стоять любое число от 1 до 25.

Докажите, что это действительно так. Попытайтесь, например, составить магический квадрат пятого порядка, в центре которого стояла бы 1.

377. Разностные квадраты. Можете ли вы расположить 9 цифр в виде квадрата таким образом, чтобы в любой строке, в любом столбце и на каждой из больших диагоналей разности между суммой двух цифр и третьей цифрой совпадали между собой? На нашем рисунке приведен квадрат, в котором все строки и столбцы удовлетворяют требуемому условию — разность в них равна 3 (например, 4 + 2 - 3, 1 + 9 - 7, 6 + 5 - 8 и т. д.), а вот диагонали «подкачали», поскольку разности 8 - (4 + 1) и 6 - (1 + 2) получены запрещенным способом: не из одной цифры должна вычитаться сумма двух остальных, а из суммы двух — одна.

Сколько всего существует решений?

378. Так ли просто? Перед вами простой магический квадрат, у которого суммы чисел, стоящих в любой строке, в любом столбце и на главных диагоналях, равны 72. Головоломка состоит в том, чтобы превратить его в мультипликативный магический квадрат, у которого произведения чисел, стоящих в любой строке, в любом столбце или на любой из больших диагоналей, совпадали бы между собой. Не разрешается ни менять числа местами, ни прибавлять к ним что-либо, ни вообще пользоваться какими-либо арифметическими знаками! Можно лишь передвигать цифры внутри одной клетки. Так, вместо 27 разрешается брать 72.

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

379. Фокус с магическим квадратом. Этот фокус был весьма разрекламирован в США много лет назад.

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

Может быть, читатель разгадает, в чем здесь дело?

380. Магический квадрат из четырех цифр. Поскольку данный квадрат составлен из одного и того же числа 1234, естественно, что суммы чисел, стоящих во всех строках, столбцах и на диагоналях, равны между собой. Суть головоломки в том, чтобы составить и разместить 9 различных четырехзначных чисел (составленных из тех же самых четырех цифр) так, чтобы они тоже образовывали правильный магический квадрат. Помните, что все вместе числа должны содержать по девять экземпляров каждой из цифр 1, 2, 3, 4 и что это должны быть настоящие четырехзначные числа без каких-либо дробей; никакие трюки здесь не допускаются.

381. Прогрессирующие квадраты. Перед вами магический квадрат, постоянная которого, то есть сумма чисел в каждой строке, в каждом столбце и на каждой из двух диагоналей, равна 287. Если мы удалим числа, расположенные по краям, то останется другой магический квадрат, постоянная которого равна 205. Если мы опять удалим крайние числа, то получится квадрат с постоянной 123. Заполните теперь пустые клетки числами от 1 до 83 включительно так, чтобы получился магический квадрат с постоянной 369 на любой из 20 его прямых.

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

Можно ли построить магический квадрат, у которого суммы чисел, стоящих в любой строке, в любом столбце и на каждой из двух больших диагоналей, были бы одинаковы, из чисел от 1 до 25 включительно, если размещать в заштрихованных клетках только нечетные числа, а в остальных четные? Существует достаточно много решений этой задачи. Не смогли бы вы найти хотя бы одно из них?

383. Пятиконечная звезда. Головоломки со звездами обладают своеобразной притягательной силой. Я приведу пример такой головоломки с простой пятиконечной звездой.

В каждый кружок изображенной здесь пятиконечной звезды требуется поместить различные числа таким образом, чтобы сумма любых четырех чисел, стоящих на одной прямой, равнялась 24. Решения с десятью последовательными числами не существует, однако вы можете использовать любые целые числа, какие пожелаете.

384. Шестиконечная звезда. В предыдущей задаче мы рассмотрели случай с пятиконечной звездой. Оказывается, с шестиконечной звездой дело обстоит еще интересней. В этом случае (см. рисунок) мы всегда можем использовать 12 последовательных чисел, от 1 до 12, а сумма четырех чисел на каждой прямой всегда окажется равной 26. Сумма чисел, стоящих в шести вершинах, может равняться любому числу от 24 до 54 включительно, кроме 28 и 50. В нашем примере эта сумма равна 24. Если вместо каждого из чисел вы подставите разность между ним и 13, то получите другое решение, дополнительное к данному, с суммой вершин, равной 54 (78 минус 24). Две дополнительные суммы в совокупности всегда дают 78.

Я приведу общее число различных решений и укажу на некоторые любопытные законы, которым подчиняется эта задача, но ее решение предоставлю читателю. Существует 6 и только 6 размещений, при которых сумма чисел на каждой прямой и во всех вершинах равна 26. Можете ли вы найти одно из них или даже все?

385. Семиконечная звезда. Мы уже познакомились вкратце с пяти- и шестиконечными звездами. Случай с семиконечной звездой особенно интересен. Все, что от вас требуется, это разместить в кружочках числа от 1 до 14 так, чтобы в любых четырех кружочках, лежащих на одной прямой, они в сумме давали 30.

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

386. Две восьмиконечные звезды. Головоломки с пяти-, шести- и семиконечными звездами приводят нас к восьмиконечной звезде. Эту звезду можно образовать двумя различными способами (см. рисунок); здесь приводится и решение для первого варианта. Числа от 1 до 16 расположены таким образом, что сумма четырех из них вдоль каждой прямой равна 34. Если вместо каждого числа вы подставите разность между ним и 17, то получите дополнительное решение.

Если читатель попытается найти какое-нибудь решение для другой звезды, то, даже зная решение, приведенное выше, он убедится, что этот орешек расколоть не так-то просто. Однако я представлю вам головоломку в легкой и занимательной форме. Оказывается, что любое решение для первой звезды можно автоматически преобразовать в решение для второй, если правильно взяться за дело. Каждая прямая из четырех чисел в одном случае появится и в другом, изменится лишь порядок чисел. Располагая этими сведениями, вам нетрудно будет найти решение и для второй звезды.

387. Гарнизоны фортов. Перед вами на рисунке изображена система фортификационных сооружений. Всего имеется 10 связанных между собой фортов, цифры обозначают численность размещенных в них небольших гарнизонов. Командующий решил передислоцировать гарнизоны таким образом, чтобы вдоль каждой из пяти прямых размещалось по 100 человек.

Не могли бы вы указать, как это следует сделать?

Гарнизоны должны передислоцироваться целиком, не будучи разбитыми на части. Эта головоломка с фишками весьма занимательна и не очень трудна.

388. Карточный пятиугольник. Набросайте на большом листе бумаги пятиугольник. Затем положите все карты одной масти, исключив валета, даму и короля, так, чтобы суммы очков трех карт, лежащих на любой стороне пятиугольника, равнялись между собой[19]. Можно заметить, что приведенное на рисунке размещение карт не удовлетворяет нашему условию. Однако после того, как вы найдете соответствующее правило, карты можно будет раскладывать, не задумываясь. Решений здесь существует очень мало.

389. Головоломка с семиугольником. Разместите в кружках числа от 1 до 14 (см. рисунок) так, чтобы три числа на каждой из сторон в сумме давали 19.

390. Розы, трилистники и чертополох. Разместите числа от 1 до 12 (по одному числу в каждой картинке) таким образом, чтобы совпали семь их сумм: вдоль каждого из двух центральных столбцов, вдоль каждой из двух центральных строк, по всем четырем розам, по всем четырем трилистникам, по всему чертополоху.

391. Магический шестиугольник. На помещенном здесь рисунке показано, как можно разместить числа от 1 до 19, чтобы суммы трех чисел вдоль каждой из 12 прямых равнялись 23. Шесть прямых совпадают, конечно, с шестью сторонами шестиугольника, а шесть остальных проходят через центр.

Можно ли иначе расставить числа, чтобы сумма по любому из 12 направлений по-прежнему составляла 23? Существует только одно такое размещение чисел.

392. Головоломка с колесом. Разместите числа от 1 до 19 в 19 кружках (см. рисунок) так, чтобы сумма любых трех чисел на одной прямой равнялась 30. Сделать это нетрудно.

393. У ручья. Существует общее мнение, что головоломки, в которых требуется отмерить некоторое количество жидкости, можно решить только путем ряда проб, однако в подобного рода случаях можно найти общие формулы для решений. Воспользовавшись как-то преимуществами неожиданного досуга, я рассмотрел этот вопрос более внимательно. В результате обнаружились весьма интересные вещи. Рассмотрим, например, простейший случай, когда некий человек приходит к ручью только с двумя сосудами и хочет отмерить нужное количество воды. Если мы имеем дело, скажем, с бочкой вина, то у нас могут возникнуть разного рода сложности, связанные с тем, пуста ли бочка или полна, известны ли нам ее вместимость и содержимое или нет, допускается ли потеря вина или нет и можно ли переливать вино обратно в бочку. В случае у ручья все эти сложности исчезают. Может быть, задача упростилась настолько, что говорить о ней как о головоломке вообще не имеет смысла? Давайте посмотрим.

Человек приходит к ручью с двумя сосудами вместимостью соответственно 15 и 16 л. Каким образом он может отмерить ровно 8 л воды за наименьшее число операций? Наполняя сосуд, опустошая его или переливая воду из одного сосуда в другой, мы совершаем одну операцию.

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

394. Затруднительное положение. Давайте теперь сделаем следующий шаг и рассмотрим случай, когда некоторое количество жидкости пропадает, хотя запас жидкости на этот раз ограничен сверху заданной величиной.

Американские органы по контролю над спиртными напитками[20] обнаружили полную бочку пива и собрались было уже опрокинуть ее на землю, когда владелец бочки, указав на два кувшина, попросил оставить ему немного пива, чтобы немедленно распить его со своими домашними. Один кувшин вмещал 7, а другой 5 кварт. Полицейский был шутником и, полагая, что это невозможно, разрешил хозяину оставить по одной кварте пива в каждом кувшине, если тот сумеет точно отмерить это количество пива, не выливая ничего обратно в бочку.

Как это можно сделать за наименьшее число операций, не делая пометок на кувшине и не прибегая ни к каким другим уловкам? Напомним, что американская пивная бочка содержит ровно 120 кварт.

395. Снова затруднительное положение. Попытайтесь решить предыдущую головоломку при условии, что пиво можно переливать обратно в бочку.

396. Бочонок вина. У одного человека был бочонок вина вместимостью 10 л и кувшин. Однажды он наполнил из бочонка полный кувшин вина, а бочонок долил водой. Когда вода полностью смешалась с вином, он еще раз налил полный кувшин и снова долил бочонок водой. После этого вина и воды в бочонке оказалось поровну.

Какова вместимость кувшина?

397. Измерение воды. Служанку послали к роднику с двумя сосудами вместимостью 7 и 11 пинт. Ей нужно принести назад ровно 2 пинты воды.

Чему равно наименьшее число операций в этом случае? Под «операцией» мы понимаем либо наполнение сосуда, либо его опорожнение, либо переливание воды из одного сосуда в другой.

398. Винная смесь. Один сосуд наполнен вином на ?, а другой сосуд равной вместимости — на ?. Каждый из этих сосудов долили водой и все их содержимое смешали в кувшине. Половину получившейся смеси снова вылили в один из двух сосудов.

В каком соотношении там оказались после этого вино и вода?

399. Украденный бальзам. Три вора украли у одного джентльмена вазу с 24 унциями бальзама. Спешно унося ноги, они встретили в лесу продавца стеклянной посуды, у которого и приобрели три сосуда. Найдя укромное местечко, воры решили разделить добычу, но тут обнаружили, что вместимость их сосудов 5, 11 и 13 унций.

Как им разделить между собой бальзам поровну?

400. Доставка молока. Однажды утром молочник вез в свою лавку два 80-литровых бидона с молоком, как вдруг ему повстречались две женщины, умолявшие тут же продать им по 2 л молока. У миссис Грин был кувшин вместимостью 5 л, а у миссис Браун 4-литровый кувшин, в то время как у молочника вообще нечем было отмерять молоко.

Как же молочник умудрился налить точно по 2 л молока в каждый кувшин? Вторая порция доставила ему наибольшие трудности. Однако он успешно справился с задачей всего за 9 операций. (Под «операцией» мы понимаем переливание либо из бидона в кувшин, либо из одного кувшина в другой, либо, наконец, из кувшина назад в бидон.)

Каким же образом действовал молочник?

401. Путь до Типперери. Популярный бард уверяет нас, что «путь далек до Типперери». Взгляните на прилагаемую карту и скажите, сумеете ли вы найти наилучший путь туда. Отрезки прямых изображают переходы от города до города. Из Лондона в Типперери следует добраться за четное число переходов. Сделать это за 3, 5, 7, 9 или 11 переходов не составляет труда, но все это нечетные числа. Дело в том, что при нечетном числе переходов опускается один очень важный морской переход. Если вам удастся добиться цели и вы доберетесь до места за четное число переходов, то это произойдет потому, что вы пересечете Ирландское море. Какой отрезок пути проходит по Ирландскому морю?

402. Разметка теннисного корта. Линии нашего теннисного корта почти стерлись и нуждаются в обновлении. Мое приспособление для разметки таково, что, начиная и кончая линию где угодно, мне нельзя ее прервать, чтобы не смазать. Поэтому некоторые участки приходится проходить дважды.

С какого места мне следует начать и по какому пути двигаться, чтобы, не прерывая линии, полностью разметить корт и дважды пройти как можно меньшие участки? Размеры корта приведены на рисунке. Какой же путь будет наилучшим?

403. Пересекая отрезки. На протяжении многих лет меня нередко спрашивают, разрешима ли следующая головоломка.

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

Существует общее мнение, что этого сделать нельзя. Я обозначил крестиками «нечетные узлы», а общее правило для таких задач гласит, что минимальное число непрерывных линий должно равняться половине числа нечетных узлов, то есть точек, из которых можно двигаться по нечетному числу направлений. В нашем случае имеется 8 узлов, из которых можно двигаться по трем (нечетное число) направлениям, и, следовательно, требуется четыре линии. Однако эту головоломку можно решить с помощью одного трюка, истолковав условия буквально. Сначала вы складываете бумагу и жирным карандашом рисуете CD и EF (см. рисунок 2) одним росчерком. Затем вторым росчерком вы проводите линию от А до В и третьим — линию GH.

За последние несколько лет эта головоломка обрела новую форму. Вам дают ту же сеть линий и предлагают, начав с любого места, обойти ее, побывав на каждом отрезке один и только один раз и нигде не пересекая своего пути. На рисунке 3 показано, что именно имеется в виду. Там изображена одна из попыток решить головоломку. Эта попытка неудачна, поскольку отрезок KL остался нетронутым. Мы могли бы пересечь его вместо КМ, но от этого положение ничуть не улучшилось бы.

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

404. Девять мостов. На рисунке изображена схема района со сложной системой ирригационных сооружений. Линиями обозначены каналы, окружающие 4 острова A, В, C и D. На каждом из островов стоит дом. Через каналы перекинуты 9 мостов Когда бы Томпкинс ни выходил из дома, собираясь навестить своего приятеля Джонсона, он всегда следует одному и тому же эксцентрическому правилу — прежде чем добраться до места назначения, он непременно проходит по каждому из мостов только один раз.

Сколько различных маршрутов может при этом выбрать Томпкинс? Его собственным домом можно считать любой.

405. Нападение на рыболовные суда. На промысел в море вышли 49 рыболовных судов. Представьте себе, что на них напал вражеский корабль. Каким образом он смог бы их протаранить и потопить, следуя 12 прямыми курсами, если весь маневр начинается и заканчивается в одной точке?

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

Подсчитайте общее число различных путей, которыми он может добраться до церкви.

407. Противолодочная сеть. На рисунке изображен участок длинной противолодочной сети. Головоломка состоит в том, чтобы, сделав наименьшее число разрезов снизу вверх, разделить сеть на две части, освободив тем самым проход для подводной лодки.

Где именно следует перерезать сеть, если разрезать узлы запрещается? Помните также, что разрезы следует производить от нижней границы сети до верхней.

408. Двадцать два моста. Вы видите здесь схему района с развитой системой ирригационных сооружений, на которой указаны многочисленные каналы и мосты. Человек выходит с одного из участков, обозначенных буквами, чтобы навестить приятеля, живущего на другом участке. Желая при этом совершить моцион, он проходит по каждому мосту один и только один раз.

Головоломка состоит в том, чтобы выяснить, на каких участках расположены дома приятелей. Она покажется вам чрезвычайно простой, если вы подумаете над ней несколько минут. Разумеется, не следует выходить за пределы схемы.

409. Следы на снегу. Четыре школьника, живущих соответственно в домах А, В, С и D, посещают разные школы. Однажды утром после бушевавшей всю ночь метели особенно хорошо было видно, что следы четырех мальчиков нигде не пересекают друг друга и не выходят за пределы квадрата. Возьмите карандаш и продолжите их пути так, чтобы мальчик А попал в школу А, мальчик В — в школу В и т. д. и чтобы эти пути не пересекались.

410. Могильная плита. Одна из могильных плит на кладбище, прилегающем к церкви Святой Марии в Монмаусе, выглядит так, как показано на нашем рисунке.

Сколько существует различных способов, с помощью которых можно прочитать надпись: HERE LIES JOHN RENIE[21], начиная с центральной буквы Н и переходя на каждом шаге от одной буквы к соседней?

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

Не могли бы вы начертить путь мухи? Его можно проделать, двигаясь 17 прямыми курсами.

412. Дорожная инспекция. Отправляясь из города А, инспектор должен проверить состояние всех дорог между населенными пунктами, обозначенными на схеме буквами. Длина каждой из этих дорог равна 13, 12 и 5 км, как показано на схеме.

Каким наикратчайшим путем следует двигаться инспектору, если он может закончить путь в любой заранее выбранной точке?

413. Железнодорожные маршруты. На рисунке показана упрощенная схема железнодорожных путей. Мы хотим узнать, сколькими различными путями можно проехать от А до Е, не проезжая дважды по одному и тому же участку при любом маршруте.

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

Сколько всего существует различных маршрутов?

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

Сколько существует различных маршрутов, на которых он может остановить свой выбор? Тут есть над чем поломать голову, пока вы не изобретете какой-нибудь остроумный метод. Каждый маршрут должен закончиться в городе А, из которого вы стартовали, и ехать вы должны из одного города в другой прямо, не сворачивая на перекрестках дорог.

415. Путешествие миссис Симпер. На рисунке изображена упрощенная схема маршрута, по которому моя приятельница миссис Симпер собирается путешествовать следующей осенью. Можно заметить, что на схеме представлено 20 городов, соединенных между собой железнодорожными линиями. Миссис Симпер живет в городе A и хочет посетить все остальные города только по одному разу, возвратившись в конце домой.

Читателю, наверное, будет небезынтересно узнать, что миссис Симпер может выбрать любой из 60 маршрутов, если считать разными маршруты, отличающиеся лишь направлением. Между N и О, а также между R и S дорога проходит через тоннель, но, как истая леди, миссис Симпер категорически против езды по тоннелям. Ей хотелось бы также отложить свой визит в D на возможно более поздний срок, чтобы иметь удовольствие встретиться со своей старой приятельницей, живущей в этом городе.

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

416. Шестнадцать прямолинейных участков. Один торговый агент отправился на своем автомобиле из точки, указанной на рисунке, решив проделать путь 76 км, который состоит из 16 прямолинейных участков, ни разу не проехав при этом по одному и тому же участку дважды. Точки обозначают населенные пункты, расположенные через 1 км друг от друга, линии — избранный нашим агентом маршрут. Агент выполнил задуманное, но при этом 6 населенных пунктов остались в стороне от его пути.

Не могли бы вы указать лучший маршрут, при котором, проделав путь 76 км, состоящий из 16 прямых участков, агент посетил бы все пункты, кроме трех?

417. Составьте маршруты. На рисунке изображена схема (весьма упрощенная, разумеется) некоторого района. Кружочками обозначены населенные пункты, а прямыми — соединяющие их дороги.

Не могли бы вы указать, каким образом 5 автомобилистов могут проехать соответственно из А в А, из В в В, из С в С, из D в D и из Е в Е таким образом, чтобы их пути не содержали общих участков и даже не пересекались между собой?

Возьмите карандаш и нарисуйте 5 искомых маршрутов; при этом вам, вероятно, придется немного поломать голову. Разумеется, не важно, в каком из двух городов, обозначенных одинаковыми буквами, начинается, а в каком заканчивается данный маршрут, так как нас интересует лишь вопрос, по каким дорогам он пролегает. Обратите внимание, что если вы отправитесь из А в А, следуя по вертикали вниз, то загородите дорогу всем остальным автомобилям, кроме идущего из В в В, поскольку, конечно, все автомобили обязаны двигаться лишь по тем дорогам, которые изображены на схеме.

418. Мадам. Сколькими различными способами можно прочитать на нашем рисунке слово MADAM? Вы можете двигаться, как вам заблагорассудится, — вверх и вниз, вперед и назад по любой из открытых дорожек. Однако каждая следующая буква должна находиться рядом с предыдущей. Перескакивать через букву запрещается.

419. Треугольники в круге. Вот одна небольшая головоломка, которая потребует от вас терпения и решимости довести дело до конца. Вам предлагается нарисовать круг и треугольники, изображенные на рисунке, с помощью наименьшего числа росчерков[22] карандаша. При этом разрешается дважды проходить по одной и той же линии, а также в любом месте начинать и заканчивать рисунок.

420. Сиамская змея. Условия этой головоломки чрезвычайно просты.

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

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

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

422. «Классики». Мы часто видим, как дети играют в древнюю и повсюду популярную игру «классики». При одной из разновидностей этой игры на земле рисуется изображенная здесь фигура. Мы хотим узнать, можно ли ее нарисовать с помощью одной непрерывной линии. Оказывается, что это возможно.

Сумеет ли читатель нарисовать такую фигуру, не отрывая карандаша от бумаги и не проходя дважды по одной и той же линии? Кривая линия обычно не используется в игре, но мы ее добавили, чтобы сделать головоломку интереснее.

423. Коварная головоломка. Один неразборчивый в средствах делец предложил 100 долларов за правильное решение следующей головоломки. Узник, приговоренный к пожизненному заключению, обратился к королю с просьбой о помиловании. Не желая оказать ему эту милость, но и не ответив отказом, король предложил помиловать узника, если тот, отправляясь из камеры А, побывает в каждой камере тюрьмы и возвратится опять в А, не заходя дважды ни в одну из камер. Сам делец либо не располагал решением головоломки, либо намеревался выйти из положения с помощью какого-нибудь трюка.

Какой наилучший ответ мог бы предложить читатель, чтобы выполнить условия головоломки как можно точнее?

424. Посадка деревьев. Один человек посадил 13 деревьев так, как показано на рисунке. В результате у него получилось 8 рядов, по 4 дерева в каждом. Однако ему не нравилось, как посажено второе дерево в горизонтальном ряду. Свои чувства по этому поводу он сформулировал довольно туманно, сказав, что «оно отлынивает там от работы и вообще ведет себя как изрядный лентяй». Второе дерево в горизонтальном ряду действительно было «из ряда вон выходящим», поскольку его единственное назначение состояло в том, чтобы заполнить второй ряд. Поэтому человек решил пересадить деревья получше и через некоторое время обнаружил, что сможет посадить их в 9 рядов, по 4 дерева в каждом.

Может ли читатель показать, как это делается?

425. Двадцать монет. Если 16 одинаковых монет расположить в виде квадрата, то в каждой строке, в каждом столбце и на каждой из двух больших диагоналей будет находиться одинаковое число монет.

Нельзя ли сделать то же самое с 20 монетами?

426. Пересадка деревьев. У одного человека была плантация из 22 деревьев, посаженных так, как показано на рисунке.

Каким образом ему следовало пересадить 6 из них, чтобы они образовали 20 рядов по 4 дерева в каждом?

427. Головоломка с колышками. На рисунке изображена квадратная доска из красного дерева с 49 отверстиями. В 10 отверстий вставлено 10 колышков.

Головоломка состоит в том, чтобы переставить 10 колышков в другие отверстия так, чтобы всего получилось 5 рядов колышков по 4 колышка в каждом.

Какие 3 колышка следует переместить и куда?

428. Пять прямых с четырьмя фишками. На рисунке показано, как можно расположить 10 фишек в точках пересечения сплошных линий, чтобы они при этом оказались лежащими на 5 прямых (отмеченных пунктиром) по 4 фишки на каждой.

Можете ли вы найти второе решение?

Разумеется, решение, которое можно получить из данного при отражении, не считается отличным от исходного. Требуется найти совершенно новую схему расстановки фишек и, разумеется, не увеличивать размеры «клетчатого участка».

429. Порядок боевых кораблей. Боевые корабли встали на якорь, как показано на рисунке. Головоломка состоит в том, чтобы передвинуть 4 корабля на новые позиции (оставив остальные там, где они стоят) так, чтобы все 10 кораблей образовали 5 прямых по 4 корабля на каждой.

Как должен поступить адмирал?

430. Головоломка с созвездием. Группу звезд, изображенную на рисунке, очень трудно обнаружить в самую ясную ночь по той простой причине, что она... невидима. 21 звезда этого созвездия образует 7 прямых по 5 звезд на каждой.

Не могли бы вы изменить расположение звезд так, чтобы они образовали 11 прямых по 5 звезд на каждой? Существует много решений этой головоломки. Попытайтесь найти симметричное.

431. Проблема четырех красок. Проблема четырех красок формулируется очень просто. Нужно доказать, что для раскраски любой карты достаточно не более четырех красок, если все сопредельные страны должны быть выкрашены в разные цвета. Страны, у которых общий участок границы состоит из одной точки (как у голубых Г и желтых Ж в точке а), не считаются сопредельными[23]. Если бы граница вместо са проходила по участку cb, то две желтые страны Ж оказались бы сопредельными, но тогда мы могли бы перекрасить, например, внешнюю желтую страну Ж в зеленый цвет, и все оказалось бы снова в порядке: желтая страна Ж на нашей карте могла бы с успехом быть и зеленой З.

Я приведу в сжатой форме мое собственное доказательство, которое некоторые математики считают вполне приемлемым. Однако кое-кто полагает, что в нем имеются «пробелы». Доказательство дается в такой форме, которую может понять каждый. Однако следует помнить, что одно дело быть убежденным в чем-то, и совсем другое — дать этому строгое доказательство.

432. Раскрашивание карты. Однажды утром полковник Крэкхэм попросил своего юного сына раскрасить все 26 районов карты, изображенной на рисунке, так, чтобы любые два прилегающих друг к другу района имели разные цвета. Молодой человек с минуту смотрел на карту, а затем сказал:

— В моем ящике не хватит одной краски.

Оказалось, что он прав. Сколько у него было красок? Пользоваться черной и белой красками ему не разрешалось.

433. Подаренные картины. У богатого коллекционера было 10 ценных картин. Ему захотелось сделать одному музею подарок, но коллекционер никак не мог сообразить, сколькими вариантами подарка он располагает: ведь подарить можно любую одну картину, любые две, любые три картины и т. д., можно даже подарить все десять картин.

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

434. Выборы в парламент. Сколько существует разных способов, которыми можно избрать 615 членов парламента если имеются всего четыре партии: консерваторов, либералов, социалистическая партия и партия независимых? Мандаты могут распределяться, например, так: консерваторы — 310, либералы — 152, социалисты — 150, независимые — 3. Возможны и другие варианты: консерваторы — 0, либералы — 0, социалисты — 0, независимые — 615 или консерваторы — 205, либералы — 205, социалисты — 205, независимые — 0 и т. д. Кандидатов от каждой партии мы не различаем, поскольку для нас важно только общее количество кандидатов.

435. Скамья магистрата. Один мой приятель из Сингапура попросил меня некоторое время назад решить следующую задачу. На скамье одного магистрата (где именно, неизвестно) занимают места два англичанина, два шотландца, два уэльсца, один француз, один итальянец, один испанец и один американец. Англичане не хотят сидеть рядом, шотландцы не хотят сидеть рядом и уэльсцы тоже не желают сидеть рядом друг с другом.

Сколькими различными способами могут разместиться на скамье эти 10 человек так, чтобы никакие два человека одной и той же национальности не сидели рядом?

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

Как почтенному семейству перебраться на противоположный берег за возможно меньшее число рейсов? Никаких уловок вроде использования веревки или переправы на другой берег вплавь не допускается.

437. Миссионеры и каннибалы. Существует один необычный рассказ о трех миссионерах и трех каннибалах, которые должны были переправиться через реку в небольшой лодке, вмещающей одновременно только двух человек. Будучи наслышаны о вкусах каннибалов, миссионеры не могли позволить себе роскошь остаться на каком-нибудь берегу реки в меньшинстве. Только один из миссионеров и один из каннибалов умели грести.

Каким образом им удалось переправиться?

438. Бегство через реку. Во время бегства турецких войск при Трейсе небольшой отряд оказался на берегу широкой и глубокой реки. Здесь обнаружили лодку, в которой катались два мальчика. Лодка была такой маленькой, что могла выдержать только двоих детей или одного взрослого.

Каким образом офицер сумел переправиться вместе со своими 357 солдатами через реку, вернув в конце переправы лодку мальчикам? Сколько раз пришлось лодке проплыть от берега до берега?

439. Соревнования по гольфу[24]. Меня попросили составить таблицу соревнований по американскому гольфу. Условия соревнований таковы:

1. Каждый игрок играет с каждым из остальных игроков один и только один раз.

2. Число дорожек в два раза меньше числа игроков, и каждый игрок играет дважды на каждой дорожке, кроме одной, на которой он играет только один раз.

3. Все игроки играют одновременно в каждом туре, а в последнем туре каждый игрок играет на соответствующей дорожке впервые.

Я составил таблицы для разного числа игроков вплоть до 26. Однако такая задача слишком трудна для данной книги, за исключением простого случая с шестью игроками.

Может ли читатель, обозначив игроков А, В, С, D, Е и F и объединив их всевозможными способами в пары (АВ, CD, EF, AF, BD, СЕ и т. д.), заполнить приведенную здесь небольшую таблицу для случая с шестью игроками?

440. Футбольные результаты. В конце футбольного сезона один читатель сообщил мне, что, возвращаясь из Глазго после матча между Шотландией и Англией, он обратил внимание на следующую таблицу, помещенную в газете:

Поскольку он уже знал, что Шотландия выиграла у Англии со счетом 3 : 0, ему пришла в голову идея найти счет в остальных пяти матчах из этой таблицы. Он успешно справился со своей задачей.

Не могли бы и вы определить, сколько голов забила и пропустила в свои ворота каждая из команд в каждом матче?

441. Сломанная линейка. Вот интересная головоломка, которая напоминает (хотя в действительности существенно отличается) одну из классических задач Баше о гире, разрезанной на куски, с помощью которых удается определить вес любого груза величиной от 1 фунта до полного веса всех кусков. В нашем случае у одного человека есть линейка, у которой обломился конец, так что ее длина стала равной 33 см. Большинство делений на линейке стерлось, так что разобрать можно только 8 из них. Тем не менее с помощью линейки можно измерить любое целое число сантиметров от 1 до 33.

Где расположены сохранившиеся деления?

Для примера я привел на рисунке линейку длиной 13 см с четырьмя делениями. Если мне нужно отмерить 4 см, то я отмеряю 1 и 3 см; если 8 см, то 6 и 2 см; если 10 см, то 3, 1 и 6 см и т. д. Разумеется, нужное измерение следует сделать, приложив линейку один раз; в противном случае мы могли бы получить любое число сантиметров, последовательно отмеряя до 1 см, что лишило бы головоломку всякого смысла.

442. Шесть коттеджей. Дорога длиной 27 км окружает заброшенный и безлюдный участок. Вдоль нее расположены 6 коттеджей (см. рисунок) таким образом, что одни из них находятся от других на расстоянии 1, 2, 3 и т. д. до 26 км включительно. Например, Браун может быть в 1 км от Стиггинса, Джонс — в 2 км от Роджерса, Вильсон — в 3 км от Джонса и т. д. Разумеется, ходить друг к другу обитатели домов могут как по часовой стрелке, так и против нее.

Не могли бы вы расположить коттеджи на таких расстояниях один от другого, чтобы удовлетворить условиям задачи? Рисунок умышленно сделан так, чтобы он не мог служить «подсказкой».

443. Четыре фишки вдоль прямой. Перед вами доска из 36 квадратов, на которой 4 фишки расположены вдоль одной прямой таким образом, что любой квадрат доски оказался на одной горизонтали, вертикали или диагонали по крайней мере с одной из фишек. Иначе говоря, если рассматривать наши фишки как шахматных ферзей, то каждый квадрат доски находится под ударом по крайней мере одного ферзя. Головоломка состоит в том, чтобы выяснить, сколькими способами можно расставить 4 фишки вдоль прямой так, чтобы каждый квадрат оказался на одной линии с какой-то из фишек.

Две позиции считаются различными, если наборы из 4 квадратов, занятых фишками, по крайней мере частично не совпадают. Так, в приведенном примере все фишки можно передвинуть вправо на соседний столбец или же расположить их на любой из двух центральных строк. Мы нашли, таким образом, 4 различных решения, о которых можно сказать, что они получаются друг из друга при поворотах и отражениях. Помните, что фишки все время должны располагаться вдоль некоторой прямой. Эта головоломка не слишком трудна и в то же время достаточно занимательна.

444. Мухи на оконном стекле. Перед вами окно, застекленное с помощью 81 стеклянного квадратика. На нем сидят 9 мух, причем ни одна муха не находится с другой на одной и той же прямой по вертикали, горизонтали или диагонали. Шесть из них совсем сонные и сидят не двигаясь, зато каждая из 3 остальных переползает на соседний квадрат. И все же после такого перемещения ни одна муха по-прежнему не находится на одной прямой с какой-либо из остальных.

Какие 3 мухи переползли и на какие квадраты (свободные в настоящий момент)?

445. За ленчем. Клерки фирмы «Пилкинс энд Попинджей» решили, что они каждый день будут садиться по трое за один и тот же стол до тех пор, пока какие-либо 3 человека не будут вынуждены сесть за этот стол вторично. Такое же число клерков фирмы «Рэдсон, Робсон энд Росс» решили проделать то же самое, но только не по 3, а по 4 человека. Когда они начали осуществлять свой план, то обнаружилось, что клерки второй фирмы могут продолжать пересаживаться ровно втрое дольше, чем их соседи.

Какое наименьшее число клерков могло служить в каждой из двух фирм?

446. «Кипучая» головоломка. Сколькими способами буквы слова EFFERVESCES[25] можно разместить вдоль прямой так, чтобы два Е не оказались рядом? Разумеется, мы не различаем между собой одинаковые буквы вроде FF, так как, переставляя их между собой, мы не получим нового размещения.

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

447. Квадрат из плиток. Имеется 20 плиток, окрашенных в одни и те же 4 цвета (взаимное расположение цветов показано на рисунке разной штриховкой).

Головоломка состоит в том, чтобы, выбрав 16 плиток, составить из них квадрат. Четвертушки одного цвета должны примыкать друг к другу: белые к белым, черные к черным и т. д. Нетрудно вырезать квадраты из бумаги или картона и покрасить их в любые цвета, точно соблюдая при этом их взаимное расположение, указанное на рисунке.

448. Головоломка с тридцатью шестью буквами. Если вы попытаетесь заполнить изображенный здесь квадрат повторяющимися буквами А, В, С, D, E, F так, чтобы ни одно А не находилось на одной горизонтали, вертикали или диагонали с другим А, ни одно В — с другим В, ни одно С — с другим С и т. д., то обнаружите, что сделать это невозможно.

Головоломка состоит в том, чтобы заполнить максимально возможное количество клеток. Вероятно, читатель оставит незаполненными больше клеток, чем нужно.

449. Десять бочек. У купца было 10 бочек сахарного песку, из которых он сложил пирамиду, как показано на рисунке. На каждой из бочек, кроме одной, был проставлен свой номер. Оказалось, что купец случайно разместил бочки так, что сумма номеров вдоль каждого ряда равнялась 16.

Не могли бы вы переставить бочки таким образом, чтобы сумма номеров вдоль каждого ряда равнялась наименьшему возможному числу? Разумеется, центральная бочка (на рисунке ею случайно оказалась бочка под номером 7) в счете не участвует.

450. Сигнальные огни. Два шпиона на противоположных берегах реки придумали способ ночной сигнализации с помощью рамки (вроде той, что изображена на рисунке) и трех ламп. Каждая из ламп могла светиться белым, красным или зеленым светом. Шпионы разработали код, в котором каждый сигнал что-то означал. Вы, разумеется, понимаете, что одна лампа, на какой крючок ее ни повесь, будет иметь только одно значение. Две лампы, подвешенные на верхние крючки 1 и 2, неотличимы от двух ламп, подвешенных на крючки 4 и 5. Две красные лампы на крючках 1 и 5 можно отличить от ламп на крючках 1 и 6, а две лампы на крючках 1 и 2 отличаются от двух ламп на крючках 1 и 3.

Учитывая все это многообразие положений ламп на крючках и цвета сигналов, ответьте, сколько можно послать различных сигналов?

451. Скованные узники. Жили-были когда-то 9 очень опасных узников, за которыми приходилось внимательно наблюдать. Каждый будний день их выводили на работу, сковав между собой, как показано на рисунке, который, кстати сказать, сделал один из охранников. Никакие два человека не бывали скованы между собой дважды в течение одной и той же недели. На рисунке показано, как узников выводят на работу по понедельникам.

Не могли бы вы разбить узников на тройки в оставшиеся пять рабочих дней недели?

Можно заметить, что номер 1 не может быть вновь скован с номером 2 (справа или слева), номер 2 — с номером 3, но, разумеется, можно сковать номер 1 с номером 3. Следовательно, наша головоломка весьма отличается от старой головоломки с 15 школьницами. Тот, кто потратит драгоценные часы досуга на поиски решения этой увлекательной головоломки, будет с лихвой вознагражден за свои усилия.

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

Поскольку водить машину умели только сам полковник, дядя Джейбз и Джордж, то потребовалось всего лишь немножко поразмыслить.

Быть может, читатель сам захочет найти то решение, которое все семейство Крэкхэмов признало к концу дня правильным?

453. Соревнование по стрельбе из лука. Три стрелка из лука, у каждого из которых имеется по 6 стрел, поражают мишень, изображенную на рисунке. Попадание в «яблочко» оценивается в 40 очков, а в каждое следующее от центра кольцо соответственно — в 39, 24, 23, 17 и 16 очков. Результаты оказались такими: мисс Дора Талбот — 120 очков, Реджи Уотсон — 110 очков, миссис Финч — 100 очков. Каждая стрела попала в цель, но в «яблочко» попала только одна стрела.

Не могли бы вы, исходя из этих сведений, определить, куда именно попали стрелы каждого из участников?

454. Стрельба по мишени. Однажды к вечеру полковник Крэкхэм посетил Слокомбский клуб токсофилов, где он откопал следующую небольшую задачку.

Три спортсмена выпустили по 6 стрел в мишень. Их результаты показаны на рисунке, где видно, что все стрелы попали в цель. Попадание в «яблочко» оценивается в 50 очков, попадание в ближайшее к «яблочку» кольцо — в 25 очков, а попадания в следующие по порядку кольца — в 20, 10, 5, 3, 2 и 1 очко. По пробоинам видно, что одна стрела поразила «яблочко», две попали в 25, три — в 20, три — в 10, три — в 1, а каждое из остальных колец было поражено двумя стрелами. В результате все три спортсмена набрали одинаковое число очков.

На следующее утро полковник спросил своих домашних, куда попали стрелы каждого из участников. Много ли времени потребуется читателю, чтобы дать правильный ответ?

455. Сакраменто — край богатый. Семья Крэкхэмов уютно устроилась в «Голубом борове» в Подлбери. Здесь им посчастливилось встретить еще одного постояльца, который явно бился над решением какой-то головоломки. Полковник вступил с ним в беседу и выяснил, что головоломка называется «Сакраменто — край богатый».

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

Какую наибольшую сумму можно собрать?

456. Семеро детей. Четыре мальчика и три девочки садятся случайным образом в один ряд.

Какова вероятность того, что два ребенка на концах ряда окажутся девочками?

Примечания:

1

В США находятся в обращении следующие мелкие монеты: полдоллара, четверть доллара, 10 центов, 5 центов и 1 цент. — Прим. перев.

2

Метродор (330–278/277 г. до н. э.) — древнегреческий философ, ученик и друг Эпикура. — Прим. перев.

19

Туз соответствует одному очку. — Прим. перев.

20

По-видимому, задача относится ко времени действия в США «сухого закона». — Прим. перев.

21

Здесь лежит Джон Рени (англ.).

22

Под росчерком здесь понимается одно непрерывное движение карандаша в заданном направлении. Если вы рисуете ломаную линию, то на каждый отрезок этой ломаной тратится по одному росчерку. Всю окружность также можно нарисовать за один росчерк. — Прим. перев.

23

Это соглашение оправдано следующими доводами. Если мы можем определять границы между странами только по цвету, то в случае, когда общий участок границы двух стран не сводится к одной точке, эти страны обязаны иметь разные цвета, иначе мы не сможем найти границу между ними. Если же границы двух стран соприкасаются только в одной точке, мы спокойно можем покрасить эти страны одной и той же краской; при этом путаницы с границами не возникнет. — Прим. перев.

24

Гольф — спортивная игра с мячом. На участке, выделенном для игры, размечаются 9 или 18 дорожек длиной от 145 до 470 м и шириной 30-40 м. В конце каждой дорожки делается лунка диаметром 11 см и глубиной 10 см, обозначаемая флажком. Мяч из литой резины имеет 14 см в окружности. Задача игроков — ударами специальной биты (клэба) прогнать мяч поочередно по всем дорожкам и загнать его в лунки. Выигрывают участники, сделавшие это наименьшим числом ударов. — Прим. перев.

25

Пузырьки воздуха, образующиеся при кипении (англ.). — Прим. перев.