Шахматная доска как расставить 15 коней
Расставьте на шахматной доске 32 коня так, чтобы каждый из них бил ровно двух других.
Подсказка
В квадрате 3×3 можно обойти ходом коня все клетки, кроме центральной, и вернуться в исходную клетку.
Решение
Если в квадрате 3×3 поставить коней на все клетки, кроме центральной, то каждый конь будет бить ровно двух других. Теперь расположим четыре таких «каре» на доске подальше друг от друга – так чтобы кони из разных каре не били друг друга (см. рисунок).
Источники и прецеденты использования
| олимпиада | |
| Название | Математический праздник |
| год | |
| Год | 1998 |
| класс | |
| 1 | |
| Класс | 6 |
| задача | |
| Номер | 6 |
Миролюбивые шахматные кони
Клетки доски 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 год).
Показать комментарии (4)
Свернуть комментарии (4)
Юрий Фёдоров 25.03.2019 04:34 Ответить
Мне снова как-то совсем простой показалась задача, и графов никаких не потребовалось придумывать-рисовать, и клетки нумеровать не нужным было, а получилась задачка всего-то в два действия:
1 действие: После нескольких попыток расставить коней я сообразил, что конь всегда бьет только клетку другого цвета (стоит на белой — бьет черные, стоит на черных — бьет белые)
2 действие: оттого стало ясно, что чтоб они не били друг друга, надо поставить коней на одноцветные клетки, а так как белых клеток тут больше, ставить коней нужно на белые.
И послесловие оказалось снова интереснее и сложнее задачи, с большей широтой и глубиной.
ee 
28.03.2019 
22:46 Ответить
А как быть с тем, что кони, выставленные квадратиком 2×2 или, скажем, в ряд, не бьют друг друга, стоят довольно компактно и при этом занимают клетки обоих цветов? Не очень понятно, как ваша идея помогает избежать перебора разных случаев расстановки. К тому же «двухцветных» способов расставить 12 коней — полным полно. Например, можно занять четыре уголка из трех клеточек по углам доски.
И послесловие оказалось снова интереснее и сложнее задачи, с большей широтой и глубиной.
Задача, конечно, не сложная. И во многом была выбрана благодаря тому, что от нее легко перекинуть «мостики» сразу к нескольким интересным темам 🙂
Кстати, послесловие еще чуть-чуть расширилось 🙂
Юрий Фёдоров 31.03.2019 08:20 Ответить
Как быть?
Без перебора ясно, что соотношение белых и черных клеток почти
1:1, (12:13),
то есть количество каждого цвета почти половина от всего количества клеток поля.
Квадратики и линии из коней сразу демонстрируют, что битых клеток вокруг них образуется больше, чем количество клеток, занятых конями.
В случае линии битых клеток вчетверо больше (если к стене приставить, то все равно дело дрянь — вдвое), то есть
1:4 (1:2),
В случае квадратика битых больше всемеро (в углу — почти втрое), то есть
1:7 (1:3, 4:11)
К чему же тут заниматься переборами??
Линии и квадраты сразу отбрасываются после этих простеньких прикидок.
Очевидно, первое соотношение — черных к белым — дает возможность выставить самое крупное стадо коней.
Ну а уж ставить коней не на все клетки одного цвета, заведомо зная, что кони, будь они на остальных клетках того же цвета, не создадут угроз остальным) — это уже мазохизм)) зачем ставить только на часть белых клеток??
Ну и, наконец, понимая, что достижимо 13 коней — зачем искать-ковыряться в комбинациях из 12?
Возможно логика моя и не «чистая», отчасти интуитивная и не продуманная до конца (не все ее элементы досконально я разобрал и доказал себе), но как-то сразу давшая результат в 13 коней.
А найти верное решение, хотя и ошибаясь в аргументах (или не будучи полностью информированным об обстоятельствах) — это частенько в жизни лучше, чем погрязнуть в расчетах и найти решение с опозданием или даже так и вовсе его не найти))
Намного лучше!)
Пошел читать расширенное послесловие, спасибо)
ee 09.04.2019 21:18 Ответить
Заметьте, что ваши рассуждения уже занимают место, сравнимое со строгим решением задачи 🙂
А найти верное решение, хотя и ошибаясь в аргументах (или не будучи полностью информированным об обстоятельствах) — это частенько в жизни лучше, чем погрязнуть в расчетах и найти решение с опозданием или даже так и вовсе его не найти))
Возможно, что и так. Но проблема такого подхода в том, что непонятно, как убедиться в верности найденного решения.
Как ходит шахматный конь
Самая любимая фигура всех детей – шахматный конь. Многих родители уже научили ходить конем. Наша задача помочь вам научиться еще лучше прыгать этой шахматной фигурой.
Известно, что конь ходит буквой «Г». Но ход по этой букве иногда вырастает до невероятных размеров и шахматный конь может оказаться совсем не там, где нужно.
Поэтому учиться ходам коня будем так: посчитаем от белого коня раз – два – в сторону. Сначала два раза вверх и налево – конь оказался на цифре 1 (d7).
Раз – два – в сторону (теперь направо). Конь приземлился на цифре 2 (f7).
Или так: ход ЛАДЬИ + ход СЛОНА. Движемся вниз на одну клетку ходом ладьи и на одну клетку вниз ходом слона. Наш конь окажется на цифре 3 (поле d3) или цифре 4 (поле f3).
Поиграем в Цветочки. Вы видели когда-нибудь стреноженного коня? Это когда коню спутывают ноги, чтобы он не мог далеко ускакать.
Так вот. Нашему шахматному коню спутали ноги на поле е5 (диаграмма выше). А вокруг него большое поле с цветами. И наш конь выбирает вкусные цветы, которыми он полакомится, когда ему развяжут ноги.
Наша задача: расставить цветочки-пешки вокруг коня. Первую пешку ставим вместе, считая знакомое раз – два – в сторону. Получилось f7.
Назовём все поля, куда мечтает прыгнуть конь:
Ке5 – f7, g6, g4, f3, d3, c4, c6, d7.
Шахматные ходы коня
Наш сытый шахматный конь захотел в гости. Самое интересное задание – это путешествие конём из угла в угол по шахматной доске. Захотелось белому коню, живущему на поле а1, сходить в гости к чёрному. А чёрный конь в другом углу живёт, на поле h8. Дорог много. Вот одна из них.
Ka1 – b3 : с5 – d7 – e5 – f7 : h8
По дороге конь может «подкрепиться» пешкой с5, а самые кровожадные могут «закусить» и конём. Будем вежливы – нанесём ответный визит.
Kh8 – g6 – h4 – g2 – e3 – c2 : a1
Часто путешествие коня заканчивается на полях g7, g8, h7. А вот оттуда в угол не попасть.
Теперь упражнения для совершенствования прыжка этой интересной фигуры. Постарайся попасть конём в угол доски. Смотри не свались с доски!
Для коня с6:
1. Kc6 – a7 2. Ka7 – c8 3. Kc8 – b6 4. Kb6 – a8
Для коня g7:
1. Kg7 – e6 2. Ke6 – f8 3. Kf8 – g6 4. Kg6 – h8
Для коня a2:
1. Ka2 – c1 2. Kc1 – b3 3. Kb3 – a1
Для коня g1:
1. Kg1 – h3 2. Kh3 – f2 3. Kf2 – h1
Ты ещё не заметил одну особенность прыжков коня? При прыжке он всегда меняет цвет поля. Стоял на белом – значит приземлится на чёрном.
Когда конь хочет кого-то побить, то при этом он может прихватить фигуры, стоящие на его пути. Как избежать таких ошибок?
Запомни, что конь бьёт только фигуру на том поле, на которое приземляется! Конь как бы протискивается или перелетает через фигуры, не обращая на них никакого внимания.
Шахматный конь — задачки
Чтобы вы стали настоящим шахматным джигитом, выполните такие задания.
1. Дома немного попрыгай конём по доске.
2. Если в квартире паркет квадратиками – «скачите на коне» в кухню и обратно. Привлеки к этому процессу всю свою семью. Походите след в след. Можно станцевать коневой танец.
3. Перейди шахматное поле конём наискосок из угла в угол. Побывай конём во всех углах.
4. Поставь на доску несколько пешек и фигур (не забудь углы!) и поиграй в Зёрнышки. Кстати, удастся ли тебе очистить всю шахматную доску за 21 ход?
5. Обойти конем всю доску нелегко! Нарисуй в тетради квадрат размером 8×8 и ходом коня обойди как можно больше клеток, останавливаясь в каждой только один раз. Каждый новый прыжок коня обозначается следующим числом. На диаграмме показано движение коня по квадрату (конь прыгнул на b3 – пишем «2», на а5 – пишем «3», b7 – «4»).
Кто больше займёт клеток на нарисованном квадрате доске, прежде чем все ходы у коня закончатся, – тот чемпион!
Всеволод Викторович Костров
Задайте вопрос или Оставьте свой комментарий
Шахматная доска как расставить 15 коней
Какое наибольшее число коней можно расставить на шахматной доске так, чтобы каждый бил не более семи из остальных?
Решение
Пример расстановки 60 коней: заняты все клетки, кроме клеток центрального квадрата 2×2.
Покажем, что при удовлетворяющей условию расстановке не менее четырёх клеток останутся свободными (то есть больше 60 коней расставить не удастся). Рассмотрим центральный квадрат 4×4. Если в нём четыре поля свободны, все доказано.
Пусть свободных полей в нем не больше трёх, тогда коней там не меньше 13. Каждый из них атакует 8 клеток доски, хотя бы одна из которых свободна. Легко проверить, что фиксированную клетку кони, стоящие в центральном квадрате, атакуют не более четырёх раз. Следовательно, свободных клеток не меньше 13 : 4 > 3, то есть не меньше 4.
Ответ
Замечания
Источники и прецеденты использования
| олимпиада | |
| Название | Турнир городов |
| Турнир | |
| Номер | 26 |
| Дата | 2004/2005 |
| вариант | |
| Вариант | осенний тур, основной вариант, 8-9 класс |
| задача | |
| Номер | 3 |