Есть идея!

Неожиданные решения арифметических задач

Говоря об арифметике, разные люди вкладывают в это понятие различное содержание. Мы будем понимать под арифметикой все, что так или иначе связано с изучением свойств целых чисел и операций сложения, вычитания, умножения и деления, производимых над числами.

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

Такие арифметические теоремы, как «2 + 1 = 3», созревали и становились достоянием умов на протяжении нескольких столетий. Если бы мы могли прокрутить назад пленку, на которой была бы запечатлена история человечества, то вряд ли нам удалось найти какой-то век, о котором можно было бы с уверенностью сказать: «Именно тогда человечество открыло арифметику». Маленькие дети овладевают понятием числа так же постепенно и незаметно. В один прекрасный день ребенок может впервые заявить изумленным родителям: «Один плюс один — два», но смысл этого утверждения ясен малышу задолго до того, как он выскажет свою первую арифметическую теорему.

Все истинные теоремы арифметики следуют непосредственно из аксиом и определений числовой системы, но это отнюдь не означает, будто истинность или ложность любого арифметического утверждения легко распознается на слух. Если кто-нибудь скажет, что при умножении 12345679 на 9 получается 111111111, вы можете не верить ему до тех пор, пока сами не умножите одно число на другое. Существуют арифметические теоремы, которые просто сформулировать, но так трудно доказать, что никто пока не знает, верны ли они. Примерам таких утверждений может служить знаменитая гипотеза Гольбаха: всякое четное число больше 2 представимо в виде суммы двух простых чисел. Никому до сих пор не удалось ни доказать ее, ни построить контрпример.

В этой главе мы рассмотрим несколько задач о числах, допускающих неожиданно простые решения, додуматься до которых не так-то просто. При выборе задач мы отдавали предпочтение таким, которые при всей элементарности служили бы ступенькой, позволяющей читателю подняться на более высокую ступень арифметики, получившей название теории чисел. Например, рассказ-задача «Разбитые грампластинки» вводит в круг простейших идей диофантова анализа — решения уравнений в целых числах. Другая задача «Один лишний» познакомит вас с важным понятием наименьшего общего кратного и интересным фокусом, основанным на замечательной «китайской теореме об остатках».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Один мальчик с увлечением занимался разведением золотых рыбок, потом это занятие ему надоело и он решил продать всех своих рыбок. Свое решение он осуществил в 5 этапов:

1. Продал половину всех своих рыбок и еще полрыбки.

2. Продал треть оставшихся рыбок и еще треть рыбки.

3. Продал четверть оставшихся рыбок и еще четверть рыбки.

4. Продал пятую часть оставшихся рыбок и еще одну пятую рыбки.

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

А вот еще одна разновидность задач того же типа.

У одной дамы было в сумочке несколько купюр достоинством в 1 доллар каждая. Других денег у нее с собой не было.

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

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

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

Ответ приведен в конце книги.

Заметим, что во всех вариантах в условиях задачи непременно говорится, сколько грампластинок, золотых рыбок или купюр остается у действующего лица по окончании всех перипетий. Во многих случаях ответ задачи можно получить и без такой информации, но для этого пришлось бы решать в целых числах некоторые неопределенные уравнения. Наиболее известная задача такого рода легла в основу рассказа американского писателя Бена Эймса Уильямса «Кокосовые орехи».

Действие рассказа происходит на острове, на который после кораблекрушения попадают 5 человек и 1 обезьяна. Первый день они собирают кокосовые орехи. Ночью один из людей просыпается и решает забрать причитающуюся ему долю орехов. Он раскладывает орехи на 5 одинаковых кучек, отдает лишний орех обезьяне и, спрятав свою долю, укладывается снова спать.

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

Сколько кокосовых орехов было собрано первоначально?

Задача допускает бесконечно много решений. Наименьшее из них — 3121 орех. Решить задачу не очень просто.

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

Лохнесское чудовище

Боб. Лохнесское чудовище имеет в длину 20 м и еще половину своей длины. Чему равна его длина?

Элен. Дай подумать. Двадцать и половина от двадцати — итого тридцать. Значит, лохнесское чудовище имеет в длину 30 м.

Боб. Не узнаю тебя, Элен! Твой ответ противоречит условию задачи, а ты этого не замечаешь. Как может лохнесское чудовище иметь в длину и 20 м и 30 м одновременно?

Элен. Ты прав, я ошиблась. Условие задачи означает, что длина лохнесского чудовища равна сумме 20 м и половины его длины. Теперь мне все стало ясно.

Чему, по-вашему, равна длина лохнесского чудовища?

По словам Боба, лохнесское чудовище имеет в длину 20 м и еще половину своей длины, то есть длина чудовища равна сумме 2 слагаемых: 20 м и половины длины чудовища. Разделите мысленно длину чудовища пополам. Если вся длина равна сумме 2 слагаемых, из которых одно равно половине длины, а другое 20 м, то на 20 м приходится другая половина длины. Следовательно, полная длина составляет 40 м.

Задача Боба допускает простое алгебраическое решение: если x — полная длина лохнесского чудовища, то

x = 20 + x/2.

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

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

Один лишний

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

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

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

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

Хотя это было не ее дело, Элен подошла к дирижеру.

Элен. Позвольте мне дать вам один совет?

Дирижер. Мне сейчас не до вас, милая девушка! И без того голова идет кругом.

Элен. Хоть вы и не очень вежливы, я все равно скажу вам, что нужно делать. Перестройте музыкантов в колонну по пять!

Боб. Я как раз собирался предложить то же самое!

Когда оркестр перестроили в колонну по пять, все шеренги оказались заполнены.

Сколько музыкантов было в оркестре?

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

Сделать это можно следующим образом. Пусть N — число музыкантов в оркестре. Мы знаем, что при делении на 2, 3 и 4 оно дает остаток 1 (живым воплощением остатка служит Спиро, в одиночестве марширующий вслед за оркестром). Наименьшее число, обладающее этим свойством, на 1 больше наименьшего общего кратного (НОК) чисел 2, 3 и 4, то есть числа 12. Рассмотрим теперь все числа, кратные 12. Увеличив любое из них на 1, мы получим число, которое при делении на 2, 3 и 4 дает остаток 1.

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

13, 25, 37, 49, 61, 73, 85, 97, 109, 121, 133, 145, …

Поскольку число 145 слишком велико для школьного оркестра, то N равно либо 85, либо 25. Имеющаяся у нас информация не позволяет отдать предпочтение какому-нибудь из этих двух чисел.

Хорошим вариантом предыдущей задачи может служить следующая задача. При перестроениях оркестра в колонну по два, три и четыре в последней шеренге каждый раз недостает одного человека, а при построении в колонну по пять все шеренги оказываются заполненными. Сколько музыкантов в оркестре? На этот раз мы должны выписать последовательность чисел, которые на 1 меньше кратных двенадцати и делятся на 5 без остатка: 35, 95, 155, …

Следующий, более трудный вариант задачи принадлежит известному американскому мастеру головоломок Сэму Лойду. По традиции в день св. Патрика члены ирландской общины проводят в Нью-Йорке торжественное шествие. В тот год, о котором рассказывается в новелле Сэма Лойда, Великий маршал ордена св. Патрика безуспешно пытался выстроить участников шествия в колонну по 10, 9, 8, 7, б, 5, 4, 3 и 2 человека, но каждый раз в последней шеренге недоставало одного человека. Суеверные участники шествия решили даже, что среди них незримо витает дух скончавшегося незадолго до дня св. Патрика хромого Кейси, без которого не обходилось ни одно шествие. Вконец отчаявшись, Великий маршал приказал участникам шествия построиться в колонну по одному. Сколько людей приняло участие в шествии, если ирландская община в Нью-Йорке насчитывала в ту пору не более 7000 человек? Задача Сэма Лойда — прекрасный пример на нахождение НОК нескольких чисел. НОК чисел 10, 9, 8, 7, 6, 5, 4, 3 и 2 равно 2520. Вычтя из этого числа скончавшегося от пневмонии хромого Кейси, мы узнаем, что в шествии приняло участие 2519 человек.

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

Старушка несла на базар корзину яиц. Испугавшись пронесшейся мимо лошади, она выронила из рук корзину, и часть яиц разбилась. На вопрос, много ли яиц было в корзине, старушка ответила, что не сильна в арифметике и точное число яиц назвать не может. Правда, потом она все-таки вспомнила, что когда пересчитывала яйца парами, тройками, четверками и пятерками, у нее оставались лишние яйца (1, 2, 3 и 4 соответственно). Сколько яиц старушка несла на базар?

На первый взгляд кажется, что эта задача намного труднее предыдущих. В действительности же она ничем не отличается от первой части нашей рой задача, так как остаток от деления каждый раз на единицу меньше делителя. Решается она таким же способом: нужно найти НОК чисел 2, 3, 4, 5 и вычесть из него единицу.

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

Фокусник садится в кресло спиной к аудитории. Кто-нибудь из зрителей задумывает любое число не больше 1000, делит задуманное число на 7, 11 и 13, называя каждый раз вслух остаток от деления.

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

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

где a, b и c — остатки от деления задуманного числа на 7, 11 и 13. Задуманное число равно остатку от деления числителя формулы на знаменатель.

Секрет формулы раскрывается просто. Первый коэффициент равен наименьшему кратному произведения bc, которое на единицу больше числа, кратного a. Найти такое число можно по определенным правилам, но когда делители a, b и c не слишком велики,

как в нашем случае, то проще всего действовать прямым подбором: выписать кратные произведения ac (143, 286, 429, 572, 715, …) и найти среди них то, которое при делении на a дает остаток 1. При a = 7 таким кратным является число 715.

Аналогичным образом вычисляются и остальные коэффициенты. Второй коэффициент равен наименьшему кратному произведения ac, которое на единицу больше числа, кратного b, а третий коэффициент равен наименьшему кратному произведения ab, которое на единицу больше числа, кратного c. В знаменателе формулы стоит просто произведение abc. Пользуясь этим алгоритмом, вы можете заготовить «тайную» формулу для любого набора взаимно простых чисел (то есть чисел, не имеющих общих делителей, кроме единицы). Сами числа не обязательно должны быть простыми.

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

В качестве упражнения попробуйте вывести «тайную» формулу для упрощенного варианта того же фокуса, восходящего к Сунцзу, китайскому математику, жившему в 1 в., одному из тех ученых, в честь которых теорема об остатках получила название китайской. Задумывать разрешается любое число от 1 до 105. Делить задуманное число следует на 3, 5 и 7. «Тайная» формула оказывается в этом случае столь простой, что после некоторой тренировки вы сможете проделывать все необходимые вычисления «в уме».

Глаза и ноги

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

Выйдя из зоопарка, Боб обратился к Элен.

Боб. Ты не пересчитала жирафов и страусов?

Элен. Нет, а сколько их было?

Боб. Сосчитай сама. Всего у страусов и жирафов было 80 глаз и 44 ноги.

Элен сразу сообразила: 30 глаз означает, что в вольере было 15 животных.

Элен. Я могла бы перебрать все возможные случаи от 6 жирафов и 15 страусов до 15 жирафов и 0 страусов, но в этом нет надобности.

Элен. Если бы все 15 животных ходили на 2 ногах, то всего у них было бы 30 ног.

Элен. Но ты, Боб, сказал, что у 15 животных 44 ноги, поэтому 14 ног «лишних». Они могут принадлежать только жирафам. Значит, в вольере 7 жирафов.

Боб. Все правильно! А раз в вольере 7 жирафов, то страусов должно быть 8.

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

А вот забавная головоломка, придуманная по образу и подобию предыдущей задачи, но требующая для решения иного подхода. На арене небольшого цирка выступает группа наездников. Если пересчитать участников номера (лошадей и всадников) по головам и ногам, то всего наберется 18 голов и 50 ног. Кроме того, в зверинце при цирке содержатся дикие животные. Если пересчитать их по головам и ногам, то получится 11 голов и 20 ног. Среди них четвероногих вдвое больше, чем двуногих. Сколько наездников и лошадей выступает в цирке и сколько диких животных содержится в его зверинце?

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

Удастся ли вам решить задачу самостоятельно, не заглядывая в конец книги?

Столкновение на полном ходу

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

По дороге Боб придумал для Элен хорошую задачку.

Боб. Видишь вой тот грузовик впереди? Он гонит вовсю, но я постараюсь его догнать.

Боб. Предположим, что грузовик делает 65 км/ч, а я еду со скоростью 80 км/ч.

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

Боб. Если шофер грузовика и я будем выдерживать каждый свою скорость и я не сверну, мы заведомо врежемся в грузовик. Вот тебе и задачка, Элен: на каком расстоянии от грузовика мы будем за 1 мин до столкновения?

Элен. Ты мог бы придумать задачку потруднее. За 1 мин до столкновения нас будет разделять 250 м.

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

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

Грузовик развивает скорость 65 км/ч, а Боб едет со скоростью 80 км/ч. Следовательно, Боб движется относительно грузовика со скоростью 15 км/ч, или 15 000 м/ч, что составляет 250 м/мин. Значит, за минуту до столкновения легковая машина, в которой едут Боб и Элен, находится в 250 м позади грузовика.

Мы знаем также, что, когда Боб закончил рассказывать Элен задачу, их автомашина находилась в 1,5 км позади грузовика, но эта информация не нужна для решения задачи: ответ получается одним и тем же независимо от начального расстояния между машинами.

Следующие две классические головоломки также решаются «обратным ходом».

1. Два космических корабля сближаются, двигаясь по прямой навстречу друг другу. Один корабль летит со скоростью 8 км/мин, другой — со скоростью 12 км/мин. Предположим, что в некоторый момент времени корабли находятся на расстоянии ровно 5000 км друг от друга. На каком расстоянии они будут находиться друг от друга за 1 мин до столкновения?

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

2. Некоему специалисту по молекулярной биологии удалось вывести редкую разновидность бактерий. Ежечасно каждая бактерия делится на 3 части, причем каждая часть мгновенно достигает размеров взрослой бактерии и час спустя претерпевает деление на 3 части.

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

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

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

Загадочная покупка

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

Элен. Здесь то, что ты собирался купить для дома, папочка!

Мистер Браун. Спасибо, дочка! А сколько это стоило?

Элен. Пятьсот стоили 3 доллара.

Мистер Браун. 3 доллара? Значит, по 1 доллару за штуку.

Элен. Правильно, папочка.

Что, по-вашему, Элен купила в подарок отцу?

Возможно, вы догадались, что слово «пятьсот» может иметь 2 значения: число пятьсот и 3 цифры 500, написанные подряд. Если одна цифра стоит 1 доллар, то 3 цифры стоят 3 доллара: Элен купила три цифры для номера дома, в котором живут ее родители.

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

Как отгадать номер телефона?

Боб. Кстати, Элен, ты до сих пор не дала мне номер своего нового телефона.

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

Боб. Помилуй, Элен! Семизначных телефонных номеров почти 10 млн. Как я смогу отгадать один из них, задав всего 24 вопроса?

Элен. Подумай хорошенько, Боб, и я уверена, что ты сумеешь отгадать мой телефонный номер.

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

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

Чтобы найти выделенный элемент в множестве из 2 элементов, достаточно задать 1 вопрос, отвечать на который можно только «да» или «нет». В множестве из 4 элементов выделенный элемент будет найден за 2 таких вопроса, в множестве из 8 элементов — за 3 вопроса, в множестве из 16 элементов — за 4 вопроса и т. д. В общем случае n вопросов, допускающих ответы типа «да» или «нет», достаточно, чтобы найти выделенный элемент в множестве из 2ⁿ элементов.

В задаче о телефонном номере 24 вопроса позволяют отгадать любое число от 1 до 2²⁴ = 16777216, что больше 9999999 — «наибольшего» из семизначных телефонных номеров. Двадцати трех вопросов может не хватить, так как число 2²³ = 8388608 меньше некоторых семизначных телефонных номеров.

Прежде всего Бобу нужно спросить у Элен: «Номер твоего телефона больше 5000000?» Ответ на этот вопрос позволит Бобу отбросить половину номеров и тем самым вдвое сузить круг дальнейших поисков. Продолжая дихотомию, он заведомо «попадет» в номер телефона Элен, задав не более 24 вопросов.

Большинство людей с трудом верят, что с помощью 24 вопросов, допускающих ответы «да» или «нет», можно отгадать любое число от 1 до 16 777 216, поскольку не сознают, как быстро возрастают члены геометрической прогрессии со знаменателем 2. Именно этот чрезвычайно быстрый рост позволяет сравнительно легко отгадывать, любое задуманное слово, задавая тому, кто его задумал, только вопросы, допускающие ответы «да» или «нет». Если вы достаточно поднаторели в дихотомии, то, хотя задуманное слово может означать что угодно, обычно его можно отгадать, задавая менее 20 вопросов.

Описанную нами процедуру отгадывания семизначного номера телефона специалисты по вычислительной технике называют алгоритмом двоичной сортировки. На том же принципе основан остроумный фокус с отгадыванием чисел. Необходимый реквизит состоит из 6 карточек, показанных на рис. 1.

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

Секрет фокуса открывается просто: вы суммируете числа, стоящие в верхнем левом углу возвращенных вам карточек. Их сумма равна задуманному числу.

Карточки построены по системе, которая станет ясной, если все числа от 1 до 63 записать в двоичной системе, как это показано на рис. 2. Числа слева записаны в десятичной системе. Справа от каждого числа указано, как оно записывается в двоичной системе. Шесть чисел вверху таблицы означают степени числа 2, участвующие в двоичной записи чисел.

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

Карточки для отгадывания чисел можно составлять на основе не только двоичной, но и любой другой системы счисления. Например, с помощью рис. 3 можно составить карточки для отгадывания любого числа от 1 до 26 на основе троичной системы. Над каждым столбцом справа указана соответствующая степень числа 3 (именно она должна стоять в левом верхнем углу карточки). Если в столбце стоит единица, то число вписывается в нужную карточку один раз. Если в столбце стоит двойка, то число вписывается в карточку дважды.

Три карточки для отгадывания любого числа от 1 до 26, составленные на основе этого правила, приведены на рис. 4.

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

Возможно, вы захотите расширить набор с трех до шести троичных карточек. Как мы уже знаем, шесть двоичных карточек позволяют отгадывать любое число от 1 до 63. Шесть троичных карточек позволяют отгадывать любое число от 1 до 728. Теперь уже вам ясно, каким образом можно составить карточки для отгадывания чисел на основе системы счисления с любым основанием больше 3. Например, если мы остановим свой выбор на системе счисления с основанием 4, то одни числа будут встречаться на карточках по одному разу, другие — дважды, а третьи — трижды, и при суммировании вам придется одни ключевые числа брать сами по себе (с коэффициентом 1), другие — удвоенными, а третьи — утроенными.

Четверичные карточки показывают, что «троичная сортировка» в некоторых отношениях превосходит двоичную. Если мы будем последовательно делить множество не на 2, а на 3 части и каждый раз нам будут говорить, какая из частей содержит выделенный элемент, то найти его можно, задавая меньше вопросов. Разумеется, сами вопросы становятся более сложными: если раньше они требовали «двоичных» ответов («да» или «нет»), то теперь ответ на каждый вопрос должен быть «троичным».

Необычайные возможности, таящиеся в троичной сортировке, наглядно демонстрирует следующий карточный фокус. Пусть кто-нибудь из зрителей задумает любую из 3³ = 27 отобранных вами карт. Сдайте отобранные карты в три стопки, переворачивая каждую карту перед тем, как выложить ее на стол, вверх лицом, попросите зрителя указать, в какой из стопок находится задуманная им карта, после чего сложите стопки вместе и повторите всю процедуру еще дважды. Сложив стопки в третий раз, попросите зрителя назвать вслух задуманную карту и, сняв верхнюю карту, покажите ее всем зрителям. У вас в руках окажется задуманная карта! Фокус можно показывать сколько угодно раз, не опасаясь «осечек» — их нет и быть не может!

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

Нетрудно понять, почему так происходит. Принцип здесь тот же, что и при отгадывании телефонного номера, только множество делится каждый раз не на две, а на три равные или почти равные части. После первой сдачи задуманная карта оказывается среди 9 верхних карт, после второй сдачи она оказывается уже среди 3 верхних карт, а после третьей сдачи оказывается первой картой сверху. Если вы проделаете всю процедуру от начала до конца, держа карты вниз рубашкой и сдавая их снизу, то сможете наблюдать, как задуманная карта постепенно, в три этапа, спускается «на дно» перевернутой мини-колоды. Автоматическая сортировка элементов различных множеств, основанная на аналогичных принципах, играет важную роль в современной информатике — науке о накоплении, хранении и обработке информации.

Унесенная ветром

Боб и Элен решили провести летние каникулы в лесах штата Мэн, где в хижине жил дядюшка Генри.

Чтобы добраться до хижины, Бобу и Элен пришлось нанять лодку и идти на веслах вверх по течению.

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

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

Они успели отмахать на веслах 3 км вверх по течению, прежде чем Элен вспомнила о шляпке.

Элен. Стой! Где моя новая шляпка? Должно быть, ее унесло ветром.

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

Предположим, что лодка всегда движется по воде со скоростью 6 км/ч, а скорость течения реки 2 км/ч.

В котором часу Боб и Элен догнали шляпку?

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

Значит, задачу можно решать так, как если бы лодка двигалась в стоячей воде, Боб и Элен уплыли от шляпки на расстояние 3 км, а затем вернулись, заметив пропажу. Их путь туда и обратно составил 6 км.

Так как лодка развивает скорость 6 км/ч, то весь путь туда и обратно Боб и Элен проделали за 1 ч. Следовательно, когда Элен выудила из воды шляпку, было 3 часа дня.

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

Предположим, что никакого течения в реке нет. Боб и Элен идут на веслах 3 км вверх по реке от того места, где они взяли напрокат лодку, затем поворачивают и возвращаются назад. Весь путь туда и обратно занимает у них 20 мин.

Предположим теперь, что река, как ей и положено, течет от истока к устью со скоростью 2 км/ч, как в нашей задаче. Боб и Элен сначала поднимутся на веслах на 3 км вверх по реке, а затем снова вернутся туда, где взяли напрокат лодку. Сколько времени им придется затратить на весь путь туда и обратно на этот раз: больше или меньше 20 мин?

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

Это рассуждение не верно. Почему?

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

Те же соображения применимы к задачам о самолетах, летящих по ветру и против ветра. Если на преодоление расстояния из A в B и обратно в безветренную погоду самолет затрачивает определенное время, то на преодоление того же пути в ветреную погоду времени потребуется заведомо больше независимо от того, куда дует ветер: от A к B или от B к A.

Не менее известна еще одна хорошая задача на относительное движение. Девушка садится в последний вагон поезда. Обнаружив, что все места в вагоне заняты, она оставляет в тамбуре тяжелый чемодан и в тот самый момент, когда за окном проплывает фабрика детских игрушек «Зайки из байки», отправляется на поиск свободного места, идя размеренным шагом, и через 5 мин доходит до первого вагона. Убедившись, что свободных мест нигде нет, девушка поворачивается и идет назад с той же скоростью. В тот момент, когда она возвращается к чемодану, за окном мелькает магазин бакалейных товаров «Супы, крупы и ступы», находящийся от фабрики «Зайки из байки» на расстоянии 5 км. С какой скоростью идет поезд?

Решение этой задачи аналогично решению задачи о шляпке Элен, унесенной ветром: знать, с какой скоростью идет девушка по вагонам и какое расстояние ей приходится пройти, совсем не нужно. Путь туда и обратно она проделывает за 10 мин. Следовательно, ее чемодан проезжает 5 км за 10 мин. Значит, поезд идет со скоростью 0,5 км/мин, или 30 км/ч.

А вот малоизвестная задача на относительное движение, способная поставить в тупик даже сильных математиков. Юноша и девушка участвуют в забеге на 100 м. К тому моменту, когда девушка пересекает линию финиша, юноша успевают пробежать 95 м, и девушка выигрывает забег с преимуществом в 5 м.

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

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

Еще одна забавная задачка рассказывает о божьей коровке, отравленной какими-то химикалиями и утратившей способность ориентироваться в пространстве. Божья коровка находится на одном конце метровой рейки и хочет доползти до другого конца. Каждую секунду она проползает 3 см вперед и 2 см назад. За сколько времени она доползет до другого конца рейки? (Те, кто думает, что это произойдет через 100 с, ошибаются!)

Финансовые проблемы

Друзья уже почти добрались до хижины дядюшки Генри, когда Элен предложила Бобу следующую задачу-головоломку.

Элен. Что, по-твоему, дороже: копилка, наполненная пятидолларовыми золотыми монетами, или та же копилка, наполненная десятидолларовыми золотыми монетами?

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

Боб. У одного шотландца 44 бумажных доллара и 10 карманов. Может ли он разложить деньги по карманам так, чтобы число долларовых купюр во всех карманах было различно?

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

Задача о шотландце, раскладывающем по 10 карманам 44 бумажных доллара, гораздо труднее. Выясним, что произойдет, если мы разложим по карманам минимальное число купюр. Даже если мы оставим первый карман пустым (положив в него чисто символически 0 долларов), а в каждый из следующих карманов положим на 1 доллар больше, чем в предыдущий, то всего нам понадобится 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45 долларов, что больше тех 44 долларов, которые были у шотландца. А стоит лишь нам изъять хотя бы один доллар из какого-нибудь кармана, как в двух карманах долларовых купюр окажется поровну.

Основную идею такого рода рассуждений математики называют принципом Дирихле. Мы называли его также принципом «птичка в клетке». Суть его кратко можно сформулировать так: трех птичек невозможно рассадить по двум клеткам так, чтобы в каждой клетке оказалось по птичке. А вот еще один пример занимательной задачи, в решении которой используется принцип Дирихле. Предположим, что в городе не более 200 000 жителей. Можно ли утверждать, что по крайней мере у двух из них число волос на голове одинаково?

Такое утверждение может показаться невероятным, но принцип Дирихле убеждает нас в том, что ответ на этот вопрос должен быть утвердительным. Судите сами. Число волос на голове у человека не превышает 100 000. Если среди жителей города нет двух людей с одинаковым числом волос на голове, то один из них может быть совершенно лысым, у другого может расти на голове 1 волос, у третьего 2 волоса и т. д. Но как только мы дойдем до 100 001-го человека, как число волос у него на голове непременно окажется таким же, как у кого-то из жителей города. А так как население города составляет около 200 000 человек, то среди его жителей найдется около 100 000 таких, у которых число волос на голове будет совпадать с числом волос на голове у кого-то другого!

Часы дядюшки Генри

Едва Элен успела решить предложенную Бобом задачку, как они дошли до хижины дядюшки Генри. Хижину дядюшка построил своими руками, и в ней не было ни электричества, ни телефона, ни радио, ни телевизора.

Дядюшка Генри сразу обратился к ним с вопросом.

Генри. Который сейчас час?

Элен. У меня часов вообще не было, а часы Боба мы потеряли. А разве у вас нет стенных часов?

Генри. Часы-то есть, да вот беда: вчера вечером я забыл завести их. Вы пока побудьте тут, а я схожу в город, узнаю, который час, и заодно раздобуду чего-нибудь съестного.

Дядюшка Генри отправился в соседний городок и полтора часа провел там в бакалейном магазине.

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

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

Генри. Ни к чему все это, Элен! Расстояние от моей хижины до городка никто не мерил, да и скорость, с которой я хожу, тоже. Знаю лишь, что туда и обратно я шел одной и той же дорогой, одним и тем же шагом. Этого достаточно, чтобы правильно поставить часы. Я так всегда делаю.

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

Каким образом дядюшка Генри ухитряется узнавать точное время по возвращении домой?

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

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

Коль скоро мы заговорили о стрелках часов, то нельзя не упомянуть об одном каверзном вопросе, на который девять людей из десяти отвечают неправильно. Сколько раз от полудня до полуночи часовая стрелка совпадает с минутной? Большинство людей отвечают, что стрелки совпадают 11 раз, хотя в действительности стрелки совпадают 10 раз. Желающие могут убедиться в этом, переводя стрелки на своих часах.

Этот несколько удивительный факт позволяет легко и просто решить задачу, которая кажется неразрешимой без использования алгебраических уравнений. Часы имеют секундную стрелку, соосную с часовой и минутной стрелками. В полдень все 3 стрелки сливаются в одну. Успевают ли все три стрелки совпасть еще раз, прежде чем наступит полночь?

Выясним сначала, много ли на окружности циферблата найдется точек, в которых часовая стрелка совпадает с минутной. Казалось бы, что таких точек 12, но, как мы уже знаем, в промежуток с 12 часов дня до 12 часов ночи минутная стрелка совпадает с часовой только 10 раз. Поскольку в полдень и в полночь часовая стрелка также совпадает с минутной, то это означает, что всего на окружности циферблата имеется 11 различных точек, в которых часовая стрелка совпадает с минутной. Как показывают аналогичные рассуждения, секундная стрелка совпадает с минутной в 59 различных точках на окружности циферблата. Следовательно, точки совпадения минутной стрелки с часовой разделены И равными промежутками времени, а точки совпадения минутной стрелки с секундной разделены 59 равными промежутками времени.

Пусть A — величина любого из 11 промежутков, а B — любого из 59 промежутков (обе величины измерены в одинаковых единицах времени).. Если у чисел A и B есть общий делитель K, то на окружности циферблата найдется K точек, в которых оба совпадения (минутной стрелки с часовой и секундной стрелки с минутной) происходят одновременно. Но числа 11 и 59 не имеют общего делителя. Следовательно, с полудня до полуночи часовая, минутная и секундная стрелки ни разу не совпадают. Иначе говоря, все 3 стрелки совпадают только в 12 часов дня и в 12 часов ночи.

А вот две шуточные задачи о часах, на которых непременно «даст осечку» кто-нибудь из ваших друзей.

1) Часы с боем успевают пробить б часов за 5 с. За сколько времени они пробьют 12 часов?

2) Дядюшка Генри так устал с дороги, что лег спать в 9 часов вечера с намерением встать в 10 часов утра. Перед сном он поставил будильник на 10 часов и через 20 мин уже безмятежно спал. Сколько времени успеет поспать дядюшка Генри до звонка будильника?

Ответы на обе задачи приведены в конце книги.

Истина в вине

В последний день каникул Боб и Элен сообщили дядюшке Генри, что решили пожениться.

Дядюшка Генри. Рад за вас, мои милые. Нужно отметить этот знаменательный день!

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

Дядюшка Генри. Постойте, я знаю, как решить спор! Выстроим все бутылки в ряд и пересчитаем их по разработанной мной системе. Вот как это делается: раз, два, три, четыре, пять…

Дядюшка Генри. …шесть, семь, восемь, девять…

Дядюшка Генри. …десять, одиннадцать, двенадцать, тринадцать… Понятно?

Боб. Понятно-то, понятно, но сколько вы еще собираетесь считать?

Дядюшка Генри. Как вы помните, в 1976 г. мы праздновали 200-летие независимости. Вот я и досчитаю до 1976 г.

Элен (со стоном). Милый дядюшка, на это у вас уйдет еще 200 лет. Впрочем, минутку… Есть идея! Считать по бутылкам совсем не обязательно! Я могу вам сразу сказать, на какой бутылке окончится счет.

Элен. Число 1976 придется на вторую бутылку.

Дядюшка Генри не поверил Элен и упрямо продолжал пересчитывать бутылки. Через 15 мин он досчитал до 1976 и убедился, что счет, как и предсказывала Элен, окончился на второй бутылке.

Дядюшка Генри. Как это тебе удалось, Элен?

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

Элен догадалась, что утомительного счета на бутылках от 1 до 1976 можно избежать, если воспользоваться так называемой арифметикой вычетов, или теорией сравнений. Два числа a и b называются сравнимыми по модулю c, если при делении на с они дают одинаковые остатки. Число c называется модулем сравнения, а остаток от деления любого числа на c — вычетом этого числа по модулю c.

Обычные часы могут служить прекрасным примером конечной арифметики вычетов по модулю 12, содержащей 12 чисел. Действительно, вычет числа 12 по модулю 12 равен 0 (то есть число 12 сравнимо с нулем по модулю 12). Предположим, что на ваших часах сейчас 12 часов. Сколько будет на ваших часах через 100 часов? Разделив 100 на 12, вы узнаете, что остаток от деления равен 4 (число 100 сравнимо с числом 4 по модулю 12). Значит, через 100 часов на ваших часах будет 4 часа.

Теперь вам ясно, что метод дядюшки Генри эквивалентен арифметике вычетов? Единственное отличие состоит в том, что каждая из 3 бутылок, стоящих в середине, соответствует двум числам, поскольку эти бутылки приходится считать и слева направо, и справа налево. Счет 8 приходится на вторую бутылку, после чего весь цикл повторяется. Следовательно, метод дядюшки Генри эквивалентен арифметике вычетов по модулю 8.

Элен оставалось лишь найти вычет числа 1976 по модулю 8, то есть разделить 1976 на 8 и найти остаток. Проделав вычисления, Элен получила остаток 0. В арифметике вычетов по модулю 8 число 8 имеет нулевой вычет. Следовательно, счет до 1976 должен окончиться на второй бутылке.

Предположим, что вам захотелось узнать, на какой бутылке кончит считать дядюшка Генри, если вздумает дойти, например, до 12 345 678 987 654 321. Нужно ли для этого делить гигантское число на 8? Нет, если вы сообразите, как избежать утомительной процедуры. Так как число 1000 сравнимо с 0 по модулю 8, то необходимо делить на 8 только 3 последних знака — число 321, Проделав деление, вы узнаете, что интересующее вас семнадцатизначное число сравнимо с 1 по модулю 8. Следовательно, вздумай дядюшка Генри считать до этого числа, он бы закончил счет на первой бутылке.

Варьируя число бутылок, вы будете получать модели конечных арифметик вычетов по другим четным модулям. Если бутылки считать, как обычно, только слева направо, то вы получите модель конечной арифметики вычетов по любому модулю, как четному, так и нечетному.

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

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

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

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

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

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

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

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

Жозефина нахмурилась и сказала:

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

Король согласился. Жозефина разложила в круг 10 дукатов и принялась считать, откладывая каждый раз семнадцатую монету в сторону, пока не остался один-единственный дукат. Король был в восторге: дочь в совершенстве овладела тайным ритуалом.

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

Как Жозефина догадалась, с кого ей следует начать счет, чтобы он закончился на милом ее сердцу Джордже?

Практикуясь на монетах, Жозефина заметила, что в круге остается третья монета, если первой назвать ту, с которой она начала счет. Поэтому войдя в круг претендентов, она уверенно начала счет с Персиваля, после которого третьим стоял Джордж.

Интересным обобщением задачи Иосифа Флавия был бы следующий карточный фокус, если бы вам удалось соответствующим образом расположить 13 карт пиковой масти. Сумеете ли вы это сделать?

Вот как должен был бы выглядеть этот фокус. В одну руку вы берете стопку карт вверх рубашкой. Отсчитав сверху 1 карту, вы кладете ее на стол и открываете. Перед вами туз пик. Затем вы отсчитываете сверху 2 карты, первую подкладываете снизу под стопку карт, которая у вас в руке, а вторую открываете и кладете на стол: перед вами двойка пик. Затем вы отсчитываете сверху 3 карты, подкладывая первые две в том же порядке, в каком вы их снимаете, под стопку карт снизу, а третью карту открываете и кладете на стол: перед вами тройка пик. Продолжая счет дальше, вы каждый раз перекладываете карты по одной сверху вниз (что эквивалентно счету по кругу в задаче Иосифа Флавия), а последнюю открываете и кладете на стол. В итоге на столе оказываются выложенными по порядку все 13 карт пиковой масти от туза до короля.

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

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