Логическая задача на расставление костей домино на шахматной доске


Оглавление (нажмите, чтобы открыть):

Bookitut.ru

Домино на шахматной доске.

Юный Николас очень хотел стать членом «Клуба любителей шахмат и шашек» своего города, но в клуб принимали только взрослых.

Ему же неизменно отказывали в приеме, считая, что он еще не дорос.

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

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

Однажды вечером юный Николас по обыкновению торчал в клубе, наблюдая за игрой мастеров. В ответ на робкую просьбу разрешить и ему сыграть партию, Николасу с насмешкой посоветовали научиться сначала играть в детскую игру домино.

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

— А ты попробуй, тогда поймешь.

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

Не скрывая насмешливых улыбок, присутствовавшие при разговоре члены клуба окружили Николаса и с интересом выслушали его сообщение.

Как хорошо известно каждому из нас, начал Николас солидным тоном, — шахматная доска состоит из 64 квадратных полей, по 8 полей вдоль каждой из сторон. Если бы мы попытались покрыть всю шахматную доску домино, то, так как каждый камень домино имеет форму прямоугольника шириной в одно поле и длиной в два поля, нам для этого понадобилось бы 32 домино. Предположим, что у нас всего лишь 31 домино. Тогда независимо от того, как мы будем располагать их на шахматной доске, два поля останутся непокрытыми. Если я начну укладывать домино на шахматную доску, оставив непокрытым поле в левом верхнем углу доски, и буду укладывать домино вплотную друг к другу, пока не исчерпаю весь запас из 31 камней, ясно, что еще одно поле должно остаться непокрытым. Задача состоит в том, чтобы это непокрытое поле оказалось в правом нижнем углу доски.

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

Завсегдатаи клуба переглянулись и согласились, что предложенная юным Николасом задача действительно интересна. Затем любители шахмат и шашек приступили к решению. Они раздобыли комплект из 31 домино и принялись усердно выкладывать их на шахматную доску то одним, то другим способом, но, как ни бились, покрыть доску домино так, чтобы поле в правом нижнем углу доски осталось свободным, им не удавалось.

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

— Но откуда вы знаете, что задача неразрешима? — спросил Николас.

— А как же? — удивился один из завсегдатаев клуба. — Мы перепробовали укладывать домино на шахматную доску всевозможными способами, и ни один из них не привел к желаемому результату, поэтому решение невозможно.

— Думаю, что вы правы, — признал юный Николас, — хотя и не объяснили, почему задача неразрешима.

— Как почему? — в один голос воскликнули завсегдатаи клуба. — Потому что нам не удалось найти его.

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

— А какой ответ может быть более обоснованным? — искренне удивились члены клуба.

— Хотя бы следующий, — пояснил юный Николас. — Я бы предложил рассматривать задачу с такой точки зрения. Поскольку на любой шахматной доске число черных и белых полей одинаково, а каждый камень домино покрывает ровно одно черное и одно белое поле, то два поля, оставшиеся непокрытыми, должны быть различного цвета. Между тем угловые поля, стоящие на противоположных концах диагонали, одного цвета. Следовательно, как бы вы ни покрывали шахматную доску камнями домино, вам не удастся расположить домино так, чтобы угловые поля на одной диагонали остались свободными. Перед нами, джентльмены, любопытный образчик задачи, в которой введение на первый взгляд ничего не значащего условия упрощает решение. В действительности же все, что необходимо для формулировки задачи, это квадрат (доска), разлинованная в «клеточку» на 8 х 8 меньших квадратов. Шахматная раскраска меньших квадратов здесь пи при чем — все квадраты могут быть одного цвета. Другое дело, что для решения задачи нам придется разделить квадраты на две группы — одни могут быть черными, а другие белыми. И такое разделение позволяет легко и просто решить задачу!

Логическая задача на расставление костей домино на шахматной доске

Георгий Гамов, Марвин Стерн

Теодору фон Карману — большому любителю задач-головоломок.

George Gamow. Marvin Stern

MacMillan & Co Ltd

Перевод с английского Ю. А. Данилова

Рисунки Ребекки Файлз

Графика Георгия Гамова

Предисловие к русскому изданию

Жанр занимательной науки давно известен и любим в России. Предлагаемая вниманию читателя книга известного физика и популяризатора науки Георгия Антоновича Гамова (1904–1968) и сотрудника американской авиастроительной фирмы «Конвэр» Марвина Стерна — признанная жемчужина жанра. Она привлекает внимание оригинальностью, неожиданностью и красотой задач, сюжеты которых заимствованы авторами из научного фольклора, подсказаны учеными-коллега- ми, известными (астрофизиком Виктором Амазасповичем Амбарцумя- ном, специалистом по аэро- и гидродинамике Теодором фон Карманом и биохимиком Альбертом Сент-Дьерди) и не очень, а в большинстве своем придуманы авторами как бы специально для читателя.

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

На русском языке книга Георгия Гамова и Марвина Стерна издается впервые.

О волны, откройте мне вечную тайну,

Решите загадку, что мучила столько голов —

Голов в париках, ермолках, чалмах и беретах,

И сотни тысяч других, что ищут ответа и сохнут.

Скажите, что есть человек?

Откуда пришел он? Куда он идет?

И кто живет в вышине, на далеких сверкающих звездах?

Пролог. Как появилась на свет эта книга

Летом 1956 года одному из нас (Г. Г.) приходилось часто бывать в Сан-Диего (Калифорния) в качестве консультанта самолетостроительной фирмы «Конвэр», в которой в качестве постоянного сотрудника работал другой из авторов (М.С.). Нам приходилось обсуждать множество (секретнейших!) проблем, а поскольку рабочий кабинет одного из нас (М. С.) находился на шестом этаже главного здания и был более комфортабельным, другой из нас (Г. Г.) обычно садился в лифт на втором этаже, где находился его рабочий кабинет. Для этого один из нас (Г. Г.) шел к лифту на втором этаже и нажимал кнопку, и первым обычно приходил лифт, который шел не в том направлении, которое было нужно, т. е. шел вниз. Примерно в пяти случаях из шести первым приходил лифт, который шел вниз, и только в одном случае — лифт, который шел вверх

— Послушайте, — сказал один из нас (Г. Г.) другому (М. С.), — вы что, непрерывно изготовляете на крыше новые лифты и спускаете их на склад в подвале?

— Что за нелепая идея! — возмутился другой (М.С.). — Разумеется, ничего такого мы не делаем. Предлагаю вам подсчитать, сколько раз первым приходит лифт, идущий в нужном вам направлении, когда вы покинете мой кабинет на шестом этаже и будете возвращаться к себе на второй этаж.

Через несколько недель разговор снова зашел о лифтах, и один из нас (Г. Г.) вынужден был признать, что его первое замечание относительно лифтов было лишено смысла. Ожидая вызванного лифта на шестом этаже, он обнаружил, что примерно в пяти случаях из шести первым приходил лифт, идущий вверх, а не вниз. И Г. Г. быстро предложил объяснение этому загадочному явлению, противоположное первому: должно быть, компания «Конвэр» строила лифты в подвале и посылала готовые лифты на крышу, откуда производимые компанией самолеты доставляли их к месту назначения.

— Позвольте, — прервал его другой (М. С.), — я и не знал, что наша компания занимается производством лифтов… Разумеется, — продолжал он, — настоящее объяснение очень просто. Но позвольте мне прежде заметить, что если бы я и не знал, сколько этажей в этом здании, то теперь, располагая той информацией, которую вы мне сообщили, смог бы сказать, что в здании семь этажей.

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

— Верно, но разве вы не понимаете, что это классическая задача, которая лишь наглядно показывает, чем частота отличается от фазы?

Поразмыслив немного, мы нашли решение задачи (его вы найдете в истории «Проходящие поезда», стр. 48–51), но наши беседы позволили нам выяснить одно немаловажное обстоятельство: оказалось, что мы оба очень любим различного рода математические задачи-головоломки и каждый из нас знает превеликое множество их.

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

Лондеролл, Вудз Хоул, Массачусетс

М. Стерн, Г. Гамов

1. Великий султан

Двенадцать и одна

Великий султан Квазиабабии ибн-аль-Каз сидел в своей сокровищнице, с удовольствием взирая на выстроенные в ряд у стены двенадцать больших кожаных мешков, набитых большими серебряными монетами. В мешках были подати, собранные эмиссарами султана в двенадцати провинциях, которыми он правил. На каждом мешке было отчетливо написано имя сборщика податей — эмиссара соответствующей провинции. Одна монета весила целый фунт[1], а так как все мешки были почти полными, то серебра было собрано много.

Внезапно дверь в сокровищницу отворилась, и стража ввела какого- то человека в лохмотьях, который бросился перед султаном на колени.

— Государь, — воскликнул он, воздев руку, — я пришел, чтобы сообщить тебе нечто очень важное.

— Говори, — повелел ибн-аль-Каз.

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

— Кто твой хозяин? — спросил ибн-аль-Каз, грозно нахмурясь, — клянусь Аллахом, что завтра же ему отрубят голову, а ты получишь большую награду!


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

Возможно, кому-нибудь покажется несложным делом определить, в котором из двенадцати мешков содержатся облегченные монеты, если бы у султана были достаточно точные весы, которые позволили бы отличить полновесные монеты в 16 унций серебра и облегченные монеты в 15 унций серебра. У султана, действительно, были такие весы, и он их очень любил. Их изготовил по его заказу лучший специалист по точным измерительным приборам в Соединенных Штатах Америки, и были они сделаны по образу и подобию весов, которые в этой высокоразвитой индустриальной стране встречаются буквально на каждом шагу. У весов была платформа, на которую ставили взвешиваемый груз, и прорезь, в которую нужно было опустить монету в один пенни. Вместо того чтобы показывать вес стрелкой на шкале, весы отпечатывали чек с указанием точного веса в фунтах и унциях и полным предсказанием судьбы на обороте. Беда была в другом: среди всех сокровищ у султана ибн-аль-Каза была только одна американская монетка достоинством в один пенни. На платформу весов султан мог выложить серебряные монеты из всех мешков в любом ассортименте, но получить он мог только один чек с напечатанным точным весом всех монет на платформе.

Принятые в Квазиабабии торговые единицы веса воспроизводят систему единиц, имевших хождение в Англии, США и Странах Содружества до введения метрической системы. В 1 торговом фунте 16 унций (453,59 г). В 1 унции 28,35 г. (Унция делилась на 16 драхм (по 1,77 г), драхма — на 3 скрупулы (по 0,59 г) и скрупула — на 10 гран (по 0,059 г)). — Прим. перев.

Petruchek.Info

Домино на шахматной доске

Одна костяшка домино покрывает две клетки шахматной доски.

Покрыть 31 костяшкой все клетки, кроме двух противоположных (на одной диагонали).

Шахматная доска состоит из 8×8 = 64 клеток.

Все клетки на одной диагонали — одного цвета. Доска без двух угловых клеток (с одной диагонали) содержит 30 клеток одного цвета и 32 клетки другого цвета.

Каждая доминошка покрывает 1 белую и 1 чёрную клетку.

Из доски 6х6 вырезали угловые квадраты 2х2. Логическая задача на расставление костей домино на шахматной доске. Раскраски. Разрезания. Замощения

На этом занятии мы поговорим о раскрасках и том, как они помогают решать задачи. Рассмотрим нестандартные задачи на разрезания и замощения и способы их решения.

Конспект занятия «Разрезания. Замощения. Раскраски.»

Раскраски. Разрезания. Замощения.

Задачами на разрезание увлекались многие ученые с древнейших времен. Решения многих простых задач на разрезание были найдены еще древними греками, китайцами, но первый систематический трактат на эту тему принадлежит перу Абул-Вефа, знаменитого персидского астронома Х века, жившего в Багдаде. Геометры всерьез занялись решением задач на разрезание фигур на наименьшее число частей и последующее составление из них той или иной новой фигуры лишь в начале XX века. Одним из основоположников этого увлекательного раздела геометрии был знаменитый составитель головоломок Генри Э. Дьюдени. Особенно большое число существовавших ранее рекордов по разрезанию фигур побил эксперт австралийского патентного бюро Гарри Линдгрен. Он является ведущим специалистом в области разрезания фигур.

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

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

Задача 1: Взяли квадрат клетчатой бумаги размером 8×8, отрезали от него две клетки (левую нижнюю и правую верхнюю). Можно ли полученную фигуру полностью покрыть «доминошками» — прямоугольниками 1× 2?

Задача 2. Можно ли выложить шахматную доску тридцатью двумя доминошками так, чтобы 17 из них были расположены горизонтально, а 15 – вертикально?

Задача 3: Можно ли разрезать квадрат клетчатой бумаги размером

4× 4 на один пьедестал, один квадрат, один столбик и один зигзаг?

Задача 4: Можно ли выложить квадрат 8 × 8, используя 15 прямоугольников 1 × 4 и один уголок вида ?

Задача 5: Можно ли выложить прямоугольник 6 × 10 прямоугольниками 1 × 4?

Задача 6: Можно ли сложить квадрат 6 × 6 с помощью 11 прямоугольников 1 × 3 и одного уголка вида ?

Задача 7: На каждой клетке доски 5 × 5 сидит жук. В некоторый момент времени все жуки взлетают и приземляются на соседние по стороне клетки. Докажите, что при этом окажется хотя бы одна пустая клетка.

Задача 8: Из доски 8 × 8 вырезали угловую клетку. Можно ли оставшуюся часть разрезать на прямоугольники 3 × 1?

Задача 9: Фигура «верблюд» ходит по шахматной доске ходом типа (1, 3). Можно ли пройти ходом «верблюда» с произвольного поля на соседнее?

Задача 10: Можно ли доску размером 10 × 10 покрыть фигурами вида ?

Задача 11: Дана доска 12 × 12. В левом нижнем углу стоят 9 шашек, образуя квадрат 3 × 3. За один ход можно выбрать какие-то две шашки и переставить одну из них симметрично относительно другой (не выходя при этом за пределы доски). Можно ли за несколько ходов переместить эти шашки так, чтоб они образовали квадрат 3 × 3 в правом нижнем углу?

Задача 12: В каждой клетке квадрата 9 × 9 сидит жук. По команде каждый жук перелетает на одну из соседних по диагонали клеток. Доказать, что по крайней мере 9 клеток после этого окажутся свободными.

Задача 13: Замок имеет форму правильного треугольника, разделенного на 25 маленьких залов той же формы. В каждой стене между залами проделана дверь. Путник ходит по замку, не посещая более одного раза ни один из залов. Найти наибольшее число залов, которое ему удастся посетить.

Задача 14: На какое наибольшее количество ромбов можно разрезать равносторонний треугольник, разбитый на 36 равносторонних треугольников?

Задача 15. В квадрате 7×7 клеток размещено 16 плиток размером 1×3 и одна плитка 1×1. Докажите, что плитка 1×1 либо лежит в центре, либо примыкает к границам квадрата.

Задача 16. В левый нижний угол шахматной доски 8×8 поставлено в форме квадрата 3×3 девять фишек. Фишка может прыгать на свободное поле через рядом стоящую фишку, то есть симметрично отражаться относительно её центра (прыгать можно по вертикали, горизонтали и диагонали). Можно ли за некоторое количество таких ходов поставить все фишки вновь в форме квадрата 3×3, но в другом углу.

Задача 1: Можно ли квадрат 5 × 5 разрезать на прямоугольники 1 × 2 (доминошки).Задача 2: Из шахматной доски 8 × 8 вырезаны противоположные угловые клетки. Можно ли остаток разрезать на прямоугольники 1 × 2 (доминошки)? Решение: Нет. Каждая доминошка занимает одну чёрную и одну белую клетки, а на доске без углов чёрных и белых клеток разное число.Задача 3: Из противоположных углов доски 10 × 10 вырезаны два квадрата 3 × 3. Можно ли остаток разрезать на доминошки?Задача 4: Придумать связную фигуру на шахматной доске, в которой поровну черных и белых клеток, но которую нельзя разбить на доминошки.Задача 5: Можно ли разрезать квадрат 10 × 10 на 25 фигур ?Задача 6: Решение: Раскрасьте доску в шахматном порядке. Чёрных клеток окажется чётное число, а в каждую фигурку их попадёт одна или три.Задача 7: Можно ли разрезать квадрат 10 × 10 на 25 фигур ? Решение:

Раскрасьте доску в четыре цвета (см. рисунок). Каждая фигурка занимает по одной клетке каждого цвета, а клеток первого и второго цвета разное число.

Задача 8: Можно ли разрезать квадрат 10 × 10 на 25 фигур ? Решение: Покрасьте вертикаличерез одну.Задача 9: Доказать, что доску 8 × 8 без угловой клетки нельзя разрезать на прямоугольники 1 × 3.Задача 10: Можно ли доску 8 × 8 разрезать на один квадрат 2 × 2 и 15 фигур вида ?Задача 11: Квадрат a)5 × 5b)8 × 8 разбили на несколько прямоугольников 3 × 1 и один квадрат 1 × 1. Где может стоять квадрат 1 × 1? Решение: а) В центре, b) На третьей клетке по диагонали от любого угла.

Указание: раскрасьте доску в три цвета.

Задача 12: Какое максимальное количество брусков 1 × 1 × 4 можно вырезать из куба 6 × 6 × 6?Задача 13: Прямоугольник разбит на фигурки и . Одну из потеряли, но заменили ее на . Доказать, что новым набором покрыть исходный прямоугольник нельзя.Задача 14: Можно ли квадрат 16 × 16 разбить на 64 прямоугольника 1 × 4, из которых 31 будут стоять вертикально, а остальные 33 — горизонтально? Решение: Покрасьте каждую четвёртую вертикаль.Задача 15: При каких n квадрат n × n можно разбить на a) ;

b) ? Решение: При n, кратных четырём.

Задача 16: Прямоугольник m × k разбит на прямоугольники 1 × n. Доказать, что m делится на n или k делится на n.

c) для любого n. Решение:

Раскрасьте в n цветов.

Задача 17: Доказать, что прямоугольник m × n можно разбить на прямоугольники a × b, тогда и только тогда, когда выполняются следующие условия:

1) m и n представляются в виде ka + lb (k и l — целые неотрицательные числа)

2) m и n делится на a.

3) m или n делится на b.

Задача 18: Прямоугольник m × n называется прочным, если его можно разбить на доминошки так, что любой разрез прямоугольника пересекает хотя бы одну доминошку. Доказать, что:

a) прямоугольник 2 × n — непрочный

b) прямоугольник 3 × n — непрочный

c) прямоугольник 4 × n — непрочный

d) прямоугольники 5 × 6 и 6 × 8 — прочные

e) если прямоугольник m × n — прочный, то и прямоугольник m × (n + 2) — прочный.

f) * прямоугольник 6 × 6 — непрочный

g) Какие прямоугольники являются прочными, а какие нет? Решение: f) Подсказка: каждая линия в квадрате 6 × 6 пересекает чётное число доминошек.

g) Все прямоугольники m × n, где mn чётно, m,n ≥ 5, кроме 6 × 6.

Уголком называется фигура вида .

a) Можно ли прямоугольник 5 × 9 разбить на уголки?

b) Доказать, что прямоугольник со сторонами,большими 100 и площадью, делящейся на 3, можно разбить на уголки.

c) Какие прямоугольники можно разбить на уголки, а какие — нет?


Можно ли доску 2 n × 2 n без угловой клетки разбить на уголки? Решение: Да, можно. Разбиение строится по индукции.

Задача 21: При каких n доску (2n + 1) × (2n + 1) без угловой клетки можно разбить на доминошки, среди которых поровну вертикальных и горизонтальных? Решение: При чётных n.

Глава 2. Задачи о шахматной доске

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

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

Можно ли покрыть домино квадрат размером 8×8, из которого вырезаны противоположные угловые клетки (рис. 2,а)?

Мы могли бы воспользоваться алгебраическими рассуждениями , однако «шахматное» решение и проще, и изящнее. Окрасим наш урезанный квадрат в черно-белый цвет, превратив его в шахматную доску без двух угловых полей a8 и h1 (рис. 2,б). При любом покрытии доски каждое домино покрывает одно белое и одно черное поле. У нас же белых полей на два меньше, чем черных (вырезанные поля — белые), и поэтому необходимого покрытия не существует! Как мы видим, раскраска доски не только позволяет шахматисту легче ориентироваться во время игры, но и служит средством решения математических задач.

В рассмотренной задаче существенным было не то, что из доски вырезаны угловые поля, а то, что они одного цвета. Ясно, что какую пару одноцветных полей ни вырезать, покрыть домино оставшуюся часть доски не удастся. Таким образом, возникает следующая задача.

Пусть теперь на шахматной доске вырезаны два поля разного цвета. Всегда ли можно покрыть оставшуюся часть доски 31 домино?

Оказывается, что всегда. Эффектное доказательство нашел известный американский математик Р. Гомори. Проведем на шахматной доске границы между вертикалями и горизонталями так, как показано на рис. 3. В лабиринте между этими границами черные и белые поля следуют друг за другом, чередуясь, как пуговицы двух цветов на замкнутой нити (путь, по которому можно обойти этот лабиринт, является замкнутым). Какие бы два поля разного цвета мы ни вырезали из доски, нить разорвется: в одном месте, если вырезанные поля находятся рядом, и в двух местах — в противном случае. При этом каждый кусок нити будет состоять из четного числа полей. Следовательно, эти куски, а значит — и всю доску, покрыть домино можно!

Рис. 3. Лабиринт Гомори

Любопытные идеи, связанные с пуговицами и нитями, мы еще встретим в главе 11.

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

Задачи о шахматной доске и домино составляют лишь небольшую часть огромной серии задач такого сорта. Американский математик С. Голомб создал целую науку, которую назвал полимипо, а его книга, посвященная этой теме, переведена во многих странах мира, в том числе у нас . В общем случае полимино представляет собой односвязную фигуру, состоящую из квадратов. С точки зрения шахматиста односвязность означает, что все квадраты полимино можно обойти ходом ладьи. В зависимости 07 числа квадратов, полимино бывают различного тига. Мономино содержит один квадрат, домино — два, тримино — три, тетрамино — четыре, пентамино — пять, гептамино — шесть квадратов и т. д. В задачах о полимино покрываются разнообразные доски, не обязательно прямоугольные. Мы остановимся еще на нескольких вопросах, связанных с обычной шахматной доской. Очевидно, покрыть дсску только прямыми тримино, т. е. домино 3×1, невозможно, так как 64 не делится на 3. Возникает следующая задача.

Можно ли покрыть шахматную доску 21 прямым тримино и одним мономино? Если это возможно, то какие поля может занимать мономино?

Одно из необходимых покрытий дапо на рис. 4,а. Для определения возможных расположений мономино проведем на доске две системы параллельных прямых, как показано на рис. 4,б.

Легко убедиться, что при любом покрытии каждое тримино покрывает ровно одно поле, через которое проходит сплошная линия, и ровно одно, через которое проходит пунктирная линия. Поскольку число полей, пересекаемых сплошными прямыми, равно 22, так же как и число полей, пересекаемых пунктирными прямыми, а тримино имеется 21, то мономино может покрывать лишь поля, пересекаемые обоими семействами прямых. А таких полей — всего четыре: c3, c6, f3 и f6! Поворачивая доску на 90, 180 и 270°, можно получить соответствующие покрытия для каждого из этих четырех полей.

Следующая задача несколько отличается от рассмотренных выше.

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

Если представить себе, что доска — это стенка, а домино — кирпичи, то существование указанной границы (шва) свидетельствует о непрочной кладке. Иначе говоря, в задаче спрашивается, можно ли расположить «кирпичи» так, чтобы «стенка» не рухнула. Прямоугольник, который удается покрыть необходимым образом, называется «прочным». В «прочности» шахматной доски можно убедиться на рис. 5. В общем случае Гарднер показывает, что из домино можно сложить «прочный» прямоугольник, если его площадь четна, а длина и ширина больше четырех, при этом исключение составляет лишь квадрат 6×6.

Ниже мы будем часто иметь дело с прямоугольными шахматными досками того ила иного размера. При этом всегда считается, что доска m×n имеет m вертикалей и n горизонталей (шахматных). Мы говорим, что доска «четна», если число ее полей четно, и «нечетна» — в противном случае. Всюду, где размеры доски не указаны, имеется в виду стандартная шахматная доска, для которой m = n = 8.

Доска 100×4 покрыта домино. Доказать, что ее можно распилить по одной из границ между вертикалями и горизонталями, не затрагивая ни одного домино.

Любая из указанных границ делит доску на две части, состоящие из четного числа полей. Поля каждой части разобьем на два класса: покрытые домино, целиком лежащими в этой части, и покрытые домино, пересекаемыми границей. Так как число полей каждой части четно (быть может, нуль), равно как и число полей первого класса (каждое домино покрывает два поля), то и число полей второго класса четно. А это и значит, что число домино, пересекаемых границей, четно. Всего разделяющих границ существует 102 (99 вертикальных и 3 горизонтальных), н если каждая из них пересекает домино, то в покрытии участвует не менее 102×2 = 204 домино. В нашем же распоряжении их только 200! Фактически мы показали, что прямоугольник 100×4 является «непрочным».

Вопрос о возможности покрытия произвольной прямоугольной доски линейными k-мино (домино k×1) решается следующей теоремой .

Доску m×n можно покрыть линейными k-мино в том и только в том случае, если хотя бы одно из чисел m или n делится без остатка на k.

Проиллюстрируем теорему на следующем примере.

Можно ли покрыть доску 10×10 (на такой доске играют в стоклеточные шашки) прямыми тетрамино?

Прямое тетрамино имеет размеры 4×1, и, значит, в принципе 25 костей могли бы покрыть все поля нашей доски. Однако из теоремы следует, что это невозможно — 10 не делится на 4.

Рассмотрим еще несколько задач о шахматной доске. В решении следующей задачи виовъ используется ее раскраска.

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

Задание невыполнимо. Действительно, если бы указанное смещение фигур существовало, то каждая «белая» фигура (стоящая на белом поле) стала бы «черной» (попала на черное поле), а каждая «черная» — «белой».

Таким образом, доска состояла бы из одинакового числа белых и черных полей, а это противоречит ее «нечетности».

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

На полях a1, b2, c3, d4 стоят четыре коня. Разрезать доску на четыре конгруэнтные части (совпадающие при наложении) так, чтобы на каждой из них оказалось по коню.

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

Рис. 6. Задача Лойда о четырех конях

Пусть после нескольких разрезов доски образовавшиеся части разрешается перекладывать так, чтобы следующий разрез мог рассечь не одну, а сразу несколько частей. Сколько разрезов потребуется для получения 64 отдельных полей доски (квадратов 1×1)?

Сначала разрежем доску пополам, затем обе половины положим рядом и разрежем доску на четыре одинаковые части и т. д. Всего понадобится 6 разрезов (2 е = 64) и меньшим числом не обойтись.

Пусть теперь части доски разрешается резать только отдельно. Сколько разрезов понадобится для получения 64 полей в этом случае?

Как правило, эта задача (особенно, если она предлагается после предыдущей) вызывает определенные трудности. Видимо, это связано с некоторой инерционностью нашего мышления. Ведь сразу видно, что понадобится 63 разреза! Действительно, каждый разрез увеличивает число частей на единицу; при этом в начальный момент мы имеем одну часть (саму доску), а в конечный — 64 (все поля доски).

Рис. 7. Три задачи на необычной доске

В задаче на рис. 7,а требуется выполнить три задания, причем одно математическое и два чисто шахматных:

а) разрезать доску на четыре конгруэнтные части;

б) заматовать черного короля кратчайшим путем при ходе белых;

в) заматовать черного короля кратчайшим путем при ходе черных верные играют кооперативно).

Решения: а) как нужно разрезать доску, показано на рис. 7,б; б) при ходе белых мат дается на 12-м ходу: 1-12. Сe1-b4, Крe3-d3-c4, Сe4-c2-b3, Крc4-c3, Сb4-d6, Сb3-d5, Крc3-c2, Сd6-c5, Сd5-c4, Сd6-b4 мат (все ходы черного короля вынуждены и не приводятся); в) при правильной игре после 1. … Крe6-e7 мат невозможен, так как черный король скрывается на e8 — 2. Сe1-b4+ Крe7-e8, и чернопольный слон вынужден уйти с диагонали a3 — e7 ввиду угрозы пата. Однако если черные играют кооперативно (помогают белым дать мат), то цель достигается всего через три хода:
1. … Крe6-d6
2. Крe3-d4 Крe6-e7
3. Сe1-b4+ Крe7-e6
4. Сe4-d5 мат.
Ряд полей нашей доски при матовании не используется, но при их исключении не было бы задачи на разрезание доски.

Рис. 8. Парадокс с разрезанием шахматной доски: а) 8×8 = 64; б) 13×5 = 65

Рассмотрим теперь один известный парадокс, связанный с разрезанием шахматной доски. Разрежем доску на четыре части, как показано на рис. 8,а (в данном случае нам невыгодно раскрашивать ее поля), и из образовавшихся частей сложим прямоугольник (рис. 8,б). Площадь доски равна 64, а площадь полученного прямоугольника равна 65. Таким образом, при разрезании доски откуда-то взялось одно лишнее поле!

Разгадка парадокса состоит в том, что наши чертежи выполнены не совсем точно (мы умышленно провели толстые линии, чтобы скрыть неточности). При аккуратном построении чертежа на рис. 8,б вместо диагонали прямоугольника появится ромбовидная, чуть вытянутая фигура со сторонами, которые кажутся почти слившимися. Площадь этой фигуры как раз будет равна «лишней» единице.

Известный популяризатор математики начала века Е. Игнатьев придумал «метод шахматной доски», позволяющий выводить различные формулы . Приведем два несложных примера на эту тему.

Найдем сумму n первых натуральных чисел «методом шахматной доски». Для этого на доске (n + 1)×n (на рис. 9,а n = 8) окрасим в чериый цвет все поля первой вертикали, все поля второй вертикали (кроме верхнего), третьей вертикали (кроме двух верхних) и т. д., наконец — нижнее поле n-й вертикали. В результате белых и черных полей на нашей доске будет поровну, а именно 1 + 2 + … + n. Поскольку вся доска состоит из п (n + 1) полей, получаем
2 (1 + 2 + … + n) = n(n + 1),

откуда вытекает известная формула для суммы арифметической прогрессии:
1 + 2 + … + n = n(n + 1)/2.

Теперь докажем такую формулу:
8(1 + 2 + … + n) + 1 = (2n + 1)².

Для этого возьмем доску (2n + 1)×(2n + 1) и закрасим ряд ее полей черным цветом так, как показано на рис. 9, 6 (для случая n = 5). Очевидно, каждая черная часть содержит (1 + 2 + … + n) полей. Без учета центрального поля мы имеем здесь четыре одинаковые белые и черные части. Необходимая формула следует из того, что наша доска содержит (2n + 1)² полей и состоит из центрального поля и восьми одинаковых частей (четырех белых и четырех черных — рис. 9,б).

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

В заключение главы приведем одно старинное доказательство на шахматной доске… теоремы Пифагора. Нарисуем на доске квадрат, как показано на рис. 10,а. Доска разбивается на этот квадрат и четыре конгруэнтных прямоугольных треугольника. На рис. 10, 6 мы видим те же четыре треугольника, а также два квадрата. Итак, треугольники в обоих случаях занимают одну и ту же площадь. Следовательно, одну и ту же площадь занимают и оставшиеся части доски без треугольников, на рис. 10,а — одного квадрата, а на рис. 10,б — двух. Поскольку большой квадрат построен на гипотенузе прямоугольного треугольника, а маленькие — на его катетах, то «пифагоровы штаны во все стороны равны»!

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

Именно такое решение дано в книге Т. Саати «Целочисленные методы оптимизации и связанные с ними экстремальные проблемы» (М., «Мир», 1973).

С. Голомб. Полимино. М., «Мир», 1974.

Она доказана А. Сойфером в статье «Клетчатые доски и полимипо» («Квант», 1972, № 11); там же приведен ряд новых задач о полимино.


Е. Игнатьев. В царстве смекалки, или арифметика для всех. Кн. 1 — 3. М. — Пг., Госиздат, 1923.

Дана шахматная доска размером 8×8, из которой были вырезаны два противоположных по диагонали угла, и 31 кость домино; каждая кость домино может закрыть два квадратика на поле. Можно ли вымостить костями всю доску? Дайте обоснование своему ответу.

Решение

С первого взгляда кажется, что это возможно. Доска 8×8, следовательно, есть 64 клетки, две мы исключаем, значит остается 62. Вроде бы 31 кость должна поместиться, правильно?

Когда мы попытаемся разложить домино в первом ряду, то в нашем распоряжении только 7 квадратов, одна кость переходит на второй ряд. Затем мы размещаем домино во втором ряду, и опять одна кость переходит на третий ряд.

В каждом ряду всегда будет оставаться одна кость, которую нужно перенести на следующий ряд, не имеет значения сколько вариантов раскладки мы опробуем, у нас никогда не получится разложить все кости.

Шахматная доска делится на 32 черные и 32 белые клетки. Удаляя противоположные углы (обратите внимание, что эти клетки окрашены в один и тот же цвет), мы оставляем 30 клеток одного и 32 клетки другого цвета. Предположим, что теперь у нас есть 30 черных и 32 белых квадрата.

Каждая кость, которую мы будем класть на доску, будет занимать одну черную и одну белую клетку. Поэтому 31 кость домино займет 31 белую и 31 черную клетки. Но на нашей доске всего 30 черных и 32 белых клетки. Поэтому разложить кости невозможно.

Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.
Если он вам понравился, то рекомендуем купить книгу

Доказать, что клетчатую доску 10 х 10 нельзя разрезать по линиям сетки на прямоугольники 1 х 4. (Решения по Д.Ю. Кузнецову.)

Решение 1 . Разделим доску на квадраты 2х2 и раскрасим их в шахматном порядке (рис.1). Заметим, что любой прямоугольник 1х4 содержит поровну (по 2) чёрных и белых клеток, но при данной раскраске на доске 52 чёрных клетки и 48 белых, т.е. не поровну. Значит, разрезать доску 10х10 на прямоугольники 1х4 не удастся.

Решение 2 . Раскрасим доску диагональной раскраской в 4 цвета (рис.2). Заметим, что любой прямоугольник содержит по одной клетке каждого из четырёх цветов, но при данной раскраске на доске по 25 клеток 1-го и 3-го цветов, 26 клеток – 2-го и 24 клетки – 4-го, т.е. не поровну. Значит, разрезать доску 10х10 на прямоугольники 1х4 не удастся.

1. Из шахматной доски вырезали нижнюю правую и левую угловые клетки. Можно ли полученную фигуру разрезать на доминошки 1х2? А если вырезать нижнюю правую и верхнюю левую?

2. Можно ли доску 6х6 разрезать на доминошки, так чтобы среди них было ровно 11 горизонтальных? (Горизонтальная раскраска в два цвета.)

3. Раскрасьте рисунок в четыре цвета так, чтобы соседние части были покрашены в разные цвета. Можно ли обойтись тремя цветами? (См. Занятие 6: Раскраска географической карты — 5-6 класс).

4. В квадрате 4×4 клетки левой половины покрашены в чёрный цвет, а остальные в белый. За одну операцию разрешается перекрасить в противоположный цвет все клетки внутри любого прямоугольника. Как за три операции из первоначальной раскраски получить шахматную?

5. Несколько кузнечиков сидят на одной прямой, причём расстояния между соседями — одинаковы. Каждую минуту один из них прыгает в точку, симметричную ему относительно другого кузнечика. Может ли через некоторое время кузнечик Саша оказаться на том месте, где в начале сидел его сосед Лёша?

6. а) Можно ли разрезать шахматную доску на фигурки, состоящие из 4 клеток в форме буквы «Т»?

б) Можно ли разрезать на такие фигурки шахматную доску 10×10?

7. Можно ли разбить квадрат 8×8 с отрезанным уголком на прямоугольники 1×3?

8. Можно ли доску 10×10 разрезать на фигурки из четырёх клеток в форме буквы»Г»? (Горизонтальная раскраска в два цвета.)

9. Доска 8×8 разрезана на доминошки размером 2×1. Может ли быть 15 вертикальных и 17 горизонтальных доминошек?

10. Треугольник разбит на треугольнички (25 штук), как показано на рисунке. Жук может ходить по треугольнику, переходя между соседними (по стороне) треугольничками. Какое максимальное количество треугольничков может пройти жук, если в каждом он побывал не больше одного раза?

11. Какое наибольшее количество ромбов, каждый из которых составлен из двух равносторонних треугольников со стороной 1, можно вырезать из равностороннего треугольника со стороной 5 (см. рис. предыдущей задачи).

12. Треугольный замок разделён на 100 одинаковых треугольных залов. В середине каждой стены сделана дверь. Сколько залов может осмотреть человек, не желающий нигде побывать больше одного раза?

Математика шахмат (задачи и решения)

Объект изучения – математические задачи на шахматную тему.

Цель работы:

  • собрать и прорешать математические задачи, сюжетом которых является шахматная доска и шахматные фигуры;
  • классифицировать математических задач на шахматную тему по типам;
  • выявить используемые при решении таких задач математические методы.

Все представленные в работе задачи мною прорешаны. Условия задач взяты из сборников олимпиадных математических задач, книги Е. Я. Гика «Математика на шахматной доске», а также использованы материалы математического кружка в лицее, который я посещаю уже третий год.

Скачать:

Запомните эту страницу: Ссылка на эту страницу Подпишитесь на обновления (RSS) login — register ПРИСЛАТЬ ЗАДАЧУ
Вложение Размер
Математика шахмат 908.5 КБ

Предварительный просмотр:

ученица 7Д класса

Карпенко Светлана Викторовна,

«Игра в шахматы существовала еще до появления на Земле человека и, может быть, даже до сотворения мира. Если мир впадет в хаос, игра в шахматы останется вне пространства и времени свидетельством вечного существования идей» – так высоко оценил искусство игры в шахматы Бонтемпелли. Я изучила много разных сложных шахматных позиций, это большой труд, но и огромное интеллектуальное наслаждение.

Но вот я решила взглянуть на шахматы несколько с другой стороны – математической. Конечно, между математикой и шахматами много общего. Игра в шахматы – это в первую очередь решение математических проблем. Выдающийся ученый Г. Харди, проводя параллель между этими видами человеческой деятельности, заметил, что решение проблем шахматной игры есть не что иное, как математическое упражнение, а игра в шахматы это как бы насвистывание математических мелодий. Понимая огромное значение математики для развития интеллекта, многие великие шахматисты увлекались решением математических задач и головоломок. В качестве примера можно привести таких шахматистов как Эммануил Ласкер, Михаил Ботвинник и Макс Эйве. Кстати, М. Эйве сказал, что «в математике не меньше логики и красоты, чем в шахматах».

Объект изучения – математические задачи на шахматную тему.

Целью моей работы:

  • собрать и прорешать математические задачи, сюжетом которых является шахматная доска и шахматные фигуры;
  • классифицировать математических задач на шахматную тему по типам;
  • выявить используемые при решении таких задач математические методы.

Все представленные в работе задачи мною прорешаны. Условия задач взяты из сборников олимпиадных математических задач, книги Е. Я. Гика «Математика на шахматной доске», а также использованы материалы математического кружка ЦДМО, который я посещаю уже… лет.

Особенностью моей работы является то, что я попыталась не просто решить задачи, а разделила их по типам. Вот что у меня получилось:

  • задачи на раскрашивание шахматной доски;
  • задачи на разрезание шахматной доски;
  • задачи на нахождение числа фигур на шахматной доске, числа путей передвижения фигур;
  • лабиринты на шахматной доске;
  • задачи о перестановках фигур на шахматной доске.

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

1. Задачи на раскрашивание шахматной доски

Задача 1. Художник-авангардист Змий Клеточкин покрасил несколько клеток доски размером 88, соблюдая правило: каждая следующая закрашиваемая клетка должна соседствовать по стороне с предыдущей закрашенной клеткой, но не должна — ни с одной другой ранее закрашенной клеткой. Ему удалось покрасить 36 клеток. Побейте его рекорд!

Решение: Можно закрасить 42 клетки, закрасить 43 клетки невозможно. Примеры ответов изображены на рис.1 а,б .

Задача 2. Поля клетчатой доски размером 88 будем по очереди закрашивать в красный цвет так, чтобы после закрашивания каждой следующей клетки фигура, состоящая из закрашенных клеток, имела ось симметрии. Покажите, как можно, соблюдая это условие, закрасить: а) 26; б) 28 клеток. (В качестве ответа расставьте на тех клетках, которые должны быть закрашены, числа от 1 до 26 или до 28 в том порядке, в котором проводилось закрашивание.)

Задача 3. Отметьте на доске 88 несколько клеток так, чтобы любая (в том числе и любая отмеченная) клетка граничила по стороне ровно с одной отмеченной клеткой.

Задача 4. В квадрате 77 клеток закрасьте некоторые клетки так, чтобы в каждой строке и в каждом столбце оказалось ровно по три закрашенных клетки.

Решение: рис.4 а,б .

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

2. Задачи на разрезание шахматной доски

Среди математических задач и головоломок о шахматной доске наиболее популярны задачи на разрезание доски.

Задача 5. Разрежьте изображённую на рисунке 5, а доску на 4 одинаковые части, чтобы каждая из них содержала 3 заштрихованные клетки.

Задача 6. Четыре алмаза.

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

После смерти властелина его сын, слабый игрок и жестокий деспот, решил отомстить мудрецам, обыгравшим его отца. Он велел разделить им шахматную доску с алмазами на четыре одинаковые по форме части так, чтобы каждая заключала в себе по одному алмазу. Хотя мудрецы выполнили требование нового властелина, он все равно лишил их жизни, причем, как гласит легенда, для казни каждого мудреца использовал его часть доски с алмазом.


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

Решение: Одно из решений задачи представлено на рис.6. Располагая четырех коней на различных полях доски, можно получить множество задач о разрезании. Интерес в них представляет не только нахождение одного необходимого разреза, но и подсчет числа всех способов разрезать доску на четыре одинаковые части, содержащие по одному коню. Установлено, что наибольшее число решений (800) задача имеет при расположении коней в углах доски.

Задача 7. На какое максимальное число частей можно разрезать шахматную доску, если считать разными части, отличающиеся своей формой или цветом полей при совмещении.

Решение: Максимальное число частей равно 18. На рис.7 представлены два разреза. Решение на рис.7, а принадлежит Лойду; особенность его состоит в том, что одна из частей содержит восемь полей (максимум). В решении на рис.7, б , отличающемся внешней симметрией, ни одна часть не содержит более пяти полей. На рис.7, а части 17 и 18, или 8 и 9, хотя и имеют одинаковую форму, отличаются цветом полей при совмещении. Другие части, например, 3 и 6, вообще не могут быть совмещены (переворачивать их нельзя).

Задача 8. Какое максимальное число полей доски можно пересечь одним разрезом?

Решение: Поля доски образуются в результате пересечения 18 прямых – девяти вертикальных и девяти горизонтальных. С каждой из них прямая-разрез может пересечься лишь в одной точке, но из четырех прямых, образующих края доски, она пересекается лишь с двумя. Отсюда следует, что наша прямая пересекает прямые, образующие поля доски, самое большее в 16 точках. Эти точки разбивают прямую не более чем на 15 отрезков, каждый из которых заключен внутри какого-нибудь поля. Таким образом, любой разрез доски пересекает не более 15 полей. Из рис.8 следует, что ровно столько полей пересекает разрез, проведенный параллельно диагонали доски и проходящий через середины сторон двух угловых клеток.

Задача 9. Сколько нужно провести разрезов на доске, чтобы пересечь все ее поля?

Решение: Семь прямых могут пересечь все 64 поля доски. Для этого одну прямую нужно провести почти в диагональном направлении через центр доски, а шесть других – в направлениях почти параллельных второй диагонали доски (рис.9).

3. Шахматная доска и домино

Задачи про шахматную доску и домино можно считать частным случаем задач на разрезание доски.

Задача 10. Можно ли целиком покрыть домино квадрат 88, из которого вырезаны противоположные угловые клетки (рис. 10,а)?

Решение: Предполагается, что каждое домино имеет размеры 21 и покрывает два соседних поля доски, а каждое поле покрывается одной половинкой домино. Можно было бы заняться алгебраическими рассуждениями, но шахматное решение гораздо проще. Окрасим урезанный квадрат в черно-белый цвет, превратив его в шахматную доску без двух угловых полей a8 и h1 (рис.10, б ). При любом покрытии доски каждое домино покрывает одно белое и одно черное поле. У нас же черных полей на два больше, чем белых, и поэтому необходимого покрытия не существует! Таким образом, раскраска доски не только позволяет шахматисту легче ориентироваться во время игры, но и служит средством решения математических головоломок.

Задача 11. Пусть на шахматной доске вырезаны два поля разного цвета. Всегда ли можно покрыть оставшуюся часть доски 31 домино?

Решение: Оказывается, что всегда. Проведем замкнутую линию, как показано на рис.11. Если из доски вырезаны соседние поля, то разорванная линия будет состоять из одного куска, проходящего через 62 поля, при этом цвета полей чередуются. Если мы станем размещать домино вдоль этой линии, то закроем всю оставшуюся часть доски. Если вырезанные поля не являются соседними, то линия разорвется на две части, проходящие через четное число полей, и каждую из них можно покрыть домино.

Задача 12. Пусть из шахматной доски вырезано некоторое количество полей. При каком наименьшем числе таких полей на оставшуюся часть доски нельзя поместить ни одного домино?

Решение: Достаточно вырезать из доски 32 поля одного цвета – либо белые, либо черные, и на ней не останется места ни для одного домино.

Задача 13. Можно ли покрыть шахматную доску 21 прямым тримино и одним мономино? Если можно, то какие поля занимает при этом мономино?

Решение: Одно из покрытий показано на рис. 12, а . Для определения возможных расположений мономино проведем на доске две системы параллельных прямых, как показано на рис. 12, б . Легко убедиться, что при любом покрытии доски каждое тримино покрывает ровно одно поле, через которое проходит сплошная прямая, и ровно одно, через которое проходит пунктирная прямая. Поскольку число полей, пересекаемых сплошными прямыми, равно 22, как и число полей, пересекаемых пунктирными прямыми, а тримино имеется 21, то мономино может занимать лишь поля, пересекаемые обоими семействами прямых. А таких полей всего четыре: c3, c6, f3 и f6. Поворачивая доску на 90°, 180° и 270°, можно получить соответствующее покрытие для каждого из этих четырех полей.

Задачи на раскрашивание и разрезание доски, по-моему, самые легкие математические шахматные задачи. Для решения таких задач единого алгоритма нет, нужны небольшие математические расчеты, хорошее внимание и, конечно, строгие логические рассуждения.

4. Задачи на нахождение числа фигур на шахматной доске,

числа путей передвижения фигур

4.1. Неторопливый король

Король – самая медленная фигура в шахматах. С любого места он может переступать только на соседние поля доски. Однако необычное измерение расстояний на доске лучше всего иллюстрирует движущийся король.

Задача 14. Сколькими способами король с поля е1 может добраться кратчайшим путем до поля d8?

Решение: Очевидно, что кратчайшее путешествие короля до цели занимает семь ходов, причем он может перемещаться любыми зигзагообразными путями, оставаясь при этом внутри прямоугольника e1-a5-d8-h4. Для подсчета искомого числа путей составим таблицу чисел, которые будем помещать прямо на полях доски (рис. 13). Число, стоящее на данном поле равно числу кратчайших путей до него с поля e1. На поля d2, e2 и f2 король может попасть кратчайшим путем единственным способом, и поэтому на них стоят единицы. По той же причине единицы стоят на полях c3 и g3. На d3 за два хода король попадает двумя способами, а на e3 – тремя. В общем случае число кратчайших путей до данного поля складывается из одного, двух или трех чисел, стоящих на полях предыдущей горизонтали, с которых король попадает на данное поле в один ход. Пользуясь этой закономерностью, мы, в конце концов, заполним всю таблицу и получим, что с поля e1 до поля d8 король может добраться кратчайшим путем 357 способами.

Задача 15. Какое максимальное число королей можно расставить на доске так, чтобы они не угрожали друг другу, т.е. не стояли рядом?

Решение: Разобьем доску на 16 квадратов (рис. 14). Если мы хотим, чтобы короли не касались друг друга, то, очевидно, в каждом из этих квадратов надо поместить не более одного из них. Это означает, что больше шестнадцати королей, удовлетворяющих условию задачи, расставить невозможно. Итак, максимальное число мирных королей на доске 88 равно 16.

Задача 16. Какое наименьшее число королей можно расставить на шахматной доске так, чтобы они нападали на все свободные поля доски?

Решение: В каждом из девяти прямоугольников, выделенных на рис. 15, имеется одно поле (на нем стоит король), которое может быть атаковано только королем, находящимся в этом же прямоугольнике. Следовательно, для того чтобы все свободные поля доски были под угрозой, в каждом из наших девяти прямоугольников должен стоять хотя бы один король. Число девять и является решением задачи для обычной доски.

Задача 17. Двое по очереди передвигают короля, стоящего на доске. Игрок, вынужденный поставить его на поле, которое король уже посетил, проигрывает. На чьей стороне победа?

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

4.2. Ферзь на шахматной доске

Ферзь – самая сильная шахматная фигура. Существует множество задач о ферзе. Я думаю, самая распространенная из них – это задача о восьми ферзях.

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

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

Многие известные математики пытались решить эту задачу, среди них: М. Беццель, Ф.Наук, В. Аренс. Однако строгое доказательство того, что 92 расстановки исчерпывают все возможности, было получено Д. Глэшером только спустя более 100 лет после открытия этой задачи. Как уже было сказано всего решений 92, но основные из них 12. Остальные получаются при помощи симметрии.

Задача 19. На бесконечной доске находятся два белых ферзя и черный король. За сколько ходов белые могут поставить мат?

Решение: Оказывается, каковы бы ни были размеры доски, и как бы ни располагались в начальный момент два белых ферзя и черный король, мат дается не позднее четвертого хода! Первым ходом один из ферзей объявляет шах по вертикали; в ответ на отступление короля на одну из соседних линий вторым ходом другой ферзь зажимает короля на двух вертикалях. При этом возникает позиция подобная той, что изображена на рис. 17. На любое движение короля на третьем ходу следует соответствующий горизонтальный шах и мат следующим ходом, например 2. Крe4 3. Фc4+ Крe5 (e3) 4. Фf4

4.3. Прямолинейная ладья

Ладья – строгая, прямолинейная фигура. Она тоже часто встречается в математических задачах.

Задача 20. Какое наименьшее число поворотов должна сделать ладья при обходе всех полей доски nn?

Решение: Ладья должна была сделать хотя бы один ход вдоль каждой вертикали или вдоль каждой горизонтали. Пусть, ладья двигалась хотя бы раз вдоль каждой вертикали. На любую из них, кроме тех, где маршрут начался и закончился, ладья должна была войти и после движения вдоль нее выйти. При этом вход и выход обязательно происходят с поворотами. Таким образом, общее число поворотов не меньше, чем 2( n –2)+1+1=2( n –1). Для любого n маршрут, содержащий ровно столько поворотов, можно получить из маршрута, приведенного на рис. 18, а ; при n =8 ладья делает 2(8–1)=14 поворотов. Этот маршрут является открытым, замкнутый маршрут состоит уже из 16 ходов (рис. 18, б ).

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

5. Лабиринты на шахматной доске. Ход конем

Совсем не обязательно быть шахматистом, чтобы знать, какая шахматная фигура самая удивительная. Конечно, это конь! Не случайно выражение «ход конем» стало крылатым и прочно вошло в наш быт. А один из самых остроумных гроссмейстеров, С. Тартаковер, прямо считал, что «вся шахматная партия – это один замаскированный ход конем». Основное свойство коня, которое отличает его от других фигур, состоит в том, что он на каждом своем ходу меняет цвет поля, на котором стоит. Многие задачи о коне удается эффектно решить, если воспользоваться указанным свойством.

Задача 21. Задача о коне Аттилы. На доске находятся две фигуры – белый конь и черный король. Некоторые объявляются «горящими». Конь должен дойти до неприятельского короля, повернуть его и вернуться в исходное положение. Ему запрещено занимать как «горящие» поля, так и поля, уже пройденные им однажды.

«Трава не растёт там, где ступил мой конь!» – похвалялся вождь гуннов Аттила, когда хотел сказать, что его полчища уничтожают всё живое на своём пути. На рис. 19, а конь Аттилы расположен на g4, а неприятельский король – на b3. Горящие поля выделены.

Соединяя отрезками все пары доступных коню полей, между которыми возможен его ход, получаем граф коня для данной задачи (полям доски соответствуют вершины графа) – рис. 19, б . В результате дело сводится к нахождению в графе такого пути, который не содержит ни одной вершины более одного раза и, кроме того, проходит через обе выделенные (на рисунке они обведены кружками).

Методы решения подобных задач, называемых лабиринтами, хорошо известны в теории графов. Впрочем, для коня Аттилы искомый путь нетрудно найти и непосредственно. Он содержит 18 ходов: Кg4-f6-е8-g7-е6-f8-g6-е7-с6-а5:b3-d2-b1-а3-b5-d6-f7-h6-g4. Для достижения цели коню пришлось побывать на 18 полях из 35, не сожжённых в начале сражения.

Задача 22. Может ли конь с поля a1 добраться до h8, побывав на каждом поле доски ровно один раз?

Решение: Не может. Исходное поле a1 – черное, и, значит, на каждом нечетном ходу конь попадает на белое поле. Однако число 63 (именно на 63-м ходу конь прибывает в противоположный угол доски) нечетно, а поле h8 – черное.

Все оказалось довольно просто, но любопытно, что за доской шахматист иногда сталкивается с подобными вопросами. Рассмотрим, например, позицию, изображенную на рис.20. Белым здесь удается добиться ничьей единственным путем – 1. Крc1! Теперь их король будет переходить с c1 на c2 и обратно, занимая каждый раз поле того цвета, что и конь, и не выпуская черного короля из заточения. В случае 1. Крc2 конь попадал на d3 при короле на c2, и пешка проходила в ферзи.

Задача 23. Обойти конем все поля шахматной доски, посетив каждое из них ровно один раз.

Эта задача известна, по крайней мере, с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию» (26 апреля 1757 г.). В письме к Гольдбаху он сообщал: «…Воспоминание о предложенной когда-то мне задаче послужило для меня недавно поводом к некоторым тонким изысканиям, в которых обыкновенный анализ, как кажется, не имеет никакого применения…. Я нашел, наконец, ясный способ находить сколько угодно решений (число их, однако, не бесконечно), не делая проб». Помимо рассмотрения задачи для коня, Эйлер разобрал аналогичные задачи и для других фигур.

Хотя задача была известна и до Эйлера, лишь он впервые обратил внимание на ее математическую сущность, и поэтому задачу часто связывают с его именем.

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

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

Рис. 21. Прохождения коня через все клетки поля шахматной доски 5 × 5.

Известно много методов для нахождения маршрутов коня, которые носят имя первооткрывателей – метод Эйлера и Вандермонда, рамочный метод Мунка и Коллини, метод деления на четверти Полиньяка и Роже и др.

Вот самое простое правило построения маршрутов коня.


Правило Варнсдорфа: при обходе доски коня следует всякий раз ставить на поле, из которого он может сделать наименьшее число ходов на еще не пройденные поля; если таких полей несколько, то можно выбрать любое из них.

Правило Варнсдорфа было предложено более 150 лет назад. Долгое время считалось, что оно действует безукоризненно. Но позднее было установлено, что его вторая часть не совсем точна. Если в распоряжении коня имеется несколько возможностей, упомянутых в первой части правила, то не все они равноценны. Машинный эксперимент показал, что произвольное применение второй части правила Варнсдорфа приводит коня в тупик.

Однако на практике правило Варнсдорфа действует весьма эффективно, и даже при вольном использовании его второй части вероятность заблудиться невелика. Иногда завершить маршрут коня удается даже в том случае, если его начальный путь сделан без всякой системы. На рис. 22, а конь, начав путешествие с поля a1, уже прошел 40 ходов. В этой трудной ситуации, пользуясь правилом Варнсдорфа, конь благополучно заканчивает маршрут. С поля 40 он мог бы пойти, кроме поля f2, на поля c5, d6, f3 и g3. Но каждое из этих полей связано с тремя свободными, а поле f2 – с двумя (hi и d3), этим и объясняется выбор, – число 41 ставится на поле f2. Дальше у коня выбор между полями h1 и d3. Второе поле связано с четырьмя свободными, а первое – только с одним, и число 42 ставится на h1. С этого поля ход определяется однозначно – на поле g3, которое и получает номер 43. Теперь у коня имеется выбор между полями h5 и f5, причем каждое из них связано с тремя свободными. Согласно правилу, можно выбрать любое из них, в нашем случае конь идет на h5 (номер 44). Продвигаясь далее таким же образом, конь в конце концов обойдет всю доску и последним, 63-м ходом, закончит маршрут на поле c6, которое получит номер 64 (см. рис. 22, б ).

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

Со времен Эйлера известен так называемый «раздельный ход коня», который заключается в нахождении пути по одной половине доски, его симметричном дублировании и соединении обеих путей вместе (рис. 24). Для половины шахматной доски – доски 8×4 – найдено точное число маршрутов коня. Это позволило подсчитать число «раздельных ходов коня» на доске 8×8, которое и дает нижнюю границу для числа всех решений задачи.

Для того чтобы обойти конём все шахматные клетки и ни разу не побывать дважды на одной и той же, к тому же сделать это «вслепую», начав или закончив на любой клетке по желанию «зрителя», можно благодаря мнемоническому стихотворению:

Алеет Осень Ценными Дарами,

Еще Один Животворящий День.

Хлеба Червонят Желтыми Шнурами,

Хрустальных Вод Философична Сень.

Два Вечера Цеплявшиеся Шишки

Артист Писал, Бездонна Синева.

Дорожный Шлак Целуют Червячишки,

Еще Покрыта Флоксами Трава.

Дымится Чай Эффектней Шоколада,

Фарфоры Чашек Достаются Трем,

Блондинке Девушка Дана Отрада

Форшмак Делить Холодным Острием.

Жена, Толкая Хилую Подругу,

Желает Сняться Этим Выходным,

Ценя Сама Арктическую Вьюгу,

Бросает Шар Арбуза Четверым.

Цикад Пяток, Едва Чревовещая,

Дарует Дрему Фикусам Окна.

Хотя Довольны Жаждавшие Чая,

Хозяин Шумно Жертвует Вина.

Фокстротами Шесть Девушек Пленились,

Эстрадных Танцев Фантастичней Па,

Едва Ступающий Цыпленок Вылез,

А Селезень Блуждающий Пропал.

Алеет Тело Бронзовой Осины,

Царит Теней Ажурная Длина.

Беззвучней, Чем Автомобиля Шины,

Болоту Ветер Дарит Семена.

Фонарь Восьмью Химерами Сияет,

Жук Прилетает, Хлопая, Туда.

Желанна Осень, Если Довершает

Ценнейший Отдых Бодрого Труда.

Первые буквы задают координаты ходов: Алеет Осень = А1; Ценными Дарами = С2; и т. д. В каждую строфу вставлена подсказка, помогающая не перепутать последовательность строф: ещё ОДИН, ДВА вечера, достаются ТРЁМ и т.д.

Значительно труднее проблема, состоящая не в отыскании определенного маршрута коня по доске, а в нахождении всех маршрутов и подсчете их числа. Однако эта задача не решена до сих пор.

6. Задачи о перестановках фигур на шахматной доске

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

Задача 24 «Пятнадцать». В коробочке 44 находятся пятнадцать квадратов, пронумерованных числами от 1 до 15. Требуется, не вынимая квадраты из коробочки, переставить их так, чтобы номера шли в возрастающем порядке.

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

Всего существует 16! Расположений квадратов, и все они распадаются на два равных по численности класса. Расположения первого класса приводятся при помощи перестановок к нужному расположению квадратов, а расположения второго удается при помощи перестановок привести к нужной позиции, только с переставленными квадратами 14 и 15.

Как определить к какому из двух классов принадлежит данная позиция? Для этого нужно посчитать число транспозиций в ней. Два квадрата образуют транспозицию тогда, когда квадрат с большим номером предшествует квадрату с меньшим. Оказывается, что если число транспозиций чётно, то позиция относится к первому классу, а если нечётно, то ко второму.

Задача 25. На доске 44 расставлены 15 ладей, пронумерованных числами от 1 до 15. Требуется переставить ладьи так, чтобы их номера расположились в возрастающем порядке, а пустым осталось поле d1.

Так как ходы ладьи на доске 44 совпадают с перемещениями квадратов в игре «пятнадцать», эта задача о ладьях изоморфна игре Ллойда. То есть существование ее решения зависит от числа транспозиций ладей в данной позиции (если число транспозиций четно, то решение существует, если нечетно – нет решения).

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

Задача 26. Старинная головоломка.

Эту задачу придумал итальянец Гуарини ещё в XVI в. Она встречается в книгах по занимательной математике. В углах доски размером 33 стоят два белых и два чёрных коня (рис. 25, а ). Требуется поменять местами белых и чёрных коней за наименьшее число ходов.

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

Теперь задача решается почти автоматически. Выбрав одно из направлений движения по кругу, будем переставлять коней до тех пор, пока они не поменяются местами. Чтобы переместить коней на доске, нужно заменить пуговицы соответствующими полями. Нетрудно убедиться, что решение состоит из 16 перемещений коней (восьми белых и восьми чёрных), причём кони противоположного цвета могут ходить по очереди. Если дополнительно потребовать, чтобы кони разного цвета при движении не угрожали друг другу (очерёдность ходов в этом случае позволяется нарушать), то решение тоже найдём на рис. 25, в . Необходимо только следить за тем, чтобы белые и чёрные кони не оказались соседями в клубке. Если круговое движение (против часовой стрелки) начинает белый конь а1, то решение будет такое: Ка1-b3, Ка3-с2, Кс-b1-а3, Кс1-а2-с3, Кb3-с1-а2, Кс2-а1-b3, Ка3-с2-а1, Кс3-b1-а3, Ка2-с3, Кb3-с1.

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

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

При написании работы я открыла для себя целый новый мир – шахматную математику.

У меня получилась следующая классификация найденных и прорешанных математических задач на шахматную тему:

  • задачи на раскрашивание шахматной доски;
  • задачи на разрезание шахматной доски;
  • задачи на нахождение числа фигур на шахматной доске, числа путей передвижения фигур;
  • лабиринты на шахматной доске;
  • задачи о перестановках фигур на шахматной доске.

В работу я поместила лишь некоторые задачи. Но, по моему мнению, их достаточно для того, чтобы показать, что шахматная математика привлекательна и интересна для молодых людей. Многие шахматные задачи до сих пор не решены и заслуживают пристального внимания и приложения интеллектуальных сил. Сейчас при решении задач на помощь к человеку приходит компьютер. Им уже поставлено много рекордов. Сейчас компьютеры могут решать окончания с семью фигурами и меньше, находя порой невероятные решения. К примеру, программисты Марк Буржуцкий и Яков Коновал обнаружили фантастический результат для семифигурного окончания «ферзь и конь против ладьи, слона и коня», в котором белые выигрывают лишь через 517 ходов! Мы можем только удивляться. Но, кто знает, может быть, в XXII веке дело дойдет и до 32 фигур на доске, и загадка шахмат будет окончательно разгадана?!

Мною были выявлены следующие математические методы, используемые при решении задач на шахматную тему:


  • метод раскраски, разрезания фигур;
  • использование теории игр;
  • использование теории графов;
  • использование комбинаторных вычислений;
  • «метода пуговиц и нитей».

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

  1. Акимова С. Занимательная математика. С-П.: Тригон, 1998.
  2. Гарднер М. Математические головоломки и развлечения. М.: Мир, 1971.
  3. Гик. Е.Я. Шахматы и математика. М.: Наука, 1976г.
  4. Гик. Е.Я. Занимательные математические игры. М. 1987.
  5. Гришин В.Г. Малышы играют в шахматы. М: Просвещение, 1991.
  6. Екимова Н.А., Кукин Г.П. Задачи на разрезание. М.
  7. Игнатьев Е.И. В царстве смекалки. М.: Омега, 1994.
  8. Квант №9. М.: Наука, 1989.
  9. Квант №10. М.: Наука, 1989.
  10. Купцов Л.П., Нестеренко Ю.В. и др. Математические олимпиады школьников. М.: Просвещение, 1999.
  11. Олехник С.Н., Нестеренко Ю.В., Потапов М.К. Старинные занимательные Энциклопедический словарь юного математика. М.: Педагогика, 1985.
  12. Савин А. Математические миниатюры. М.: Детская литература, 1991.
  13. Чулков П.В. Математика: Школьные олимпиады. М., 2004.
  14. Энциклопедия для детей. Том 11. Математика. М.: Аванта+, 2002.
  15. Южаков О.И. Математические олимпиады. Курган: Изд-во ИПК и ПРО, 2004.
  16. Ященко И.В. Приглашение на Математический праздник. М.: МЦНМО, 2005.

Логическая задача на расставление костей домино на шахматной доске

(Стоит почитать и тем, кто не любит «сложных» задач! Эта — совсем не сложная)

«Шахматную доску 8х8 клеток легко покрыть (без перекрытий и пустот) 32-мя костяшками домино (состоящими из двух клеток, то есть, размером 1х2). А можно ли покрыть 31-ой костяшкой домино шахматную доску, из которой вырезали два угловых поля – левое нижнее (a1) и правое верхнее (h8)? «

Начинающие кружковцы не очень понимают такие задачи, где не надо давать численный ответ, а надо ответить на вопрос «можно ли?».

Конечно же, первая мысль почти у всех верная: останется 62 клетки, и в принципе покрыть 62 клетки двухклеточными костяшками можно, т.к. оно чётное, а если костяшек 31, то тоже в принципе можно, т.к. 31*2=62.

Многие совсем начинающие на этом и останавливаются, считая задачу решенной.

Другие рисуют картинку, и пытаются покрыть доску доминошками. Не получается. Пробуют еще — опять не получается. Пробуют долго — никак не получается.
После этого обосновывают свой ответ: «Я очень долго пробовал, и у меня никак не получилось, значит это точно нельзя сделать.»

Антошка (он же на ВМШ ассистирует) придумал интересное возражение на такой ответ: «А если 100 мудрецов 100 дней будут пытаться это сделать вдруг у них получится?»

Тогда дети уже понимают, что они еще не решили задачу, и приходит время немного объяснить им, что от них требуется.

«Вот если бы у кого-то из вас, хотя бы у одного человека получилось — то всё, задача решена, так как найден конкретный ПРИМЕР того, как МОЖНО замостить доску».

А чтобы доказать, что этого сделать нельзя — просто количеством попыток уже не обойтись, надо убедить меня, что как ни старайся — никогда не получится. И желательно, конечно, чтобы это НЕ БЫЛ разбор ВСЕХ ВОЗМОЖНЫХ вариантов раскладок доминошек. Наверное, их очень много.»

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

Но это не объясняет ПОЧЕМУ возникают такие 2 клетки, которые нельзя покрыть.

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

Задачи с доминошками на собеседованиях

По личному опыту, могу сказать, что довольно популярными на собеседованиях являются задачи, так или иначе связанные с покрытиями доминошками каких-либо поверхностей. Условия могут варьироваться, но суть у всех остается одна.

Пример 1

Имеется шахматная доска 8 на 8 клеток, левый нижний и правый верхний углы которой отрезаны.

Можно ли полностью покрыть такую доску доминошками размера 2×1 клетку?

На доске остается четное число клеток (62), так что на первый взгляд решение возможно. Однако, давайте сделаем одну очень простую вещь:

Мы раскрасили клетки через одну. Теперь все становится очевидным. Каждая доминошка может занимать строго две клетки: одну белую и одну черную. Других вариантов не дано. Смотрим, какие клетки на доске отрезаны – обе черные, соответственно мы имеем 32 белых и 30 черных клеткок и полностью покрыть такую доску не представляется возможным.

Условия задачи могут варьироваться, но в целом, задачи на возможность-невозможность сразу бросаются в глаза.

Пример 2

Имеется большой куб сыра 3x3x3 состоящий из 27 одинаковых кубиков сыра и мышонок, который съедая один кубик принимается за соседний с ним по грани кубик сыра. Сможет ли мышонок полностью съесть весь сыр, если центральный кубик заменить на несъедобный муляж?

Задача та же самая, только в пространстве, а не на плоскости. Считаем клеточки: в изначальном раскладе это 14 на 13, после удаления центрального кубика: 14 на 12 и как следствие, решения нет.

Следующими по популярности идут задачи на подсчет количества вариантов решений.

Пример 3

На каждой вырезано по 2 клетке. Количество вариантов покрытия доминошками какой из досок больше? В обоих случаях вырезаны клетки разного цвета, так что все познания с раскраской из предыдущих примеров нам здесь не помогут. Времени на собеседованиях на задачи отводится мало, так что нужно искать какую-то зацепку. А она есть. Исключим из первого варианта все покрытия содержащие вырезанные клетки второй доски, а из второго варианта – первой. (Если так проще представить – то можно считать, что вырезанные клетки изначально покрыты доминошкой – которую нельзя двигать, и, очевидно, что таким образом мы приводим доски к идентичному состоянию и количество вариантов покрытий будет тоже идентичным). После этого рассмотрим нижний угол 3 на 2 клетки. Во втором варианте, левая нижняя клетка может быть покрыта только одним способом. Сопоставим этому покрытию вариант для первой доски:

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

Пример 4

Найти количество вариантов покрытия доминошками доски 2хN клеток.

Пусть ее можно покрыть X(N) способов. Рассмотрим вариант покрытия левой верхней клетки:

Оставшуюся часть в первом случае можно покрыть X(N-1) способами, а во втором, очевидно, X(N-2).
Так как перечислены все варианты покрытия и никакие из них не будут совпадать, то получаем уравнение X(N) = X(N-1) + X(N-2)
X(1) = 1, X(2) = 2, а Х(N) будет равно N+1 числу последовательности Фибоначчи.

Пример 5

Написать программу, вычисляющую количество способов покрытия доски 3xN клеток доминошками.

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

В заключение, для демонстрации, реализация алгоритма “в лоб” на питоне:

from itertools import combinations
# формирование матрици инцидентности опущено для краткости
# оно тривиально
# Например, для доски 2×2 с номерами клеток:
# 1 2
# 3 4
# это:
# mat = [
# [0, 1, 1, 0],
# [0, 0, 0, 1],
# [0, 0, 0, 1],
# [0, 0, 0, 0]
#]
# 1 => 2, 1 => 3, 2 => 4, 3 => 4
# Обратные направления ( напр. 3 => 1 )
# не представляют для нас интереса
N = len(mat)
# создаем итератор со всеми парами вершин
all_edges = combinations(xrange(N), 2)
# фильтруем по матрице инцидентности
edges = [(x,y) for x,y in all_edges if mat[x][y]]
# отфильтровываем все максимальные варианты
matchings = [tuples for tuples in combinations(edges, N/2) \
if len(set(reduce(lambda x, y: x+y, tuples))) == N]
print len(matchings)
# осторожно, сложность O(N!)

Полоски из домино

Задача

а) Сколькими способами можно замостить полосу 2×10 доминошками 2×1? Замощения, получающиеся друг из друга вращением полосы, считаются разными; например, на рисунке 1 изображено два разных замощения полоски 2×3.
б) Тот же вопрос для полосы 3×30.

Подсказка 1

а) Попробуйте искать ответ на поставленный вопрос как частный случай более общей задачи: сколькими способами можно замостить доминошками полосу 2×n для произвольного натурального числа n? Обозначим число замощений такой полосы через an — это даст последовательность чисел. Как связан очередной элемент этой последовательности с предыдущими?

б) Можно ли воспользоваться теми же соображениями, что и в пункте а)?

Подсказка 2

б) Действовать совсем аналогично пункту а) не получится: замостить доминошками фигуру, состоящую из нечетного числа клеток, невозможно. Поэтому нужно рассматривать только полосы четной длины. Пусть bn — число замощений полосы 3×2n доминошками. Как связан очередной элемент этой последовательности с предыдущими?

Решение

а) Для начала заметим, что a1 = 1, a2 = 2 — соответствующие замощения изображены на рис. 2. Далее, предположим, что для некоторого натурального n все значения от a1 до an нам уже известны. Как найти an+1? Для этого рассмотрим левую верхнюю клетку полосы 2×(n + 1). В каждом замощении она покрыта некоторой фигуркой домино, вертикальной или горизонтальной (рис. 3). В первом случае мы можем отрезать эту доминошку, так что оставшаяся фигура будет представлять собой полосу 2×n. Последнее означает, что количество замощений полосы 2×(n + 1), у которых левая верхняя клетка покрыта вертикальной фигуркой домино, совпадает с числом замощений полосы 2×n и равно an. Что же касается второго случая, то в нем со всей определенностью левая нижняя клетка также будет покрыта горизонтальной фигуркой домино, а вместе эти доминошки образуют квадрат 2×2, отрезав который, мы получим полосу 2×(n − 1). Следовательно, количество замощений полосы 2×(n + 1), у которых левая верхняя клетка покрыта горизонтальной фигуркой домино, совпадает с числом замощений полосы 2×(n − 1) и равно an−1.

Суммируя полученные результаты, мы получаем следующее рекуррентное соотношение: an+1 = an + an−1. В этом месте читатель, знакомый с числами Фибоначчи, сразу скажет ответ. Но и не обладая подобным знанием, последовательным вычислением нетрудно найти, что a3 = 3, a4 = 5, a5 = 8, a6 = 13, a7 = 21, a8 = 34, a9 = 55, a10 = 89.

Отметим, что полученное нами соотношение справедливо также для n = 1, если считать, что a = 1: в этом случае равенство an+1 = an + an−1 превращается в 2 = 1 + 1. Указанное соображение будет справедливо и для пункта б), что в ближайшее время сослужит нам добрую службу.

б) К полосе 3×30 применимо аналогичное, хотя и несколько более хитрое рассуждение. Для начала можно заметить, что b = a = 1, b1 = a3 = 3. Далее, предположим, что для некоторого натурального n все значения от b до bn уже известны, и попробуем выразить через них bn+1. Для этого рассмотрим доминошку, которой накрыта левая средняя клетка, — имеется три возможных варианта ее расположения. В одном из них рассматриваемая доминошка горизонтальна, и легко видеть, что количество таких замощений полосы 3×2(n + 1) совпадает с числом замощений полосы 3×2n, которое равно bn. В оставшихся двух вариантах доминошка вертикальна, а каждый из этих вариантов естественным образом разбивается на два случая: в одном из них количество замощений равно bn, а в другом снова возможно подразбиение на два вида слагаемых, и т. д. (рис. 4).

Продолжая рассуждение указанным образом, приходим к выводу, что последовательность bn должна удовлетворять следующему соотношению:

Складывая вместе подобные слагаемые, мы приходим к более компактной версии:

В принципе, полученное соотношение уже вполне пригодно для того, чтобы вычислить b15, особенно если для этой цели использовать компьютер. Но если хочется посчитать искомое значение вручную, удобнее сначала упростить полученное выражение. Для этого достаточно вычесть из обеих частей последней формулы то же соотношение, но выписанное не для bn+1, а для bn. Сделав это, получим

или, после очевидных преобразований:

Последнее выражение позволяет получить ответ довольно быстро даже вручную: b2 = 11, b3 = 41, b4 = 153, b5 = 571, b6 = 2131, b7 = 7953, b8 = 29 681, b9 = 110 771, b10 = 413 401, b11 = 1 542 841, b12 = 5 757 961, b13 = 21 489 003, b14 = 80 198 051, b15 = 299 303 201.


Послесловие

В подсказках к задаче предлагалось подумать над более общим вопросом: сколькими способами можно замостить фигурками домино полоски 2×n и 3×2n? Вполне возможно, что читатель резонно поинтересуется, как обстоит дело с ответом на него. Оказывается, если последовательность удовлетворяет линейному рекуррентному соотношению, то существует формула для ее n-го элемента, которую можно найти, воспользовавшись методом производящих функций. В частности, для чисел Фибоначчи an справедлива формула Бине:

а элементы bn удовлетворяют соотношению

Продемонстрируем на примере последовательности bn, как работает метод производящих функций. Для начала определим производящую функцию этой последовательности — бесконечную формальную сумму вида \( B(x)=b_0+b_1x+b_2x^2+b_3x^3+ \ldots \). Заметим, что если умножить ее на \((1-4x+x^2) \) и раскрыть скобки, то за счет того, что для всех натуральных n выполняется соотношение \( b_=4b_n-b_ \), почти все сократится:

Таким образом, разделив на \((1-4x+x^2) \), с учетом равенств b = 1 и b1 = 3 получим выражение для B(x):

мы можем разложить эту дробь на сумму простейших:

После чего, дважды воспользовавшись формулой для суммы геометрической прогрессии,

убеждаемся, что производящая функция B(x) принимает искомый вид:

Можно не ограничиваться замощениями полос и попытаться перейти к еще более общим вопросам. Рассмотрим какую-нибудь связную область Γ на клетчатой бумаге. Естественно полюбопытствовать, во-первых, можно ли в принципе замостить Γ доминошками, а во-вторых, если это возможно, то сколькими способами. Первое, что приходит в голову — раскрасить клетчатую бумагу в черный и белый цвета, как это делают с шахматной доской, и посчитать, сколько клеток какого цвета входит в область Γ. Так как каждая фигурка домино покрывает две клетки разных цветов, получаем необходимое условие: если замощение области Γ доминошками существует, то число черных и белых клеток внутри Γ совпадает. Однако достаточным указанное условие не является; убедиться в этом помогает пример, изображенный на рис. 5.

Тем не менее, существуют методы, которые не только отвечают на поставленные вопросы, но и делают это за полиномиальное время (это значит, что количество требуемых для ответа на вопрос операций зависит от размера входных данных — размера области Γ в данном случае — как многочлен), то есть довольно быстро. Опишем подход, восходящий к голландскому физику Питеру Кастелейну (Pieter Kasteleyn). Пусть область Γ состоит из n черных и n белых клеток. Пронумеруем их от 1 до 2n таким образом, чтобы сначала шли черные клетки, а затем — белые, после чего сопоставим области Γ матрицу K = (Kuv) размера 2n×2n согласно следующему правилу (здесь \(i=\sqrt<-1>\) — мнимая единица):

Тогда оказывается справедливой теорема Кастелейна, утверждающая, что количество замощений области Γ доминошками равно \(\sqrt<|\det|>\) (det — это определитель матрицы). Учитывая, что соседними клетками могут быть только клетки разных цветов, легко видеть, что матрица K на самом деле имеет блочный вид

\[ A=\begin 1 & i & 0\\ i & 1 & i\\ 0 & i & 1 \end, \]

а число замощений равно \(\sqrt<|\det^2|>=\det=3\).

Замощение доминошками областей на клетчатой бумаге можно интерпретировать как частный случай еще более общей задачи. Именно, рассмотрим произвольный граф H. Совершенным паросочетанием (или димерной упаковкой) графа H называется любой набор его ребер, в котором каждая вершина графа встречается ровно один раз. Ясно, что если вершины графа H суть центры клеток некоторой области Γ на клетчатой бумаге, а ребрами соединены те из них, для которых соответствующие клетки являются соседними, то вопрос о количестве совершенных паросочетаний графа H превращается в точности в вопрос о числе замощений области Γ фигурками домино. Например, на рис. 7 изображены граф, отвечающий области Γ с рис. 6, а также его совершенные паросочетания.

Совершенные паросочетания тесным образом связаны с остовными деревьями. Напомним, что деревом называется любой связный граф без циклов. Если же дан связный граф G, то его остовное дерево — это дерево, вершины которого совпадают с вершинами графа G, а каждое ребро является ребром графа G. Выясним, как каждому остовному дереву графа G сопоставить совершенное паросочетание некоторого графа H. Для этого сделаем дополнительное предположение, что граф G — плоский, то есть что его можно расположить на плоскости так, чтобы его ребра не пересекались нигде, кроме вершин. Тогда плоскость окажется разбита ребрами графа G на области, называемые гранями, среди которых будет неограниченная по размеру внешняя грань. Будем обозначать множества вершин, ребер и граней графа G буквами V, E и F соответственно.

Построим на основе графа G новый, расширенный граф H. Для этого отметим вершины, середины ребер и центры граней («центром» грани можно считать любую точку внутри этой грани) исходного графа — это будут вершины нового графа, а ребрами соединим такие пары вершин, для которых соответствующие объекты в исходном графе инцидентны (рис. 8)

Рис. 8. Соответствие между остовным деревом графа G и паросочетанием графа H. Вершины графа G отмечены черными точками, середины его ребер — белыми, а центры граней — серыми. Обратите внимание, что для удобства внешняя грань графа G отмечена не точкой, а внешним контуром

Заметим, что в графе H имеется только два типа ребер: \((\bar,\bar)\) и \((\bar,\bar)\), где \(v\in\), \(e\in\), \(f\in\), а черточкой мы обозначаем соответствующую вершину графа H. С одной стороны, отсюда следует, что совершенными паросочетаниями граф H не обладает, поскольку знаменитая формула Эйлера для плоских графов гласит, что \(|V|-|E|+|F|=2\). С другой стороны, мы видим, что это легко исправить: достаточно удалить из H две вершины вида \(\bar\) и \(\bar\) вместе с исходящими из них ребрами. Например, удалив вершину, соответствующую внешней грани, а также одну из вершин вида \(\bar\), мы получим граф H’, который уже обладает паросочетаниями. Теперь, чтобы на основе данного паросочетания графа H’ построить остовное дерево графа G, достаточно взять все входящие в паросочетание ребра вида \((\bar,\bar)\) и провести соответствующие им ребра e. Отметим, что указанное сопоставление всегда будет взаимно однозначным, если для получения графа H’ мы будем удалять из H вершины, прилегающие друг к другу с точки зрения графа G.

Как и для числа замощений доминошками, для числа остовных деревьев связного графа без петель существует формула, оперирующая определителем матрицы. Именно, пусть xuv обозначает количество ребер, соединяющих между собой вершины u и v графа G, а \(\deg\) — степень вершины v, то есть общее количество исходящих из нее ребер. Определим матрицу Δ следующим соотношением:

Очевидно, что сумма чисел в каждой строке матрицы Δ равна нулю, а значит, \(\det\Delta=0\). Однако оказывается, что для достижения цели достаточно вычеркнуть из матрицы строку и столбец, причем неважно, какие. Именно, если мы вычеркнем строку и столбец, соответствующие вершинам u и v соответственно, а получившуюся матрицу назовем \(\Delta^<(u,v)>\), то число остовных деревьев графа G равно \(|\det\Delta^<(u,v)>| \). (Более точно, количество остовных деревьев равно любому алгебраическому дополнению матрицы Δ). Например, если граф G состоит из пяти вершин, соединенных между собой ребрами так, как мы это видели на рис. 8, то ему соответствует матрица

и, согласно описанной выше формуле, число остовных деревьев равно, скажем, \(|\det\Delta^<(3,2)>|\):

В данном случае, число остовных деревьев графа G легко вычислить непосредственно. В самом деле, этот граф состоит из двух циклов длины три и четыре соответственно. Чтобы получить остовное дерево, необходимо удалить по одному ребру из каждого цикла, однако удаляемые ребра должны быть различными. Поэтому количество остовных деревьев есть 3·4 − 1 = 11.

Любопытно, что изначально этот результат, оперирующий математическими понятиями графов и остовных деревьев, был получен немецким физиком Густавом Кирхгофом для электрических цепей. И правда, электрическую цепь можно рассматривать как граф, вершинами которого будут узлы цепи, а ребрами — ее ветви. Теперь если ребру, соединяющему вершины u и v, приписать сопротивление соответствующей ветви Ruv и рассмотреть матрицу T = (Tuv), заданную соотношением

то из законов Кирхгофа можно вывести, что сопротивление между узлами k и l равно \(\dfrac<\det>><\det>>\), где T(k, l) — матрица, получающаяся вычеркиванием строк и столбцов, соответствующих узлам k и l, а T(l) — матрица, получающаяся из T вычеркиванием строки и столбца, соответствующих узлу l.

Напоследок отметим два классических результата, касающихся замощений доминошками различных областей. Во-первых, нужно сказать о непосредственно связанной с нашей задачей формуле, которая выражает количество способов замостить прямоугольник размера m×n:

Обратите внимание, что если оба числа m и n являются нечетными, получается корректный ответ — ноль. Наиболее типичное доказательство этой формулы базируется на упомянутой выше теореме Кастелейна, но, конечно, ею не ограничивается. А во-вторых, нельзя не отметить задачу об Ацтекском бриллианте. Ацтекским бриллиантом размера n называется фигура на плоскости, состоящая из клеток, центры которых удовлетворяют неравенству \(|x|+|y|\leqslant\) (так, на рис. 9 изображен Ацтекский бриллиант размера 4). Оказывается, общее количество замощений доминошками Ацтекского бриллианта размера n равно \(2^<1+2+\ldots+n>=2^\). Интересно поведение типичного замощения при больших n: теорема о полярном круге утверждает, что внутри вписанной в Ацтекский бриллиант окружности оно является хаотичным. А вот почти все доминошки, находящиеся вне этой окружности — в углах бриллианта, будут «заморожены»: в нижнем и верхнем углах они почти всегда будут горизонтальными, а в левом и правом — вертикальными.

Изуродованная шахматная доска

Из шахматной доски вырезали две угловые клетки, расположенные на концах «белой диагонали», так, как показано на рисунке:

Можно ли получившуюся «изуродованную» шахматную доску замостить 31 костью домино, каждая из которых накрывает ровно две клетки, таким образом, чтобы они полностью покрыли все 62 оставшиеся клетки доски? Если можно, то как?

Разместить 31 кость домино на доске, у которой вырезаны два угловых квадрата на противоположных концах диагонали, невозможно. Это следует из того, что каждая кость домино обязательно покрывает две клетки разного цвета, поскольку только такие клетки примыкают друг к другу. Поэтому после того, как 30 костей закроют 60 клеток доски, свободными останутся два квадрата одинакового цвета (в нашем случае — чёрного). Они не могут находиться рядом, и поэтому их нельзя прикрыть последней костью домино.

Материал для занятий кружка «Логическая математика» по теме «Пентамино»

Презентация к уроку

Внимание! Предварительный просмотр слайдов используется исключительно в ознакомительных целях и может не давать представления о всех возможностях презентации. Если вас заинтересовала данная работа, пожалуйста, загрузите полную версию.

Полимино

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

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

В последующих комбинаторных задачах предполагается, что полимино можно вращать (то есть поворачивать на 90, 180 или 270) и зеркально отражать (переворачивать), не меняя формы самих фигур.

Домино

Домино состоит из двух квадратов и может иметь лишь одну форму – форму прямоугольника размером 1×2 (см. рис. 1). Первая связанная с домино задача, вероятно, многим знакома: даны шахматная доска, из которой вырезана пара противоположных угловых клеток, и коробка домино, каждое из которых покрывает ровно две клетки шахматной доски (см. рис. 2). Возможно ли целиком покрыть доску с помощью 31 кости домино (без свободных клеток и наложений)? Ответ на этот вопрос гласит: «НЕТ» и имеет замечательное доказательство. Шахматная доска содержит 64 чередующиеся клетки белой и черной раскраски (имеется в виду обычная шахматная раскраска доски). Каждая положенная на такую доску и покрывающая две соседние клетки кость домино покроет одно белое и одно черное поле, а n костей домино – n белых и n черных полей, т.е. поровну и тех и других. Но изображенная на рисунке шахматная доска содержит больше черных клеток, чем белых, и потому ее нельзя покрыть костями домино. Этот результат есть типичная теорема комбинаторной геометрии.

Тримино

Тримино (или триомино) — полимино третьего порядка, то есть многоугольник, полученный путём объединения трёх равных квадратов, соединённых сторонами. Если повороты и зеркальные отражения не считать различными формами, то существует только две «свободных» формы тримино (см. рис.3): прямое (I-образное) и угловое (L-образное).

Тетрамино

С тетрамино связано множество задач на составление из них разных фигур. Доказано, что сложить какой-либо прямоугольник из полного набора тетрамино невозможно. Доказательство использует раскраску в шахматном порядке. Все тетрамино, кроме Т-образного, содержат 2 чёрные и 2 белые клетки, а Т-образное тетрамино — 3 клетки одного цвета и 1 клетку другого. Поэтому любая фигура из полного набора тетрамино (см. рис.4) будет содержать клеток одного цвета на две больше, чем другого. Но любой прямоугольник, с чётным количеством клеток, содержит равное число чёрных и белых клеток.

Пентамино

Полимино, покрывающее пять клеток шахматной доски, называются пентамино. Существует 12 видов пентамино, которые можно обозначить прописными латинскими буквами, как указано на рисунке (см. рис. 5). В качестве приема, позволяющего легко запомнить эти наименования, укажем, что соответствующие буквы составляют конец латинского алфавита (TUVWXYZ) и входят в имя FiLiPiNo. Поскольку всего имеется 12 разных пентамино и каждая из этих фигур покрывает пять клеток, то вместе они покрывают 60 клеток.

Самая распространённая задача о пентамино — сложить из всех фигурок, без перекрытий и зазоров, прямоугольник. Поскольку каждая из 12 фигур включает в себя 5 квадратов, то прямоугольник должен быть площадью 60 единичных квадратов. Возможны прямоугольники 6×10, 5×12, 4×15 и 3×20 (см. рис. 6).

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

Для прямоугольника 5×12 существует 1010 решений, 4×15 — 368 решений, 3×20 — всего 2 решения (отличающихся вышеописанным поворотом). В частности, существует 16 способов сложить два прямоугольника 5×6, из которых можно составить как прямоугольник 6×10, так и 5×12.

Еще одна интересная задача о пентамино — задача об утроении фигур пентамино (см. рис. 7). Эта задача была предложена профессором Калифорнийского университета Р.М.Робинсоном. Выбрав одну из 12 фигур пентамино, необходимо построить из каких-либо 9 из 11 оставшихся пентамино фигуру, подобную выбранной, но в 3 раза бо́льшей длины и ширины. Решение существует для любого из 12 пентамино, причём не единственное (от 15 решений для Х до 497 для Р). Существует вариант этой задачи, в котором для построения утроенной фигуры разрешается использовать также и саму исходную фигуру. В этом случае число решений от 20 для Х до 9144 для Р-пентамино.

Комментарии к презентации «Пентамино»

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

Для работы нам потребуется комплект, состоящий из двенадцати деталей пентамино. Его очень легко сделать самим на уроке или дома. На листе в клетку нужно нарисовать фигуры так, чтобы каждая состояла из пяти квадратов со стороной 1см. Затем следует приклеить лист в клетку на картон и вырезать по контуру получившиеся фигурки. При желании их можно раскрасить цветными карандашами или фломастерами. Пентамино готово.

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

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

Начиная с пятой задачи, учащиеся сами должны выбрать фигурки, которые будут использованы для данной картинки. В задаче №5 для «собачки» потребуются три фигурки пентамино.

В задаче №6 ребята должны не только собрать данные картинки, но и попытаться объяснить, почему может быть представлено только единственное решение этих задач.

В задачах №7 и №8 решений может быть несколько, и можно устроить соревнования «кто первый найдет все возможные решения этих задач».

Начиная с задачи №9, решений становится гораздо больше. Найти все решения на уроке не получится. Эти задачи можно предложить как вариант домашнего задания или предложить найти решения, разбив класс на группы.

В задачах №13 и №14 при решении используются все двенадцать фигур пентамино. Это уже достаточно сложные задания. С ними могут справиться не все учащиеся 5-6 классов. Поэтому те ребята, которые нашли решения этих задач, должны быть поощрены.

Очень интересный результат можно получить, предложив ребятам самим придумать различные картинки, составленные из фигур пентамино. Если это начальные классы, то нужно оговорить, что можно использовать не все фигуры сразу. В более старших классах учащиеся могут использовать весь комплект. Здесь следует напомнить, что каждая фигурка встречается ровно однажды и нельзя использовать какие-то детали более одного раза.

И вообще, очень трудно охватить такой огромный материал в одной презентации. Я предложила только малую толику того, что может быть придумано из пентамино. Творите, и результат превзойдет все ваши самые смелые ожидания. Ваши дети очень талантливы, и нужно только направить их мысль в нужную сторону. А там…

Мастер Йода рекомендует:  Лучший браузер 2020 года сравнение Chrome, Firefox, Opera, Internet Explorer и Edge
Добавить комментарий