Текст книги "Есть идея!"
Автор книги: Мартин Гарднер
сообщить о нарушении
Текущая страница: 9 (всего у книги 17 страниц)
Финансовые проблемы
Друзья уже почти добрались до хижины дядюшки Генри, когда Элен предложила Бобу следующую задачу-головоломку.
Элен. Что, по-твоему, дороже: копилка, наполненная пятидолларовыми золотыми монетами, или та же копилка, наполненная десятидолларовыми золотыми монетами?
Боб немного помедлил, но ответил правильно и в свою очередь задал Элен задачу.
Боб. У одного шотландца 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 карт пиковой масти от туза до короля.
Карты в стопке должны лежать в следующем порядке (сверху вниз): туз, восьмерка, двойка, пятерка, десятка, тройка, дама, валет, девятка, четверка, семерка, шестерка, король.
Может быть вам покажется, что выстроить такую последовательность удалось лишь методом проб и ошибок после многих безуспешных попыток. Вы глубоко заблуждаетесь: для получения таких последовательностей существует очень простой алгоритм. Многие фокусники, разрабатывая трюки такого рода, действительно немало времени проводят в раздумьях над тем, как расположить карты, пока внезапная догадка не превратит задачу, над решением которой они безуспешно бились не один день, в тривиальную. Удастся ли вам разгадать, как строится последовательность в задуманном нами фокусе в духе Иосифа Флавия, прежде чем вы заглянете в ответ, помещенный в конце книги.
Глава 4
Логические находки
Неожиданные решения задач, требующих умения мыслить последовательно
В этой главе нас будет интересовать не формальная логика, а задачи, для решения которых не нужны особые познания в математике, но необходимо умение мыслить последовательно. Некоторые из предлагаемых нами задач напоминают загадки в том смысле, что содержат умышленно введенные в их условия утверждения, способные «сбить с толку» не слишком проницательного читателя, или решения, основанные на игре слов, но в большинстве случаев мы предлагаем вам честную игру – задачи, которые имеют решение.
В том, как собранные в этой главе различные логические задачи-головоломки относятся к математике, нетрудно усмотреть некую общую тенденцию. Все математические задачи решаются при помощи рассуждений, проводимых в рамках некоторой дедуктивной системы, включающей в себя наряду с другими правилами основные законы логики. Хотя для решения любой задачи из этой главы не требуется знание формальной логики, тем не менее ведущие к решению неформальные рассуждения по существу имеют много общего с теми, которые проводят математики, физики, химики и биологи, сталкиваясь с какой-нибудь трудной проблемой.
Под «трудной проблемой» мы понимаем здесь задачу, подход к решению которой неизвестен. Разумеется, если алгоритм решения существует, то ни о какой по-настоящему трудной проблеме не может быть и речи: достаточно лишь засыпать зерна исходных данных и привести в действие жернова алгоритма, как мы получим ответ. Например, памятная всем формула корней квадратного уравнения говорит нам о том, какие действия и в какой последовательности необходимо произвести над коэффициентами уравнения, чтобы найти его корни.
И в математике, и в естественных науках интересными задачами, бросающими вызов исследователю, принято считать такие, для решения которых не существует готовых методов. Столкнувшись с такой задачей, исследователь долго, а иногда и мучительно размышляет, перебирая в памяти всю информацию, имеющую хотя бы отдаленное отношение к интересующей его теме, в надежде, что удачная догадка подскажет нужное решение. Именно поэтому решение занимательных логических задач служит великолепной тренировкой к решению важных научных проблем.
Некоторые задачи в этой главе связаны с серьезной математикой еще более тесными узами. Например, задача «В костюмах одного цвета» и следующая за ней задача легко решаются табличным методом, аналогичным широко используемому в формальной логике методу таблиц истинности. В одной из этих задач встречается важное логическое отношение – так называемая «материальная импликация». В исчислении высказываний (одном из разделов математической логики, имеющем первостепенное значение) импликацию принято обозначать знаком ⊃ или →. Отношение A ⊃ B означает, что если A истинно, то B должно быть истинно. Одно из возможных истолкований этого логического отношения (на языке теории множеств) гласит: все элементы множества B содержатся в множестве A.
Слово «индукция» имеет по существу два различных значения. Неполная индукция – это процесс восхождения от частного к общему. Ученый, наблюдающий частные случаи (например, замечающий, что некоторые вороны черные), делает общее заключение (о том, что все вороны черные). Это заключение никогда не носит характер достоверного утверждения: вполне возможно, что на свете существует по крайней мере одна белая ворона, которая еще не попадалась на глаза наблюдателю.
Математическая индукция, с которой вы познакомитесь в комментариях к тестам со шляпами в задаче «Аховы награды», представляет собой совершенно иной процесс, хотя и в математической индукции мы имеем дело с восхождением от частного к общему, охватывающему информацию о бесконечной последовательности частных случаев. Математическая индукция – неоценимое средство исследования почти во всех разделах математики.
Большинство задач, собранных в этой главе, по сложности и серьезности уступает задаче о шляпах. Тем не менее и они позволят вам отточить свое остроумие, научат внимательно следить за всякого рода словесными «ловушками», расставленными в условиях задачи, и в особенности оценить преимущества непредвзятого, широкого поиска возможного подхода к решению задачи. Чем больше подходов вы проанализируете, сколь бы причудливыми и экзотическими они ни были, тем больше шансов у вас на успех. В этом один из секретов всех творчески мыслящих математиков.
