Есть идея!

Дихотомия (последовательное разбиение множества на 2 части), играющая важную роль в вычислительной технике и теории автоматической сортировки данных, лежит в основе задачи об угадывании номера телефона Элен и позволяет читателю войти в круг вопросов, связанных с двоичной системой счисления. Принцип «птичка в клетке», известный также под названием принципа Дирихле, позволяет доказывать многие важные факты из теории чисел. Мы используем его для доказательства двух забавных утверждений: о бумажных долларах и о числе волос на голове человека. Свойство двух целых чисел быть взаимно простыми (не иметь общих делителей, кроме единицы) позволяет доказать, что, за исключением 12 часов, часовая, минутная и секундная стрелки часов никогда не совпадают (обычно это вычисление доказывают, проделывая довольно громоздкие выкладки).

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

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

Разбитые грампластинки

Больше всего на свете Боб и Элен любили всякого рода головоломки. Особенно им нравилось ставить в тупик друг друга и своих друзей каверзными вопросами.

Однажды, когда Боб и Элен проезжали мимо магазина грампластинок, Боб задал Элен вопрос.

Боб. Ты все еще собираешь пластинки с джазовой музыкой?

Элен. Нет, половину всех пластинок и еще полпластинки я подарила Сьюзен.

Элен. Половину оставшихся пластинок и еще полпластинки я подарила Джо.

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

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

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

Какая мысль пришла Бобу в голову?

Половинки целого

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

По словам Элен, у нее после того, как она преподнесла свой второй подарок, осталась 1 пластинка. Значит, до того, как она подарила часть своих пластинок Джо, у нее должны были остаться 3 пластинки. Половина от 3 составляет 3/2, а 3/2 + 1/2 = 2, поэтому Элен подарила Джо 2 пластинки, после чего у нее осталась 1 пластинка. Продолжая решать задачи «задним ходом», нетрудно установить, что сначала у Элен было 7 пластинок и что 4 пластинки она подарила Сьюзи.

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

Новые головоломки того же типа мы получим, варьируя параметры задачи. Предположим, например, что Элен каждый раз дарит кому-нибудь половину своих пластинок и еще полпластинки, проделывает это не дважды, а трижды и остается не с одной пластинкой, а без единой пластинки. Сколько пластинок было у нее сначала? Возможно, вам покажется странным, что ответ остается прежним — 7 пластинок, но удивительного здесь ничего нет: в третий раз Элен дарит последнюю оставшуюся у нее пластинку. А сколько пластинок было у нее сначала, если она дарит каждый раз половину своих пластинок и еще полпластинки и проделывает эту процедуру 4 раза, после чего у нее остается 1 пластинка? А если Элен дарит пластинки 5 раз? Какого рода последовательность порождают возникающие в этой серии задач числа?