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