Мартин Гарднер - Математические головоломки и развлечения
2k >= n > 2k-1
В общем виде эта задача была поставлена Л. Р. Фордом и Д. Р. Фулкерсоном. Однако она представляет собой лишь частный случай более общей задачи, опубликованной Л. Мозером, о минимальном числе распилов, которые необходимо произвести, чтобы разрезать прямоугольный параллелепипед размером а х b х с на единичные кубики.
Ю. Дж. Патцер и Р. В. Лоуэн в своей работе «Об оптимальном способе распиливания прямоугольного параллелепипеда на единичные кубы[9] пошли еще дальше. Они рассматривают n-мерные кирпичи с целыми сторонами, которые надо разделить минимальным числом плоских распилов на единичные гиперкубы. Авторы считают, что трехмерная задача «может найти применение в сыроваренной и сахарной промышленности».
8. Пассажир, приехавший необычно рано, шел пешком 55 мин, прежде чем его подобрала жена. Если они приехали домой на 10 мин раньше обычного, это значит, что жена выиграла 10 мин от времени своей обычной поездки на станцию и обратно или 5 мин от времени поездки на станцию. Следовательно, она встретила мужа за пять минут до того момента (пять часов), когда обычно сажала его в машину, то есть в 4 ч 55 мин. Он вышел в четыре часа, поэтому шел 55 мин. Скорость пешехода, скорость машины и расстояние от дома до станции для решения задачи не нужны. Если вы пытались подобрать эти величины, вам, наверное, показалось, что задача чересчур сложна.
Некоторые читатели заметили, что решение задачи намного упрощается, если нарисовать график движения (рис. 16).
Рис. 16 График к задаче о раннем пассажире.
По горизонтальной оси отложено время, по вертикальной — расстояние.
Из графика видно, что жена могла выехать из дому самое большее на 10 мин раньше, чем нужно, чтобы вовремя попасть к поезду.
Нижний предел продолжительности прогулки мужа (50 мин) достигается лишь тогда, когда жена выезжает из дому ровно на десять минут раньше обычного и либо сама едет с бесконечно большой скоростью (в этом случае муж прибывает домой в тот же момент, в какой она выезжает из дому), либо муж идет с бесконечно малой скоростью (в этом случае жена встречает его у самого вокзала, откуда он вышел за 50 мин до встречи, поскольку за эти 50 мин муж так и не сдвинулся с места). «Ни одно из этих предположений, — пишет профессор Д. У. Вайзер, приславший одно из лучших решений задачи с подобным анализом, — не следует считать ошибочным: ни мастерское вождение машины женой, ни странное поведение мужа, который битый час не трогается с места, поровнявшись с пивной».
9. Кучку фальшивых монет можно найти с помощью одного единственного взвешивания. Нужно взять одну монету из первой кучки, две из второй, три — из третьей и т. д. и, наконец, все 10 монет из десятой кучки. Затем все отобранные монеты взвешиваются все вместе на пружинных весах. Лишний вес, выраженный в граммах, будет соответствовать номеру фальшивой кучки. Если, например, отобранные монеты весят на семь граммов больше, чем они должны весить, то фальшивой должна быть седьмая кучка, откуда вы взяли семь монет (каждая из которых на 1 г тяжелее настоящей). Даже при наличии одиннадцатой кучки из десяти монет этот метод все еще пригоден: отсутствие излишка в весе говорит о том, что кучка, из которой вы не взяли ни одной монеты, — фальшивая.
Глава 4. КРЕСТИКИ И НОЛИКИ, ИЛИ ТИК-ТАК-ТОУ
Кто из нас в детстве не играл в крестики и нолики! Об этом древнем состязании на сообразительность писал еще Уордсворт:
На глади грифельной доски,
Расчерченной в квадраты,
Ведем сраженье я и ты,
Бывалые солдаты.
Кресты с нулями испестрят
Все поле битвы густо,
Но строй их — не могильный ряд
И не наводит грусти.
Не нужно нам владеть клинком,
Не ищем славы громкой.
Тот побеждает, кто знаком
С искусством мыслить тонким.
Не можем мы лишь одного:
Назвать то состязанье,
Хоть просты правила его,
Длинно его названье.
На первый взгляд кажется непонятным, что может так увлекать в этой детской забаве. Правда, даже в самом простом варианте игры число возможных комбинаций чрезвычайно велико (если ограничиться лишь пятью первыми ходами, то и тогда наберется 9x8x7x6x5 = 15120 различных вариантов), но на самом деле существенно различных вариантов немного, и любой мальчишка за час может стать непобедимым чемпионом. В то же время игра в крестики и нолики имеет и более сложные разновидности, и более глубокую стратегию.
На языке теории игр крестики и нолики можно назвать конечной (то есть доигрываемой до конца за конечное число ходов) строго детерминированной (то есть не содержащей элемента случайности) игрой двух сторон с полной информацией. Последнее означает, что обоим игрокам известны все сделанные ходы. Если обе стороны играют «рационально», игра должна закончиться вничью.
Единственный способ выиграть заключается в том, чтобы заманить неосторожного противника в ловушку, заготовив для следующего своего хода два почти готовых ряда (противник может помешать достроить лишь один ряд).
Из трех возможных начальных ходов — в угол, в центр и в боковую клетку — самым сильным является ход в угол, ибо при этом противник, чтобы не попасть с самого начала в ловушку, из восьми оставшихся клеток может выбрать только одну — центральную.
Наоборот, если первый ход сделан в центр, то блокировать его можно, лишь заняв угол. Наиболее интересная партия получается в том случае, когда первый игрок, открывая игру, занимает одну из боковых клеток: при таком начале перед обеими сторонами открываются широкие возможности в постановке ловушек. Три первых хода и ответы на них второго игрока, действующего осмотрительно, показаны на рис. 17.
Рис. 17 Первый игрок (ему принадлежат крестики) может сделать любой их трех ходов. Во избежание проигрыша второй игрок (ему принадлежат нолики) должен в каждом случае занять лишь одну из указанных клеток.
За много веков до нашей эры были известны гораздо более интересные с математической точки зрения варианты крестиков и ноликов, чем тот, в который принято играть в наше время. Во всех этих вариантах для игры нужно взять шесть фишек, по три у каждого игрока (у одного, например, три монеты одного достоинства, а у другого три монеты другого), и доску, изображенную на рис. 18.
Рис. 18 Игра в крестики и нолики монетами или фишками.
В древнем Китае, Греции и Риме был популярен самый простой вариант игры, когда играющие по очереди выставляют на доску фишки и делают это до тех пор, пока не выставят все шесть фишек. Если ни одному игроку не удается поставить три монеты в ряд и выиграть, то игра продолжается. Каждый из противников передвигает по очереди одну из своих фишек на соседнюю клетку.
Передвигать фишки можно только по вертикали и горизонтали.
Эта игра упоминается у Овидия в книге III «Искусства любви» в числе тех игр, которыми поэт советует овладеть женщине, если она хочет привлечь к себе внимание мужчин в обществе. Игра в крестики и нолики была известна в Англии еще в 1300 году под названием «Танец трех мужчин», от которого пошли «танцы» девяти, одиннадцати и двенадцати мужчин; в Америке последний вариант по сей день называется «мельница». Поскольку первый игрок, начиная с центра, наверняка выигрывает, то такое начало не сулит ничего интересного и обычно им не пользуются. Это ограничение при рациональной тактике приводит к ничьей, но обе стороны могут поставить противнику уйму потенциальных ловушек.
В одном из вариантов игры разрешается передвигаться на соседние клетки вдоль двух главных диагоналей. Дальнейшее видоизменение игры (приписываемое американским индейцам) допускает перемещение любой фишки на одну клетку в любом направлении (например, с клетки 2 можно передвинуться на клетку 4). В первом варианте тот, кто делает первый ход, может добиться победы, если начнет с центра, но второй вариант, по-видимому, всегда можно свести вничью. В игре без всяких ограничений, называемой во Франции «les pendus» («повешенные»), фишку разрешается передвигать на любую свободную клетку. Эта игра при разумной тактике также заканчивается вничью.
Известно много разновидностей крестиков и ноликов, в которых игра ведется на доске размером 4 клетки на 4. У каждого игрока имеется по четыре фишки, и их нужно попытаться выстроить в один ряд. В шестидесятые годы появилась игра «тико» — разновидность крестиков и ноликов, для которой нужна доска размером пять клеток на пять. Каждый из игроков по очереди выставляет свои четыре фишки, а затем передвигает их на одну клетку в любом направлении. Выигрывает тот, кто сумеет либо поставить свои четыре фишки в ряд (по горизонтали, вертикали или диагонали), либо выстроит их в виде квадрата на четырех клетках с общей вершиной.
