ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 88099
Тема:    [ Замощения костями домино и плитками ]
Сложность: 2
Классы: 5,6,7
В корзину
Прислать комментарий

Условие

Двадцать восемь косточек домино можно разными способами выложить в виде прямоугольника 8×7 клеток. На рис. 1-4 приведены четыре варианта расположения цифр в прямоугольниках. Можете ли вы расположить косточки в каждом из этих вариантов?


Подсказка

Вариант 1 (см. рис. .1 в задачах). Попробуйте определить, на каких местах расположены косточки дубли. Вариант 4 (см. рис. .4 в задачах). Где расположена косточка 4-2? Могут ли во второй строке находиться косточки 0-1 и 5-6? Могут ли в первой строке лежать косточки 1-2 и 4-5? Могут ли во второй строке лежать косточки 2-5 и 1-4? Может ли косточка 1-1 стоять во втором столбце? А может ли косточка 5-5 стоять в седьмом столбце? Где расположена косточка 0-6? Могут ли косточки 6-3 и 3-0 находиться в третьей или четвёртой строках?

Решение

Все подобные задачи решаются одинаково. Используются обычные свойства косточек домино. Например, в наборе домино обязательно встречается косточка с парой любых чисел от 0 до 6, причём ни одна такая пара не повторяется дважды. Косточки домино не могут расположиться на нечётном числе клеток и т.д. Поскольку варианты предложены в порядке возрастания трудности, рассмотрим подробные решения только для первого  — в силу его наглядности и для последнего  — в силу его сложности. Вариант 1 (рис. 1):

  1. Места всех дублей в этой раскладке определяются однозначно. Отметим их Отсюда однозначно определяется местоположение косточек 5-0, 5-3, 0-2, 3-4, 0-6, 2-5. Отметим теперь, что если гденибудь перечисленные пары цифр и стоят рядом, то они не могут образовывать косточки. Полученная позиция изображена на рис. 2.
  2. Отсюда однозначно определяется местоположение косточек 2-4 и 0-3. Отметив, что эти косточки не могут находиться на других местах, получим расположение косточек (позиция на рис. 3).
  3. И снова обратим внимание на то, что, если гденибудь перечисленные пары цифр и стоят рядом, они не могут образовывать косточки. Отсюда уже можно однозначно восстановить всю раскладку (рис. 4).
Вариант 4 (рис. 5):
  1. Единственная косточка, расположение которой можно определить однозначно, это 4-2 (нигде больше 4 и 2 не стоят рядом).
  2. Во второй строке не может находиться косточка 0-1 (иначе получим две одинаковые косточки 0-1 в первой и второй строках). По тем же соображениям во второй строке не может находиться косточка 5-6, а в шестой  — косточки 4-6 и 0-2. Отметим это (рис. 6).
  3. В первой строке не может лежать косточка 1-2 (иначе цифра 1, стоящая на пересечении второй строки и второго столбца, будет образовывать ещё одну косточку 1-2). По аналогии, в первой строке не может лежать косточка 4-5.

  4. Аналогично тому, как это уже делалось в пункте 2, определим, что косточки 2-5 и 1-4 не могут лежать во второй строке. Отметим это (рис. 7).
  5. Теперь очевидно, что косточка 1-1 не может стоять во втором столбце (иначе негде расположить косточку 1-2). По аналогии, 5-5 не может находиться в седьмом столбце (иначе нет места для косточки 4-5). Отсюда можно однозначно восстановить расположение косточек 0-1, 0-5, 5-6 и 6-1. Отметив, что в других местах эти косточки располагаться не могут, получим однозначную возможность расположить косточки 1-1 и 5-5. Отметим, что иное их расположение невозможно. Таким образом получаем расположение косточек, изображённое на рис. 8.
  6. 0 и 6 трижды встречаются рядом, и все три раза  — в шестом строке. Однако только та пара, которая лежит точно под косточкой 4-2, может образовывать косточку 0-6 (в противном случае получим две косточки 0-6). Отсюда однозначно определяется положение косточек 4-0 и 2-6. Отметим невозможность расположения этих косточек в других местах (рис. 9).
  7. Обратим внимание на то, что ни в третьей, ни в четвёртой строках не могут находиться косточки 6-3 и 3-0; отсюда определяем расположение косточек 6-6 и 0-0. Далее, косточка 3-3 не может находиться ни в третьей строке, ни в четвёртом или пятом столбцах. Отсюда определяем расположение косточек 3-3, 5-3 и 1-3. Отметив, что эти косточки нигде в других местах располагаться не могут, получим однозначное расположение всех косточек домино (рис. 10).

Ответ

 См. рисунок.

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

книга
Автор Козлова Е.Г.
Название Сказки и подсказки
задача
Номер 167

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .