своих курсов лекций, озаглавленном «Головоломки и парадоксы». Тогда-то один из моих студентов заметил мне: «Знаете, профессор, ваша книга — особенно ее третья и четвертая части — читается прямо как какой-то математический роман. Ничего подобного я раньше не встречал!». Мне кажется, что слова «математический роман» в этом случае весьма уместны. Действительно, большая часть книги написана в форме художественного повествования. Поэтому ее вполне можно было бы назвать как-то вроде «Тайна сейфа из Монте-Карло» — ведь в последней части книги речь идет о расследовании, в процессе которого инспектор Крейг из Скотланд-Ярда пытается подобрать комбинацию цифр, позволяющую открыть замок одного из сейфов в Монте-Карло, и тем предотвратить катастрофу. Когда все его усилия вскрыть сейф оказываются безуспешными, инспектор возвращается в Лондон, где по счастливой случайности вновь сталкивается с блестящим и чудаковатым изобретателем цифровых кодирующих машин. Они приглашают еще и специалиста по математической логике, и вскоре все трое погружаются в глубокие воды потока, ведущего в самое сердце великого открытия Гёделя. Конечно же, замок сейфа из Монте-Карло оказывается «гёделевым», а его modus ореrandi[1] прекрасно иллюстрирует фундаментальную идею Гёделя, влияние и результаты которой обнаруживаются во многих научных теориях, связанных с таким удивительным явлением, как процесс самовоспроизведения.
В конечном счете исследования Крейга и его друзей приводят к весьма примечательным математическим открытиям, не известным до настоящего времени ни ученому миру, ни тем более широкой публике, — это так называемые «законы Крейга» и «законы Фергюссона», которые впервые преданы гласности на страницах книги. Несомненно, они должны заинтересовать как любителей математики, так и логиков, лингвистов и специалистов по вычислительной технике.
Книгу эту я писал с огромным удовольствием; хотелось бы, чтобы с таким же удовольствием ее и читали. Собираюсь написать еще несколько книг в том же духе. Наконец, я хочу поблагодарить моего редактора Энн Клоуз и технического редактора Мелвина Розенталя за ту неоценимую помощь, которую они мне оказали.
Часть первая. Принцесса или тигр?
Задачки с подвохом — старые и новые
Начнем с нескольких арифметических и логических задачек. Одни из них новые, а другие могут оказаться знакомыми читателю.
1. Сколько денег? Предположим, что у вас и у меня имеется одинаковая сумма денег. Сколько денег я должен вам дать, чтобы у вас стало на 10 долларов больше, чем у меня?
2 Задача о конгрессменах. В некоем конгрессе заседают сто политических деятелей. Каждый из них либо продажен либо честен. Нам известны следующие два факта:
1) По крайней мере один из конгрессменов является честным
2) Из каждой произвольно выбранной пары конгрессменов по крайней мере один продажен.
Можно ли с помощью этих двух утверждении определить, сколько конгрессменов в этом конгрессе будут честными, а сколько — продажными?
3. Старое вино в не слишком новые мехи. Бутылка вина стоит 10 долларов. Вино на 9 долларов дороже бутылки. Сколько стоит пустая бутылка?
4. Какова прибыль? Самое удивительное в этой задаче, что разные люди решают ее различными путями, каждый получает свой ответ и каждый с пеной у рта готов доказывать, что именно его ответ правильный.
Торговец купил некий товар за 7 долларов, продал его за 8, потом вновь купил за 9 долларов и опять продал его за 10. Какую прибыль он получил?
5. Задача о десяти любимцах. Самым поучительным в этой задаче является то, что, хотя она легко решается посредством элементарных алгебраических выкладок, ее можно решить вообще без всякой математики — лишь с помощью рассуждений. Более того, решение, подсказанное здравым смыслом, по- моему, гораздо интереснее и уж, конечно, более творческое, а также содержит больше информации, чем сугубо математическое решение.
Итак, десяти собакам и кошкам скормили 56 галет. Каждой собаке досталось 6 галет, каждой кошке — пять. Сколько было собак и сколько кошек?
Любой читатель, хотя бы немного знакомый с алгеброй, легко найдет ответ. Можно решить эту задачу и методом проб и ошибок. Ясно, что для числа кошек в задаче есть 11 возможностей (от 0 до 10).
Перебрав все, легко найти правильный ответ. Однако если подойти к этой задаче толково, то оказывается, что есть еще одно удивительно простое решение, для которого не нужно ни алгебры, ни перебора вариантов. Поэтому я советую тем из вас, кто получит ответ ПО-СВОЕМУ, заглянуть в решение, приведенное в конце главы.
6. Большие и маленькие птицы. Вот еще одна задача, которая решатся как алгебраически, так и с помощью рассуждений; я и тут предпочитаю здравый смысл. В зоомагазине продают больших и маленьких птиц. Большая птица вдвое дороже маленькой. Леди, зашедшая в магазин, купила 5 больших птиц и 3 маленьких, Если бы она вместо этого купила 3 больших птицы и 2 маленьких, то потратила бы на 20 долларов меньше. Что стоит каждая птица?
7. Как плохо быть рассеянным. Следующая история произошла на самом деле.
Как хорошо известно, с вероятностью более 50 % можно утверждать, что в группе, состоящей как минимум из 23 человек, всегда найдется по крайней мере двое, у которых день рождения падает на одно и то же число. В свое время я преподавал математику в Принстонском университете и как-то занимался со студентами элементарной теорией вероятностей. Я объяснил своим слушателям, что если число людей в группе увеличить с 23 до 30, то вероятность того, что в ней окажутся по крайней мере двое, которые родились в один и тот же день, окажется близка к единице.
— Но, — продолжал я — поскольку вас здесь всего 19, то вероятность того, что у двоих из вас дни рождения совпадают, будет гораздо меньше 50 %.
Тут один из студентов поднял руку:
— Бьюсь об заклад, профессор, что по крайней мере у двоих из присутствующих здесь дни рождения должны совпасть.
— С моей стороны было бы не очень честно принимать ваше пари, — ответил я. — Ведь теория вероятностей целиком на моей стороне.
— Это не имеет значения, — упорствовал студент. — Я все-таки готов с вами поспорить!
— Ну, ладно, — согласился я, надеясь преподать юному скептику достойный урок. Затем я стал по очереди опрашивать студентов, с тем, чтобы каждый назвал дату своего рождения. Не успели мы выслушать и половину присутствующих, как вдруг вся аудитория, в том числе и я, покатились со смеху по поводу моей бестолковости.
Юноша, который так самоуверенно вступил со мной в спор, не знал даты рождения никого из присутствующих, за исключением, конечно, самого себя. Не догадаетесь ли вы, почему он был так уверен в своей правоте?
8. Республиканцы и демократы. В одной фирме каждый служащий является либо республиканцем, либо демократом. Как-то раз один из демократов решил перейти в республиканцы, и после того, как это произошло, в фирме оказалось ровно столько же республиканцев, сколько и демократов. Спустя несколько
