Сколько способов поставить коней чтобы они не били друг друга

Миролюбивые шахматные кони

Задача

Клетки доски 5×5 раскрашены в шахматном порядке (рис. 1). а) Какое наибольшее число шахматных коней можно расставить на этой доске так, чтобы они не били друг друга? б) Сколькими способами это можно сделать?

Подсказка

Кони, стоящие на одной диагонали, друг друга не бьют.

В пункте б) ответ — один способ. Но это надо доказать.

Решение

Расстановка 13 коней показана слева на рис. 2. Докажем, что большее число не бьющих друг друга коней расставить на такой доске нельзя. Для этого мысленно разобьем клетки на пары так, чтобы в каждую пару входили клетки, отстоящие друг от друга на один ход коня. Одной клетке, естественно, пары не найдется. В том, что такое разбиение существует, можно убедиться, посмотрев на правую часть рис. 2.

Очевидно, что, как ни расставляй коней на доске, в каждой паре можно будет занять не больше одной клетки. Это означает, что коней заведомо не больше, чем количество пар, которых 12, плюс один (одна непарная клетка) — то есть 13.

Чтобы показать, что расстановка 13 коней на этой доске всего одна, идею с разбиением клеток на пары удобно несколько модифицировать.

Рассмотрим граф, вершинами которого будут центры клеток доски. Две вершины соединим ребром, если из одной в другую можно попасть за один ход коня. Этот граф показан слева на рис. 3. Важно, что в этом графе есть последовательность ребер, которая проходит через каждую из 25 вершин ровно по одному разу (рис. 3, справа).

На языке теории графов последовательности вершин, соединенных по цепочке ребрами, называют путями. Ясно, что из любых двух клеток, которые встречаются подряд на нашем пути, конь может стоять только в одной. Поэтому для того, чтобы «уместить» максимальное число коней, начинать надо прямо с первой клетки этого пути. Это и даст расстановку, показанную на рис. 2.

Послесловие

Рис. 4. Уильям Гамильтон, фотопортрет середины XIX века. Изображение из твиттера библиотеки Дублинского университета

Путь в графе, который помог нам решить задачу, проходил через все вершины графа по одному разу. Такие пути называются гамильтоновыми. Если в графе есть замкнутый гамильтонов путь (у которого совпадают начало и конец, путь в таком случае является циклом), то сам граф называется гамильтоновым. Название дано в честь ирландского математика Уильяма Гамильтона (1805–1865), которого по праву называют одним из величайших математиков XIX столетия: он оставил значительный вклад в разных областях математики (про некоторые важнейшие разделы вообще можно сказать, что они впоследствии выросли из его работ), механики и оптики.

Известно, что по мотивам своих исследований Гамильтон даже придумал игру-головоломку «Икосиан» (осторожно: перейдя по этой ссылке вы увидите решение головоломки!), которая одно время продавалась и была довольно популярной. Цель игры — построить гамильтонов цикл (то есть пройти по всем вершинам, каждый раз переходя в соседнюю по ребру, и вернуться в начало пути) в правильном додекаэдре (рис. 5, слева). Поскольку изготавливать такой правильный многогранник, а затем распространять его и, главное, играть с ним не очень удобно, игра представляла собой плоскую доску с выемками для фишек, соединенными линиями, соответствовавшими ребрам додекаэдра (рис. 5, справа). Фишек было 20 (столько же, сколько вершин у додекаэдра), они были пронумерованы, чтобы их можно было расставлять в порядке обхода.

Рис. 5. Слева: додекаэдр — один из пяти правильных многогранников; у него 12 граней, являющихся одинаковыми правильными пятиугольниками, 30 ребер и 20 вершин. Рисунок с сайта ru.wikipedia.org. Справа: оригинальный экземпляр игры «Икосиан». Любопытно, что игра названа «в честь» икосаэдра, а обходить в ней надо додекаэдр. Связано это с тем, что эти два многогранника двойственны друг другу Фото с сайта researchgate.net

В задаче о гамильтоновом пути требуется выяснить, есть ли в данном графе гамильтонов путь (или цикл), и, в случае положительного ответа, найти его явно. Эта задача — важная и неожиданно сложная с точки зрения сложности вычислений: в известных алгоритмах с ростом числа вершин в графе количество требуемых операций растет экспоненциально. Из-за этого такие алгоритмы на практике неэффективны: фактически для произвольного графа с сотней-другой вершин уже невозможно получить ответ на этот вопрос даже на самом мощном суперкомпьютере. По сути, эти алгоритмы — хоть и оптимизированный, но перебор всех возможных путей.

При этом, если кто-нибудь предоставит вам сколь угодно большой и сложный граф, а также путь в нем, то проверить, является ли этот конкретный путь гамильтоновым, вы сможете довольно просто. Это (вместе с тем, что пока неизвестен быстрый алгоритм решения) означает, что с точки зрения теории алгоритмов задача о гамильтоновом пути попадает в класс сложности NP. Более того, она является NP-полной задачей: к ней относительно просто — за полиномиальное время — можно свести любую другую задачу из этого класса. Раз уж зашла речь об классах сложности, то нельзя не упомянуть одну из так называемых задач тысячелетия — проблему равенства классов P и NP. К классу P относятся задачи, для которых известны алгоритмы, в которых количество операций растет как какой-то определенный многочлен от размера входных данных. Даже если степень многочлена большая, с точки зрения теории алгоритмов такая задача считается простой. Если придумать полиномиальный алгоритм для любой NP-полной задачи (в том числе и для поиска гамильтонова пути), то эта проблема автоматически будет решена.

При этом с «теоретической» точки зрения про гамильтоновы пути известно, грубо говоря, всё, поскольку теорема Бонди — Хватала (Bondy–Chvátal theorem) дает критерий того, что граф является гамильтоновым: для этого необходимо и достаточно, чтобы замыкание этого графа тоже было гамильтоновым графом. Замыкание графа G с n вершинами — это граф, который строится последовательным «пририсовыванием» ребер, соединяющих любую пару вершин, удовлетворяющую следующим двум свойствам: во-первых, эти вершины должны быть еще не соединены ребром, а во-вторых, сумма их степеней должна быть больше n. Проблема с этой теоремой в том, что она не помогает в алгоритмическом поиске гамильтонова цикла. И даже просто для ответа на вопрос о том, есть ли в графе такой цикл, она плохо годится, поскольку сводит проверку одного графа к проверке другого, в котором к тому же больше ребер. Исключение — те случаи, когда замыкание графа оказывается «хорошим»: про него относительно легко понять, что он гамильтонов. Пример «хорошего» в этом смысле графа — полный граф, в котором любые две вершины соединены ребрами (при \(n>2\) он точно гамильтонов).

Рис. 6. Леонард Эйлер. Портрет, выполненный Я. Э. Хандманном (1756 год). Рисунок с сайта ru.wikipedia.org

Кстати, с другим важным типом путей в графах — эйлеровыми путями, которые проходят по одному разу по всем ребрам, — все гораздо проще. Во-первых, есть простой критерий эйлеровости графа: связный граф эйлеров (то есть в нем есть эйлеров цикл) тогда и только тогда, когда в нем нет вершин нечетной степени. Во-вторых, есть алгоритмы, которые ищут такие пути за линейное время от размера графа (количества ребер). Понятие эйлерова пути появилось, когда Леонард Эйлер размышлял над задачей о семи кёнигсбергских мостах (это было в районе 1736 года).

Охватить весь спектр приложений эйлеровых и гамильтоновых графов в рамках нашей статьи невозможно, но можно посоветовать заинтересовавшимся читателям ознакомиться, например, со статьей Ф. Компо и П. Певзнера «Реконструкция генома: головоломка из миллиарда кусочков» («Квант», №3 за 2014 год). В ней подробно описано, какие математические идеи лежат в основе методов секвенирования ДНК и, в том числе, какую роль играют в этом эйлеровы и гамильтоновы графы.

Вернемся к приключениям шахматного коня на доске. Вспомним, что в решении задачи мы рассмотрели «коневой» граф шахматной доски 5×5 (он нарисован слева на рис. 3) и нашли в нем гамильтонов путь. По сути, этот путь показывает, как можно шахматным конем обойти всю доску, побывав в каждой клетке ровно один раз. Оказывается, этот вопрос — можно ли обойти конем данную доску (не обязательно квадратную)? — известен не одну сотню лет. Распространенное название — задача о ходе коня (Knight’s tour).

Легко видеть (на примере нашей задачи), что это частный случай поиска гамильтонова пути. Благодаря специфике «коневого» графа он решается относительно просто. Одно из первых исследований этого вопроса, кстати, выполнил Эйлер: в статье Solution d’une question curieuse qui ne paroît soumise à aucune analyse (1759 год) он предложил способ строить нужные обходы коня для доски 8×8.

С тех пор, разумеется, этот вопрос изучен вдоль и поперек. Например, известно, что всего для обычной шахматной доски существует 13 267 364 410 532 замкнутых обходов. Придуманы разные алгоритмы построения нужного пути. Самый, пожалуй, простой формулируется буквально одной фразой: нужно начать из любой клетки и каждым ходом ходить в ту клетку, с которой потом можно попасть на минимальное число еще не пройденных клеток (если таких клеток несколько, то можно выбрать любую). Этот способ называется правилом Варнсдорфа, он был предложен еще в XIX веке. Уточнение, написанное в скобках, делать приходится, потому что описанные в нем ситуации вполне вероятны и нужно хоть как-то выбирать из равнозначных вариантов. При внимательном исследовании этого способа (уже при помощи компьютеров) оказалось, что иногда совсем произвольный выбор следующей клетки для хода коня может впоследствии завести его в тупик. Однако это происходит довольно редко. Подробнее об этом рассказано в книге Е. Гика «Шахматы и математика».

Наконец, приведем еще пару задач, в которых рассмотренные выше идеи помогают найти решение без перебора.

1. Можно ли выписать целые числа от 0 до 9 в таком порядке, чтобы сумма любых двух соседних чисел делилась либо на 5, либо на 12? (Использовать каждое число можно только один раз.)

Построим граф, в котором вершины соответствуют данным числам. Соединим две вершины ребром, если сумма соответствующих чисел делится либо на 5, либо 12. После этого остается найти в таком графе гамильтонов путь.

2. Мышь грызет кусок сыра в форме куба 3×3×3, разбитый на единичные кубики. Когда она съедает один кубик целиком, то приступает к соседнему по грани кубику. Может ли она таким образом съесть всё, кроме центрального кубика?

Идея в том, чтобы раскрасить единичные кубики в шахматном порядке. Тогда в любом «пути» мышки по кубикам их цвета будут чередоваться. Значит, число «белых» кубиков не может отличаться от числа «черных» больше чем на 1.

3. Картинная галерея имеет форму правильного треугольника, который разбит на 36 одинаковых треугольных залов (залы — тоже правильные треугольники). Между любыми двумя соседними залами есть дверь. Какое наибольшее число залов может обойти, если не заходить в один и тот же зал дважды?

Подробный разбор этих задач, другие примеры и более строгое обсуждение их математической сути можно найти в статье П. Кожевникова «Длинные пути в графах» («Квант», №1 за 2018 год).

Источник

Сколько способов поставить на шахматную доску двух ладей так, чтобы они не били друг друга?

Найти количество способов поставить на доску восемь ладей так, чтобы никакие две не били друг друга
Дана квадратная доска 12×12 клеток. Найдите количество способов поставить на неё восемь ладей так.

Сколькими способами можно разместить на шахматной доске восемь ладей так, чтобы они не били друг друга?
Помогите решить, задачу,если есть возможность объяснить первый шаг решения задачи,или общий ход.

Число способов расставить на шахматной доске NxN K ладей так, чтобы они не били друг друга
Требуется найти число способов расставить на шахматной доске NxN K ладей так, чтобы они не били.

Рекурсия: расставить на шахматной доске 8 ладей так, чтобы они не били друг друга
Нужно расставить на шахматной доске 8 ладей так, чтобы они не били друг друга, вот что я наваял: .

Решение

Iliodor, Странная дробь
Имхо.
а) 64*49
б) 14*49 + 50*48

Добавлено через 5 минут
в) 6*(49+8) + 8*(49+6) +49*48 (тут хорошо бы меня проверили)

Найти число способов расставить на доске магараджей так, чтобы они не били друг друга
Магараджа—это шахматная фигура, сочетающая возможности ферзя и коня. Таким образом, магараджа может.

Найти число способов расставить на доске N*N ровно K магараджей так, чтобы они не били друг друга
Магараджа — это шахматная фигура, сочетающая возможности ферзя и коня. Таким образом, магараджа.

Расставить на доске 8*8 ферзя и двух белопольных коней так, чтобы они не били друг друга
Расставьте на шахматной доске 8х8 клеток ферзя и двух белопольных коней так, чтобы они не били друг.

Найдите количество способов поставить на шахматную доску 8 ладей
Дана квадратная доска 10×10 клеток. Найдите количество способов поставить на нее 8 ладей так, чтобы.

Разместить k королей так, чтобы они не били друг друга
На прямоугольном клеточном поле n x m разместить k королей так, чтобы они не били друг друга. Если.

Источник

∀ x, y, z

Главная ≫ Инфотека ≫ Математика ≫ Книги ≫ Глава 9. Независимость н доминирование шахматных фигур / Математика на шахматной доске // Гик Е. Я.

Глава 9. Независимость н доминирование шахматных фигур / Математика на шахматной доске Гик Е. Я. Глава 9. Независимость и доминирование шахматных фигур Множество очень интересных и красивых задач на шахматной доске возникает при решении двух следующих комбинаторных проблем. 1. Какое максимальное число одноименных фигур (ферзей, ладей, слонов, коней или королей) можно расставить на шахматной доске так, чтобы никакие две из них не угрожали друг другу? 2. Какое минимальное число одноименных фигур (ферзей, ладей, слонов, коней или королей) можно расставить на шахматной доске так, чтобы они держали под обстрелом все свободные поля доски? Первое из этих чисел мы будем называть числом независимости для соответствующих фигур, а второе — числом доминирования. Для единства терминологии фигуры, которые не угрожают друг другу, будем называть независимыми, а фигуры, обстреливающие все свободные поля доски (доминирующие на доске), — доминирующими. Здесь мы имеем явную аналогию с рядом важных задач из теории графов. Чтобы убедиться в этом, приведем следующие определения. Множество вершин графа называется независимым, если никакие две из них не соединены между собой ребром. Среди независимых множеств существует хотя бы одно «максимально независимое», содержащее максимальное число вершин. Это число называется числом независимости для данного графа (или числом его внешней устойчивости). Множество вершин графа называется доминирующим, если каждая вершина вне этого множества соединена ребром хотя бы с одной вершиной, принадлежащей ему. Среди доминирующих множеств существует хотя бы одно «минимально доминирующее», содержащее минимальное число вершин. Это число называется числом доминирования для данного графа (или числом его внутренней устойчивости)36. Каждой шахматной фигуре можно поставить в соответствие граф, вершины которого расположены на всех 64 полях доски, а ребра соответствуют ходам этой фигуры. Иначе говоря, если фигура в состоянии сделать ход между двумя данными полями, то расположенные в них вершины соединены ребром (аналогично был введен граф при рассмотрении задачи о коне Аттилы). Теперь легко убедиться в том, что наша первая проблема заключается в определении числа независимости для графа данной фигуры, а вторая проблема — в определении числа доминирования. Установленная связь между чисто математическими объектами — графами и задачами о шахматных фигурах, как мы видели, довольно естественна, чем и объясняется большая популярность шахматных терминов и задач в литературе по теории графов. Многие задачи о графах, весьма сложные в общем случае, удается решить для графов шахматных фигур. Именно так обстоит дело и с задачами о независимости и доминировании на шахматной доске. Ниже мы найдем числа независимости и доминирования для графов всех шахматных фигур и, следовательно, разрешим для них обе наши проблемы. Попутно нами будут рассмотрены вопросы о подсчете числа «оптимальных» расстановок фигур, а также разлтные обобщения для досок n×n. Для удобства через А будем обозначать число независимости, а через D — число доминирования, индекс у этих букв указывает размер доски; так, Dn (Л) — число доминирования для ладей на доске n×n. Результаты наших исследований мы будем заносить в табл. 2, знаки вопроса означают, что соответствующие числа неизвестны (по крайней мере, автору). После каждой строки с числами N и D в таблще идет строка с числом «оптимальных» расстановок на доске — т. е. расстановок, в которых участвуют, соответственно, N или D указанных фигур. Остановимся теперь на каждой из шахматных фигур в отдельности. 1. Ферзь. Число независимости для ферзей на любой доске n×n найдено в предыдущей главе, имеем N2(Ф) = 1, N3(Ф) = 2, Nn(Ф) = n (n ≠ 2, 3). Формула для числа соответствующих расстановок в общем случае не известна. На обычной доске, как мы знаем, кожно расставить восемь независимых ферзей (рис. 43), причем существуют 92 различные расстановки. Число доминирования для ферзей на обычной доске, как, впрочем, и на досках 9×9, 10×10 и 11×11 (рис. 35, 39), равно пяти. Существует 4860 способов для расстановки пяти «ферзей-часовых» на доске 8×8. Как уже говори л ось, в общем случае формулу для Dn (Ф) никому найти не удалось (тем более неизвестно и число решений). 2. Ладья. Для ладьи все результаты получены в главе 6. Как мы знаем, Nn (Л) = Dn(Л) = n, а число расстановок соответственно равно n! и 2n n — n! На обычной доске имеется 8! расстановок восьми независимых ладей и 2×8 8 — 8! расстановок восьми доминирующих ладей. Источник Оцените статью Вам также может понравиться Ясень семена способ распространения Ясень обыкновенный Fraxinus excelsior – так в ботанической Ярлыки способы создания ярлыков ос windows Создаем ярлыки на рабочем столе Windows Создаем ярлыки Японское удобрение фуджима способ применения Удобрения Фуджима Знаете потрясающее удобрение, палочка Японский чай способ заварки Технология заваривания японского чая Известно, что Правообладателям Политика конфиденциальности Контакты