Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Покрытие «изуродованных» шахматных досок с помощью L-тримино

Читайте также:
  1. Ferrite calibration калибровка катушки с помощью феррита.
  2. V1: Управление запасами и складскими процессами с помощью логистики
  3. XVII. Укажите номера предложений в которых –ing-форма переводится на русский язык с помощью слова «будучи» и страдательного причастия.
  4. А. Включение и отключение блока управления с помощью переключателя
  5. Анализ устойчивости с помощью логарифмических амплитудно-частотных характеристик
  6. Воспроизведение направляющей функции при рабочем и латерально-выдвигающем движениях нижней челюсти с помощью резцовой направляющей подставки
  7. Восстановление нескольких задних зубов с помощью амальгамы

 

Среди современных математиков приобрела большую популярность так называемая теория покрытий. Нижеследующий текст первоначально был опубликован в «College Mathematical Journal» (май 2009).

 

Введение

Пусть стандартную шахматную доску «изуродовали», удалив два крайних угловых поля, расположенных по диагонали друг напротив друга. Можно ли оставшиеся 62 квадрата покрыть с помощью 31 прямоугольной костяшки домино? Ответ — нет, потому что убранные квадраты — одного цвета. Допустим, их цвет — белый. Тогда среди оставшихся 62 полей окажутся два «лишних» черных квадрата. Между тем каждая костяшка домино покрывает одну черную и одну белую клетку. После того как мы поместим на доску 30 костяшек, две черные клетки останутся свободными. Они не могут примыкать друг к другу (иметь общую сторону), а следовательно, их невозможно покрыть при помощи костяшек домино. Эта широко известная задача, которая решается элементарной проверкой равенства, являет собой простой пример задачи покрытия изуродованной шахматной доски.

Менее известна связанная с ней другая задача. Предположим, доску изуродовали, удалив две клетки разного цвета из любых мест доски. Всегда ли можно будет покрыть при помощи костяшек домино оставшиеся 62 клетки? Ответ — да, и существует прелестное доказательство, полученное Ральфом Гомори[72].

 

 

 

 

Рис. 1. Доказательство Гомори

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

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

Если вместо пластинок домино покрывать доску с помощью L-тримино (называемых также косыми, или V-тримино, или угловыми тримино), тогда все квадратные доски, у которых число клеток без остатка делится на 3, можно будет покрыть такими фигурами (кроме доски 3×3). Среди них мы не будем рассматривать «неповрежденные», а возьмем лишь такие изуродованные доски, где число клеток кратно 3 после того, как из произвольного места доски удалили одну клетку. Будем называть такие доски дефицитными. Иными словами, доска со стороной n является дефицитной, если n2–1 кратно 3; т. е. само n не кратно 3. Длины сторон таких досок образуют ряд (1):

 

2, 4, 5, 7, 8, 10, 11, 13, 14… (1)

 

Каждое из этих чисел будем называть порядком доски. И еще: здесь и далее слово «тримино» будет означать исключительно L-тримино.

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

 


Дата добавления: 2015-10-30; просмотров: 174 | Нарушение авторских прав


Читайте в этой же книге: И другие размышления о всякой всячине | Энн Коултер бросает вызов Дарвину | Исаак Ньютон и его безбрежный океан истины | Выстрелы в яблочко и знаменитые промахи | Почему я не сторонник паранормального | Новое мышление», «Единство» и Элла Уилер-Уилкокс | Была ли предсказана гибель «Титаника»? | Дракула готовит мартини | Выше 7-го порядка | ПОЛНЫЙ И УНИВЕРСАЛЬНЫЙ РЕЗУЛЬТАТ |
<== предыдущая страница | следующая страница ==>
Ряд Фибоначчи| Порядки 5 и 7

mybiblioteka.su - 2015-2024 год. (0.005 сек.)