Генри Дьюдени - Пятьсот двадцать головоломок

434. Всего имеется 39 147 416 разных способов. Прибавьте 3 к числу членов (что даст 618) и вычтите 1 из числа партий (что даст 3). Тогда ответом будет число способов, которыми можно выбрать 3 предмета из 618, то есть

Общее решение таково. Пусть p — число партий, а m — число членов парламента. Число способов равно числу сочетаний из m + p - 1 объектов по p - 1.

435. Если нет никаких ограничений, то 10 человек могут разместиться на прямой 10! = 3 628 800 способами. Сколько из этих перестановок запрещено? Будем рассматривать двух человек одной национальности, заключенных в скобки, как единое целое.

1. Тогда (Ан, Аи) (Ш, Ш) (У, У) Ф Ит Ис Ам можно переставить 7! × 2 3= 40 320 способами. Помните, что два Ан могут меняться местами внутри скобок, где бы последние ни расположились, и то же самое верно для Ш и У. Отсюда и появляется 2 3.

2. Однако мы можем рассмотреть (Ан, Ан) (Ш, Ш) У У Ф Ит Ис Ам, где два У не объединены скобками, а «свободны». Это даст нам 8! × 2 2вариантов, но мы должны исключить отсюда результат пункта 1, чтобы не сосчитать некоторые перестановки дважды. Получаем 120 960.

3. Поступим аналогичным образом с двумя «свободными» Ш. Получим 120 960.

4. Поступим так же с двумя «свободными» Ан. Получим 120 960.

5. Но мы можем рассмотреть (Ан, Ан) Ш Ш У У Ф Ит Ис Ам, где и Ш, и У «свободны». Это даст нам 9! × 2 случаев, из которых мы должны вычесть результаты пунктов 1, 2 и 3 по очевидным теперь причинам. Получим 443 520.

6. Когда в скобки заключены только Ш, вычтем результаты пунктов 1, 2 и 4. Получим 443 520.

7. Когда в скобках оставлены только У, вычтем результаты пунктов 1, 3 и 4. Получим 443 520.

Сложим результаты семи пунктов и получим при этом 1 733 760. Теперь из самого первого результата вычтем полученное число, что даст нам верный ответ, равный 1 895 040 способам.

436. Головоломку можно решить за 9 переправ следующим образом:

1) мистер и миссис Вебстер переправляются вместе;

2) миссис Вебстер возвращается;

3) переправляются мать и невестка;

4) возвращается мистер Вебстер;

5) переправляются тесть и сын;

6) возвращается невестка;

7) переправляются мистер Вебстер с невесткой;

8) возвращается мистер Вебстер;

9) мистер и миссис Вебстер переправляются вместе.

437. Обозначим трех миссионеров через М м м, а трех каннибалов через К к к; прописными буквами обозначены миссионер и каннибал, умеющие грести. Тогда переправляются К к; К возвращается на лодке; переправляются К к; К возвращается; переправляются М м; возвращаются М к; переправляются М К; возвращаются М к; переправляются М м; возвращается К; переправляются К к; К возвращается; переправляются К к; при этом все переправляются через реку, не нарушая заданных условий.

[Задачи о переправах через реку этого и предыдущего типа решаются с помощью простого метода из теории графов. См. гл. 35 книги М. Гарднера «Математические досуги» (М., изд-во «Мир», 1972). — М. Г. ]

438. Двое детей гребут к другому берегу. Один из них вылезает, а другой возвращается назад. Один солдат переправляется, вылезает, а мальчик возвращается назад. Таким образом, чтобы переправить на другой берег одного взрослого, лодка должна 4 раза проплыть от берега до берега. Поэтому ей пришлось сделать 4 × 358 = 1432 рейса, чтобы переправить офицера и 357 солдат, причем лодка в конце концов снова оказалась у детей.

439. Можно составить следующую таблицу:

440. Из таблицы можно сразу определить, что Англия победила Ирландию и сыграла вничью с Уэльсом. Поскольку А сыграла в этих матчах с общим счетом 2 : 0, то она должна была победить со счетом 2 : 0, а вничью сыграть со счетом 0 : 0. Таким образом, нам все известно про А и остается только определить результаты трех матчей: У с И, Ш с И и Ш с У. Шотландия пропустила только 1 гол от У или И. И забила только 1 гол в ворота У или Ш. Допустим, что в ворота Ш. Тогда У не забил ни одного гола в ворота Ш. Но У всего забил 3 гола; следовательно, все они были забиты в ворота И. Получается, что в ворота И было забито 6 голов: 2 — А, 3 — У (если принять, что И забила гол в ворота Ш) и оставшийся гол — Ш. Но поскольку мы приняли, что И забила 1 гол в ворота Ш, матч между этими командами должен был закончиться вничью. Однако из таблицы видно, что в этом матче выиграла Ш и, следовательно, И не могла забить гол в ворота Ш. Таким образом, гол в ворота Ш забил У. А поскольку У всего забил 3 гола, то остальные 2 были забиты в ворота И, которая свой единственный гол забила в ворота У. Окончательно мы получаем, что Ш выиграла у У со счетом 2 : 1, у И со счетом 2 : 0, а У выиграл у И со счетом 2 : 1.