Шахматная доска как расставить 15 коней
Перейти к содержимому

Шахматная доска как расставить 15 коней

  • автор:

Шахматная доска как расставить 15 коней

1. Шахматный конь стоит в левом нижнем углу доски. Может ли он через а) 4; б) 5; в) 1803 хода вернуться на исходное поле?

Ответ. а) да; б) нет; в) нет.

Решение. в) Нет, так как при каждом ходе конь меняет цвет поля, значит, после нечётного числа ходов он может оказаться только на поле противоположного цвета.

2. Из шахматной доски вырезали две противоположные угловые клетки. Можно ли разрезать оставшуюся часть на доминошки? 3. В каждой клетке треугольной доски размером 7 × 7 × 7 сидит жук. В один прекрасный момент каждый жук переполз на соседнюю по стороне клетку.
а) Докажите, что хотя бы одна клетка оказалась при этом свободной.
б) Какое наименьшее число клеток могло оказаться свободными?
в) Задача-конкурс. Придумайте такое «переползание» жуков, чтобы как можно больше клеток оказались пустыми.

Решение. Раскрасим клетки доски в шахматном порядке. Тогда жуки, которые сидели на чёрных клетках, после переползания окажутся на белых, и наоборот. Поскольку клеток одного цвета на 7 больше, чем другого, останется по крайней мере 7 пустых клеток.

4. Можно ли разрезать шахматную доску на доминошки так, чтобы никакие две доминошки не образовали квадрат 2 × 2?

Указание. Противоречие легко получить, если попробовать разрезать доску, начиная с угла.

5. Какое наибольшее число а) ладей; б) королей можно расставить на шахматной доске, чтобы они не били друг друга?

Решение. а) Так как в каждом столбце может стоять не больше одной ладьи, то ладей не может быть больше восьми. Восемь ладей можно поставить, например, на одну из диагоналей.
б) Разобьём доску на 16 квадратиков 2 × 2. Тогда в каждом из них может стоять не больше одного короля. Значит, всего на доске не может быть больше 16 королей. 16 королей можно поставить, например, в левых верхних углах таких квадратиков.

6. На каждом поле доски 11× 11 стоит шашка. Настя и Лена играют в такую игру. За один ход можно убрать одну шашку или любую «полоску» из шашек (несколько шашек, расположенных подряд без пропусков в столбце или строке). Проигрывает тот, кто не может сделать ход. Может ли одна из девочек ходить так, чтобы всегда выигрывать, как бы ни старалась её победить соперница? 7. Можно ли разрезать шахматную доску на 15 вертикальных и 17 горизонтальных доминошек?

Решение. Допустим, так разрезать можно. Раскрасим доску на чёрные и белые горизонтальные полосы.
Тогда вертикальные доминошки займут 15 чёрных и 15 белых клеток. Соответственно, горизонтальным доминошкам достанется 49 чёрных и 49 белых клеток. Но каждая горизонтальная доминошка занимает две клетки одного цвета, значит, все горизонтальные доминошки должны занимать чётное число чёрных и чётное число белых клеток. Получили противоречие.

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!


Шахматная доска как расставить 15 коней

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

Подсказка

В квадрате 3×3 можно обойти ходом коня все клетки, кроме центральной, и вернуться в исходную клетку.

Решение

Если в квадрате 3×3 поставить коней на все клетки, кроме центральной, то каждый конь будет бить ровно двух других. Теперь расположим четыре таких «каре» на доске подальше друг от друга – так чтобы кони из разных каре не били друг друга (см. рисунок).

Источники и прецеденты использования

олимпиада
Название Математический праздник
год
Год 1998
класс
1
Класс 6
задача
Номер 6

Шахматный конь, рекурсия, максимумы

Имеется шахматная доска 8х8. Предположим в каждой клетке доски содержится некоторое количество яблок. Шахматная фигура “конь” может ходить по классическим правилами хода коня. Оказываясь в очередной клетке, конь собирает все яблоки, которые в ней находятся. Имеется ограничения на количество ходов. Ваша программа должна принимать на вход следующие аргументы: максимальное число ходов, имя файла, содержащего схему заполнения шахматной доски яблоками. Строки в файле соответствуют строкам шахматной доски, строки разделяются переносами. Числа в строках разделяются пробелами. Ваша программа должна вывести максимально возможное количество собираемых яблок конем, при заданном ограничении ходов и произвольном выборе начальной позиции. Собственно, хотелось бы понять, каким образом/методом следует решать эту задачу. Сам код мне, конечно, нужен, но думаю и сам смогу написать программу, если пойму её основную идею. Была идея решать через жадный алгоритм, передвигаясь в клетку, содержащую в себе максимально возможное число яблок (сравнивал количество яблок в каждой из клеток, доступных в данный момент и шел в клетку с максимальным числом), но, как мне кажется, это решение, мягко говоря, не совсем верное. Задача должна содержать в себе рекурсию. Подайте идею решения данной проги или посоветуйте литературы по этой теме, пожалуйста. Заранее благодарю! 😀

Отслеживать

81.6k 9 9 золотых знаков 78 78 серебряных знаков 136 136 бронзовых знаков

Глава 11. Перестановочные задачи

Любая шахматная задача связана с какими-нибудь перестановками фигур на доске. Однако к перестановочным, или пермутационным, относят обычно такие задачи па перестановку фигур, задания в которых далеки от обычных. Вот типичный пример задачи с «нешахматным» заданием.

Задача Доусона. У белых лишь король на e1 и пешка на d2; у черных же на доске полный комплект фигур, все они находятся на своих первоначальных местах. Черным разрешается ходить только в том случае, если они дают своим ходом шах. Учитывая это, белые должны заставить черных дать мат их королю.

Конечно, эту задачу. Доусона на обратный мат нельзя считать настоящей шахматной задачей, так как прави/ а игры здесь сильно нарушены. Для того чтобы добить, я своей цели, белый король должен весьма умело перемещаться по доске, вызывая огонь на себя. Он получает мат лишь на 33-м (!) ходу после следующих перемещений:
1-4. Крe1-d1-c2-b3-a4.
Теперь черные воервыо получают возможность сделать ход (дать шах).
4. … b7-b5+
5-6. Крa4-b3-c3 b5-b4+
7. Крc3-d3 Сc8-a6+
8. Крd3-e3
9. d2-d3
(единственный раз в «партии» ход делает белая пешка)
10-13. Крe3-d2-c1-b2-b3 Сa6-c4+
14-20. Крb3-b2-c1-d2-e3-f2-g3-h3 Сc4-e6+
21. Крh3-h4 g7-g5+
22-24. Крh4-g3-h2-h1 Сe6-d5+
25-26. Крh1-g1-f1 Сd5-g2+
27-29. Крf1-e1-d2-c2 b4-b3+
30. Крc2-b2 Сf8-g7+
31. Крb2-a3 Сg7-b2+
32. Крa3-a4 Сg2-c6+
33. Крa4-a5 Сb2-c3
мат!

У Фабеля приводится ряд пермутационных задач на подсчет последовательностей ходов (заданной длины), приводящих одну шахматную позицию к другой. Хотя искомых перестановок ходов может существовать очень много, нахождение каждой из них не представляет труда. Однако, на наш взгляд, более интересны пермутационные задачи, в которых нелегко найти даже одну необходимую перестановку. В этих задачах доска часто имеет причудливую форму, и фигурам на ней очень тесно… Прежде чем перейти к таким задачам, вспомним классическую перестановочную игру-головоломку С. Лойда «Пятнадцать».

В коробочке 4×4 находятся пятнадцать квадратов, занумерованных числами от 1 до 15. Не вынимая квадраты из коробочки, переставить их так, чтобы номера были расположены в возрастающем порядке: 1, 2, …, 15, а пустым был правый нижний угол коробочки.

Пусть начальное расположение квадратов таково: 1, 2, …, 13, 15, 14, т. е. от искомого оно отличается перестановкой двух последних квадратов. За решение головоломки при такой начальной «позиции» Лойд назначил премию в 1000 долларов. Правда, он ничем не рисковал, так как доказал, что задание невыполнимо. Вообще говоря, существует 16! расположений квадратов, и все они распадаются на два равных по численности класса. Расположения первого класса при помощи перестановок квадратов приводятся к искомому виду, а расположения второго класса удается привести только к «позиции» с переставленными квадратами 14 и 15.

Говорят, что в некотором расположении два квадрата образуют транспозицию, если квадрат с большим номером предшествует квадрату с меныпим. Для того чтобы определить, к какому именно виду приводится данное расположение, надо подсчитать число транспозиций в нем. Если это число четно (в частности, ноль), то расположение относится к первому классу и перестановками приводится к «нормальному» виду. Если же число транспозиций нечетно, то положение относится ко второму классу. Подробный анализ игры не входит в наши планы38, ее упоминание здесь объясняется лишь аналогией этой головоломки с некоторыми перестановочными задачами на шахматной доске.

На доске 4×4 расставлены 15 ладей, занумерованных числами от 1 до 15. Переставить ладьи так, чтобы их номера расположились в возрастающем порядке, а пустым было поле в правом нижнем углу доски.

Так как ход ладьи на нашей доске совпадает с перестановкой квадрата в игре «Пятнадцать», то данная задача фактически сводится к ней. Другими словами, существование решения зависит от числа транспозиций ладей в исходной расстановке.

Задача с ладьями легко обобщается и для доски 8×8. Можно показать, что все позиции с 63 ладьями, занумерованными числами от 1 до 63, распадаются на два класса: в половине из 64! позиций ладьи удается расположить в возрастающем порядке (с пустым полем h1), а в половине — нет. Любопытно, что для коней имеет место та же самая ситуация, что и для ладей. Все позиции с 03 занумерованными конями также распадаются на два равных по численности класса39.

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

Рис. 59. «Пистолет» Т. Доусона. Белые начинают и дают мат в 21 ход

Перейдем теперь к рассмотрению других пермутационных задач. В «позиции» на рис. 59 фигуры ходят по обычным правилам, но доска имеет весьма оригинальную форму. Белым на доске-«пистолете» очень тесно, этим и объясняется затянутость решения — 21 ход! Перечислим белые фигуры в том порядке, в каком они делают ходы (в распоряжении черного короля лишь два соседних поля, на которых он и ждет своей участи): К, Л, К, Л, С, Л, К, Л, К, С, К, Л, К, Л, Кр, К, Кр, Л, Кр, К, Л:С мат.

На рис. 60,а — в изображены знаменитые зигзаги немецкого шахматного композитора В. Шинкмана. Конечно, во всех трех задачах цель должна быть достигнута кратчайшим путем. Первая перестановка осуществляется за 26 ходов, а для второй требуется на один ход больше. Третья же задача представляет собой настоящий пермутационный рекорд! Здесь для перестановки короля и ферзя (остальные фигуры должны вернуться на исходные места) приходится совершить 107 (!!) перемещений. Приведем решения двух первых зигзагов, а перестановку в последней марафонской задаче предлагаем наиболее терпеливым читателям провести самостоятельно.

1) С, Ф, Кр, С, Л, Ф, С, Л, С, Кр, С, Ф, Кр, С, Л, Ф, Л, С, Л, С, Л, С, Кр, С, Ф, Кр; 2) С, Л, Кр, С, Лc2-c1 (здесь мы пользуемся полной шахматной нотацией, чтобы указать, какая именно ладья идет на c1), С, Л, Лd1-c1, С, Л, С, Кр, Л, С, Кр, С, Л, С, Лc3-c2, С, Кр, Л, Кр, Лc2-d2, С, Кр, Крb1:a1.

Рис. 60. Зигзаги В. Шинкмана:
а — король попадает на a1, не проходя через b2;
б — белый король берет черного коня (при этом конь неподвижен, а король не становится под шах);
в — король и ферзь меняются местами

Рис. 61. Метод пуговиц и нитей:
а — вадача Гуарини; б — поля доски с номерами; в — распутанный клубок из пуговиц в нитей

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

В противоположных углах шахматной доски 3×3 стоят два белых и два черных коня (рис. 61,а). За минимальное число ходов поменять местами белых коней с черными.

Эта задача, придуманная итальянцем Гуарини еще в XVI в., хорошо известна математикам, часто предлагалась на различных олимпиадах и конкурсах. Наиболее изящно она решается при помощи так называемого метода пуговиц и нитей, придуманного известным изобретателем головоломок Г. Дьюдени (об этом методе и его авторе можно прочитать у Гарднера).

Занумеруем поля нашей маленькой доски, как показано на рис. 61,б (центральное поле осталось без номера, но оно нас сейчас не интересует, так как кони все равно не могут на него попасть). После этого поместим на каждое из занумерованных полей по пуговице и если между двумя полями возможен ход коня, то расположенные на них пуговицы свяжем нитью. Полученный клубок пуговиц и нитей распутаем так, чтобы все пуговицы расположились по кругу (рис. 61,в).

Теперь решение находится почти автоматически. Выбрав одно из направлений по кругу, достаточно переставлять коней до тех пор, пока они не поменяются местами. Необходимое перемещение на доске получается заменой занумерованных пуговиц соответствующими полями. Нетрудно убедиться, что решение состоит из 16 перестановок коней (8 ходов белых и 8 ходов черных), причем белые и черные кони могут ходить по очереди. Если дополнительно потребовать, чтобы кони. разного цвета при своем движении не угрожали друг другу (очередность ходов в этом случае произвольна), то решение также непосредственно следует из рис. 61,в. Нужно следить лишь за тем, чтобы белые и черные кони не оказались на нашем круге рядом. Будем считать, что круговое движение (против часовой стрелки) начинает белый конь a1 (на нем помещена пуговица с номером 1). Тогда в шахматной нотации решение можно записать так: Кa1-b3, Кa3-c2, Кc3-b1-a3, Кc1-a2-c3, Кb3-c1-a2, Кc2-a1-b3, Кa3-c2-a1, Кc3-b1-a3, Кa2-c3, Кb3-c1.

Поменять местами белых и черных коней (рис. 62,а; 63,а) так, чтобы они ходили по очереди и кони разного цвета не угрожали друг другу.

Хотя доска на рис. 62,а больше, и на каждой стороне по три, а не по два коня, метод пуговиц и нитей также позволяет быстро найти необходимую перестановку. Распутанный клубок показан на рис. 62,б. Решение состоит из 22 ходов (11 белых и 11 черных):
1. Кa1-b3 Кa4-b2
2. Кb1-c3 Кb4-c2
3. Кc1-a2 Кc4-a3
4. Кb3-c1 Кb2-c4
5. Кc3-a4 Кc2-a1
6. Кa2-c3 Кa3-c2
7. Кc1-a2 Кc4-a3
8. Кa4-b2 Кa1-b3
9. Кc3-a4 Кc2-a1
10. Кa2-b4 Кa3-b1
11. Кb2-c4 Кb3-c1.

Рис. 62. Задача о перестановке коней: а — исходное расположение коней; б — распутанный клубок

Рис. 63. Метод пуговиц и нитей на необычной доске:
а — исходное расположение коней; б — распутанный клубок

Доска на рис. 63,а имеет довольно причудливую форму, но для метода пуговиц и нитей это не является препятствием. Распутывая клубок, получаем картину, изображенную на рис. 63,б (здесь в кружках записаны обозначения самих полей необычной доски). В данной ситуации поле c3 является «транзитным» — связь между «ветками» a2 — d3 и b1 — b3 возможна только через него.

Из рис. 63,б находим, что для достижения цели необходимо произвести следующие маневры. Сначала перевести через транзит на c3 всех трех коней левой ветки (a4, b2, d3) на правую, причем для экономии времени расположить их на полях b1, a3, c2. Теперь черному коню a2 надо перебраться на d3, а белым коням следует вернуться на левую ветку (поля a4, b2). После этого второй черный конь c2 временно располагается на a2 и пропускает белых коней на правую ветку (поля b1, a3). Наконец, этому коню надо с a2 пройти на b2, а белым занять поля a4, a2, после чего все кони окажутся на нужных местах. Хотя план не сложен, для его выполнения требуется целых 40 ходов. Заметим, что поля a1, b3 в решении не используются, и их можно было бы вырезать, придав доске еще более причудливую форму.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *