Немалое удовольствие вы получите, предлагая задачи из нашего сборника своим друзьям и знакомым. Во многих случаях они будут долго размышлять над предложенной вами задачей, пока наконец не признают себя побежденными, а задачу безнадежно трудной. Когда же вы покажете им, что задача решается очень просто, они, без сомнения, получат большое удовольствие. Не исключено, что озарения каким-то образом связаны с удовольствием, получаемым от игры. Тот, кто умеет находить нестандартные решения, при встрече с головоломкой или трудной задачей испытывает радость, сравнимую с той, которая знакома любителям бейсбола или шахмат. Дух игры, по-видимому, предрасполагает к озарениям, позволяющим находить оригинальные решения.
Способность к нестандартному мышлению отнюдь не обязательно коррелирует с быстротой соображения. Тугодумы могут получать удовольствие от задачи ничуть не меньше тех, кто схватывает все на лету, и при поиске неожиданных решений могут оказаться сильнее «скородумов». Возможно, что удовольствие, получаемое при нестандартном решении задачи, побудит кого-нибудь к более глубокому изучению традиционных методов решения. Эта книга предназначена для любого читателя, наделенного чувством юмора и способностью понимать задачи.
Несомненно, существует тесная взаимосвязь между озарениями и творческой деятельностью в науке, искусстве и любой другой области человеческой деятельности. Великие революции в науке почти всегда были и будут следствием неожиданного интуитивного постижения истины. Что такое наука, как не систематические попытки ученых решать те трудные задачи, которые поставила перед ними природа? Природа бросает вызов любознательности ученого, который пытается понять, как именно и почему происходит в природе то или иное явление. Ни изнурительный метод проб и ошибок, которым Эдисон подбирал подходящий материал для волоска своей электрической лампы, ни даже дедуктивные рассуждения, опирающиеся на соответствующие знания, во многих случаях не позволяют решить задачу. Решение, как правило, открывается неожиданно, и его по праву можно было бы назвать решением типа «Эврика». Восклицание «Эврика!» («Нашел!») заимствовано нами из древней легенды о том, как Архимед, сидя в ванне, открыл способ, позволяющий определить, сколько золота утаили мастера при изготовлении короны царя Сиракуз. Рассказывают, будто Архимед так обрадовался своему открытию, что выскочил из ванны и, забыв об одежде, бросился бежать по улице, крича: «Эврика! Эврика!»
Собранные в книге задачи разделены на шесть категорий: комбинаторные, геометрические, теоретико-числовые, логические, процедурные и словесные. Это категории не взаимоисключающие, они неизбежно перекрываются, и задачи, отнесенные нами к одной из них, можно было бы включить и в другие. Каждую задачу мы стремились облечь в форму какой-нибудь забавной истории, чтобы создать у читателя приятное настроение и тем самым вовлечь его в игру. Мы надеялись, что такое настроение позволит читателю с большей легкостью отринуть установившиеся, стандартные способы решения задач. Всякий раз, когда вам случится решать новую задачу, мы настоятельно рекомендуем обдумать ее со всех сторон, сколь бы странными и причудливыми ни казались иные подходы, вместо того чтобы напрасно тратить время на длинное и громоздкое решение.
К каждой задаче с замечательными иллюстрациями канадского графика Джима Глена мы присовокупили несколько замечаний. В них речь идет о характере задач и показывается, как во многих случаях рассмотренная нами игровая ситуация связана с важными аспектами современней математики. В некоторых случаях мы предоставляем читателю возможность испытать свои силы на еще не решенных задачах.
Стремясь облегчить поиск нестандартных решений, мы хотим обратить внимание читателя на следующие вопросы, которые иногда могут служить своего рода путеводными нитями и позволяют хотя бы приблизительно систематизировать возможные подходы:
1. Нельзя ля свести задачу к более простому случаю?
2. Нельзя ли преобразовать задачу к изоморфной задаче, легче поддающейся решению?
3. Не существует ли для решения задачи какого-нибудь простого алгоритма?
4. Нельзя ли для решения задачи применить какую-нибудь теорему из другой области математики?
5. Можно ли проверить правильность полученного решения на наглядных примерах или контрпримерах?
6. Какие аспекты задачи несущественны для решения и лишь отвлекают ваше внимание?
Не будет преувеличением сказать, что в наше время многие склонны поддаваться все более сильному искушению сводить решение всех математических задач к составлению программ для ЭВМ. Современная быстродействующая ЭВМ, проделав исчерпывающий перебор всех возможных случаев методом проб и ошибок, действительно может решить ату или иную задачу за считанные доли секунды или за несколько секунд, но на составление хорошей программы и ее отладку потребуется несколько часов или дней. Составление программы также не всегда сводится к стандартным операциям и требует своих озарений. Но удачная идея может привести к решению задачи и без обращения к ЭВМ и сделать излишним составление программы.
Было бы печально, если бы блага НТР оказали на человечество растлевающее влияние и оно интеллектуально обленилось бы настолько, что утратило бы способность к творческому мышлению. Главная цель предлагаемой вниманию читателя подборки задач и состоит в том, чтобы предоставить ему широкие возможности для оттачивания и развития способности находить нестандартные решения.
Мартин Гарднер
Глава 1
Комбинаторные находки
Неожиданные решения задач на составление и перечисление комбинаций
Комбинаторный анализ, или комбинаторика, занимается изучением способов составления комбинаций из предметов. Пожертвовав самую малость общностью, комбинаторный анализ можно определить как раздел математики, который занимается изучением способов объединения по заранее заданным правилам элементов в множества и свойств возникающих при таком объединении множеств.
Например, наша первая задача сводится к установлению способов объединения в множества разноцветных шариков. Требуется найти наименьшие множества шариков, удовлетворяющие определенным условиям. Во второй задаче речь идет о способах установления очередности встреч между участниками турнира по настольному теннису, разыгрываемого по олимпийской системе (важный аналог этой задачи встречается при автоматической сортировке данных).
В комбинаторном анализе часто требуется найти число всех возможных способов объединения предметов в множества по определенным правилам. С проблемой перечисления, как принято называть эту разновидность комбинаторных задач, мы познакомим читателя при подсчете числа различных маршрутов, которыми Сьюзен может следовать в школу. В нашем случае объединяемые элементы представляют собой прямолинейные отрезки маршрутов, проходимые по строкам или столбцам матрицы. Поскольку подсчет маршрутов связан с рассмотрением геометрических фигур, мы вступаем в область комбинаторной геометрии.
Комбинаторные аспекты присущи всем разделам математики, и не удивительно поэтому, что читатель обнаружит комбинаторные задачи во всех без исключения главах нашей книги. Так, существует комбинаторная теория чисел, комбинаторная топология, комбинаторная логика, комбинаторная теория множеств и даже, как мы увидим в последней главе, посвященной словесным играм, комбинаторная лингвистика. Особенно важную роль комбинаторика играет в теории вероятностей: без подсчета всех комбинаций нельзя было бы найти распределение вероятностей. Много задач по теории вероятностей собрано в книге Уитворта «Выбор и случай»[2]. Слово «выбор» в заголовке книги указывает на ее комбинаторный аспект.
Самая первая задача в нашей книге также имеет непосредственное отношение к теории вероятностей: ведь, в ней требуется указать комбинацию цветных шариков, которая с полной гарантией (то есть с вероятностью, равной 1) позволила бы удовлетворить определенным требованиям. Читая нашу книгу, нетрудно убедиться в том, что из простых вопросов о перечислении способов объединения предметов по тому или иному признаку возникает поистине безбрежное море вероятностных задач. Перечисление маршрутов, по которым Сьюзен могла бы следовать в школу, тесно связано с треугольником Паскаля и теми применениями, которые он находит при решении элементарных задач теории вероятностей.
Число комбинаций, дающих решение данной комбинаторной задачи, очевидно, может быть равно нулю, единице, любому конечному числу и даже обращаться в бесконечность. Например, нечетное число ни одним способом невозможно представить в виде суммы двух четных чисел. Число 21 представимо в виде произведения двух простых чисел одним и только одним способом. Число 7 представимо в виде суммы из двух целых положительных чисел тремя различными способами (слагаемые каждой из трех допустимых комбинаций нанесены на противоположные грани игральной кости). Существует бесконечно много пар четных чисел, сумма которых четна.
