Игры, где побеждает объяснениеЛогика / Выбирать сохраняющуюся величину Пробное занятие
Логика · шаг 42 из 64

Почему доску нельзя замостить

Выбирать сохраняющуюся величину · Доказывать невозможность покрытий

Около 20 минут 5 задач Подсказки рядом

В этом занятии

  • Выбирать сохраняющуюся величину
  • Доказывать невозможность покрытий
  • Различать необходимое условие и достаточное

Пригодится: Рекомендуем сначала пройти «Оставь сопернику неудобное число».

Ваш путь начинается с личного кабинета

Взрослый создаёт аккаунт для себя и отдельные кабинеты для школьников. У каждого — свой прогресс. Общие 48 часов знакомства начинаются с регистрации взрослого; школьники получают оставшееся время.

Войти или начать бесплатно
Учебное время начнёт считаться после нажатия
Понять — интереснее, чем запомнить.
Разберёмся перед практикой+

Почему доску нельзя замостить

Инвариант — свойство, которое сохраняет каждый разрешённый шаг. Для покрытия клетчатой доски домино полезно шахматное раскрашивание: соседние по стороне клетки имеют разные цвета. Каждая плитка 1 × 2 закрывает ровно одну тёмную и одну светлую клетку.

Если вся оставшаяся доска покрыта без наложений, числа клеток двух цветов должны совпадать. Удалим два противоположных угла доски 4 × 4: оба угла одного цвета. Было по восемь клеток каждого цвета, осталось шесть одного и восемь другого; домино не могут исправить этот дисбаланс.

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

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

НА ПРИМЕРЕ

На шахматно окрашенной доске 4 × 4 удалены верхний левый и нижний правый углы. Можно ли покрыть остаток домино 1 × 2?

  1. Углы имеют одинаковый цвет, поскольку суммы их координат одинаковой чётности.
  2. После удаления соотношение цветов 6 к 8.
  3. Любые семь домино закрыли бы 7 клеток каждого цвета; такое покрытие невозможно.

Попробуйте самостоятельно

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

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

Читайте и разбирайте пример в своём темпе. К практике можно перейти, когда будете готовы.