Текст книги "Есть идея!"
Автор книги: Мартин Гарднер
сообщить о нарушении
Текущая страница: 7 (всего у книги 17 страниц)
Глава 3
Находки в мире чисел
Неожиданные решения арифметических задач
Говоря об арифметике, разные люди вкладывают в это понятие различное содержание. Мы будем понимать под арифметикой все, что так или иначе связано с изучением свойств целых чисел и операций сложения, вычитания, умножения и деления, производимых над числами.
Когда-то, на заре человечества (точную дату не может назвать ни один антрополог), первобытные люди открыли, что предметы можно считать и результат счета не зависит от того, в каком порядке сосчитаны предметы. Например, если вы приметесь считать двух овец по пальцам, то результат будет одним и тем же независимо от того, с какой овцы вы начнете считать и будете ли вы загибать пальцы с мизинца или с большого пальца. У вас всегда получится 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. «Тайная» формула оказывается в этом случае столь простой, что после некоторой тренировки вы сможете проделывать все необходимые вычисления «в уме».
