Здравствуйте!
Наконец-то закончилась сессия и можно спокойно отдохнуть, в смысле заняться головоломками.
Стаи грачей
Сегодня для выпуска я выбрал Джонатана Велтона (Jonathan Welton) "Стаи грачей" (Cluster Rooks). Она некоторое время назад обсуждалась на замечательном (но англоязычном) сайте .
Стаи грачей (cluster rooks), также, как и НЛО (UFO), относится к головоломкам, в которых объекты (в данном случае грачи) могут летать по прямой линии до тех пор, пока их что-нибудь не остановит: или граница доски, или поставленный ранее грач. Играют на квадратной доске, ниже пример с доской 4х4. Каждый ход на свободную клетку доски ставят стаю из 5 грачей. Один грач остается на этой клетке. Один летит на север так далеко, как сможет, то есть пока не будет остановлен на клетке перед границей доски, либо перед другим грачом). Один - на юг. Ещё один - на запад и последний - на восток. То есть за один ход максимум клеток, которые могут быть заполнены - 5. Если стая была поставлена на клетку, которая граничит с границей доски, или заполненной клеткой, то улететь сможет меньше пяти грачей, то есть менее пяти клеток за ход будет заполнено.
Задача - заполнить доску за минимальное количество ходов.
В примере доска 4х4 заполнена за 4 хода (постановки стаи грачей). Я думаю, что это единственное решение (за исключением симметричных, разумеется):
Клетку, куда я ставлю стаю грачей я обозначал цифрой - номером хода, а "стрелками" показаны какие грачи смогли улететь (один грач остался в той же клетке)
Доска 5х5 может быть заполнена за шесть ходов (я не буду рисовать стрелки, а разлетевшихся грачей обозначу Х-ами). Найти решение достаточно просто. Решения скорее всего много, вот одно из них:
Каждая стая грачей может заполнить не более пяти клеток, поэтому n стай могут заполнить 5n клеток. Но занять углы можно ценой, как минимум трех грачей, так что в действительности n стай могут заполнить лишь 5n-3 клетки. 8 стай могут заполнить 8*5-3=37 клеток, что достаточно для заполнения доски размером 6х6, при условии, что не более чем один грач будет неэффективен. Можно ли заполнить доску 6х6 восьмью стаями? Да! Я знаю два решения, одно из которых достаточно красивое. Вполне возможно, что они единственные. Сможете ли вы их найти, или разыскать более двух решений?
Задачи с досками 7х7 и 8х8 просты.
Доска 9х9 теоретически может быть заполнена 17 стаями (17*5-3=82) Опять-таки одного грача можно потерять зря. Но лучшего результата, которого я добился - это заполнения 80 клеток доски с помощью 17 стай. Сможете ли вы полностью заполнить доску 9х9 за 17 ходов?
Ну и для самый умных - как насчет обобщения? Можно ли найти единую оптимальную стратегию? Всегда ли можно заполнить доску на практике, если в теории это возможно (то есть стай хватает)?
Присылайте свои ответы. На данный момент у меня есть ответы для задачи с доской 6х6 и 9х9. Эти и присланные вами ответы мы разберем в одном из следующих выпусков рассылки.
Обзоры
Сегодня я расскажу вам о рассылке "Mad Lar Team: Шевели извилиной!".
Код рассылки: rest.brain.erudit
Ведущий рассылки: Валерий
Страница рассылки в каталоге:
Периодичность: Раз в неделю
WWW:
В каждом выпуске рассылки вас ждут старинные русские загадки, вопросы для эрудитов, рубрика слово за слово, какая-нибудь задача и ответы на задания предыдущего выпуска. Как мне кажется, лучшая рубрика - старинные русские загадки, так как все остальное можно найти и в других рассылках. Загадки показались мне достаточно сложными, даже более чем достаточно. Вот вы сами подумайте, ну может современный человек отгадать такую загадку:
Игогоница поспела,
Ерохвоститься пора!
Мало того, что придется спрашивать всех, что такое "игогоница" и когда пора "ерохвоститься", так ведь все равно ведь не догадаешься, что ответ - баня. Хотя пример, конечно, я специально привел такой заковыристый, бывают загадки и легче, но то, что в старину головоломщики в России были хоть куда становится очевидно после чтения рассылки.
До встречи! (скорее всего очень скорой :)
