Лев Генденштейн - Алиса в стране математики

— Он вернётся сюда! — воскликнула Алиса, обращаясь к Королю. — Если, конечно, ему удастся обойти все стены, — добавила она. — Но тогда, — родилась у неё новая мысль, — Валету придётся здесь и закончить обход — ведь все три стены, идущие от «греческого храма» будут им уже пройдены!

— В том-то и дело, — загадочно отозвался Король и стал снова следить за Бубновым Валетом — он как раз дошёл до «египетской пирамиды» и остановился в раздумье.

— Куда же он сейчас повернёт? — подумала Алиса, и вдруг её осенило.

— Он уже не сможет выиграть! — воскликнула она,

— Почему ты так решила? — удивилась Королева. — Ведь он только начал обход!

— Куда бы он сейчас ни пошёл, две стены, которые отходят от «египетской пирамиды», будут пройдены, — сказала Алиса. — А чтобы пройти третью стену, Валету придётся вернуться в «египетскую пирамиду» и закончить в ней обход!

— Ну и что? — спросила Королева. — Почему бы ему не закончить обход в «египетской пирамиде»?

— Но ведь с «греческим храмом» уже получилось то же самое , — ответила Алиса, — здесь тоже пройдены две стены из трёх . И поэтому получается, что Валет должен закончить обход и в «греческом храме», и в «египетской пирамиде» — но ведь не может же он закончить обход сразу в двух башнях за́мка!

— Это не под силу даже Королю, — согласилась Королева, и стражники увели Бубнового Валета.

В третий раз выбор Королевы пал на Валета Червей.

— А если и он не сможет пройти? — с тревогой за своего нового знакомого подумала Алиса. — Чтобы его спасти, я должна до чего-то догадаться , — вспомнила она слова Короля. — Только вот до чего ?

Валет Червей начал обход с «греческого храма» и направился в сторону «индийского храма». Алиса посмотрела вслед Валету, окинула взглядом весь за́мок и... догадалась!

— Обойти этот за́мок так, как предложил Король, вообще невозможно ! — воскликнула она.

— Ну, это уж слишком! — возмутилась Королева. — Валет не прошел и одной стены, а ты уже заявляешь, что обойти весь за́мок вообще невозможно! Откуда ты это знаешь?

— В каждой башне за́мка сходятся три стены, — сказала Алиса. — А это значит, что каждая из четырёх башен может быть только либо началом , либо концом обхода!

— Почему? — не поняла Королева.

— Потому что в середине обхода могут быть только башни, в которых сходится чётное число стен, — объяснила Алиса. — Ведь при каждом «заходе» в такую башню надо пройти две стены: по одной стене прийти в башню, а по второй — уйти из башни! Поэтому ни одна из четырёх башен вашего нового за́мка не может быть в середине обхода , и, значит, обойти весь за́мок так, как предложил Король, невозможно! — закончила свое рассуждение Алиса.

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

— Зачем вы придумали такую игру, в которую невозможно выиграть? — с упрёком обратилась она к Королю.

— Почему невозможно? — возразил Король. — Как раз вы-то всё время выигрываете! Вы же любите выигрывать? Теперь вы даже заранее знаете, что выиграете — вы говорили, что тогда вам играть интереснее всего?

— Но теперь и они все знают, что не смогут выиграть! — воскликнула Королева, показывая на гостей.

— Тем лучше, — отозвался Король. — Значит, теперь вы можете выигрывать, даже не играя — разве это не самое интересное?

Гости по-прежнему не сводили глаз с Королевы. Она медленно обвела гостей взглядом и обратилась к Алисе:

— Наверное, ты была права: выигрывать без игры не так интересно... Игра отменяется! — громко объявила она.

Валет Червей благодарно посмотрел на Алису, и она ответила ему кивком.

— Раз игра отменяется, надо помиловать и двух приговорённых Валетов, — сказала Алиса, обращаясь к Королеве.

— Конечно, — поддержал Король Алису. — Если отменяется игра, то отменяются и все проигрыши!

Гости с облегчением вздохнули, но тут Королева сказала:

— Переходим к суду.

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

Вот как были расположены кёнигсбергские мосты:

Может быть, вам удастся их «обойти»? Попробуйте. Но если вам не повезет, не огорчайтесь: ни один житель Кёнигсберга так и не смог этого сделать! А вот если это вам удалось , значит... значит, вы просто ошиблись ! Скорее всего, забыли пройти по какому-то мосту или прошли его дважды. Дело в том, что обойти все кёнигсбергские мосты по одному разу невозможно ! Сейчас мы докажем это.

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

Если можно обойти все семь мостов, пройдя по каждому из них только один раз, то и наш новый за́мок тоже можно обойти, проходя один раз каждую из семи стен. Однако посмотрите — ни одна из четырёх башен не может быть в середине обхода, потому что в любой башне нашего «кёнигсбергского за́мка» сходится нечётное число стен! И поэтому обойти его, проходя один раз по каждой стене, невозможно (так же, как и новый королевский за́мок Королевы Червей). Обойти за́мок можно только в том случае, когда башен с нечётным числом стен не больше двух — тогда одна из «нечётных» башен должна быть началом обхода, а вторая — его концом. (Если все башни «чётные», то начать обход можно из любой башни. Тогда в этой же башне обход и закончится.)

Задачу о кёнигсбергских мостах первым решил Эйлер в 1736 году. Эйлер был великим математиком и поэтому не ограничился только кёнигсбергскими мостами — он решил задачу в общем виде , то есть для любого числа мостов, которые как угодно соединяют берега и любое число островов! И теперь даже житель Санкт-Петербурга может определить, удастся ли ему прогуляться по трёмстам мостам своего города, соединяющим сорок два острова, причём прогуляться так, чтобы пройти по каждому мосту только один раз.