"Информатика (в 3 частях)", Семёнов А.Л., Рудченко Т.А.
Цвет в задаче — не просто украшение, а признак, который присваивают объектам по определённому правилу. Раскрашивание помогает увидеть свойство, незаметное при обычном подсчёте: например, разделить клетки на два класса или проверить, что делает каждый ход. Главное — задать правило однозначно и подобрать его под условие. Тогда по цветам можно сравнивать объекты, находить сохранение свойства и доказывать невозможность действия.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Цвет — признак, который присваивают объекту по выбранному правилу. Например, клетку можно назвать белой или чёрной не из-за её внешнего вида, а по номеру или координатам. Такое обозначение нужно, чтобы сравнивать объекты и замечать различия между ними.
Раскрашивание — распределение цветов между объектами задачи. Мы мысленно или на рисунке относим каждый объект к определённой группе. Это помогает выделить важное свойство и не запутаться в большом количестве одинаковых объектов.
Правило раскрашивания — способ определить цвет объекта по его номеру, координатам или положению. Одному и тому же объекту при одинаковых условиях правило должно назначать один цвет. Благодаря этому раскраска становится проверяемой, а не случайной пометкой.
Двухцветная раскраска — раскрашивание двумя цветами, при котором соседние или связанные объекты получают разные цвета. На шахматной доске это белый и чёрный цвета. Такая раскраска нужна, чтобы сравнивать две группы и исследовать, как они меняются при действиях.
Раскрашивание выделяет свойство объектов, которое трудно увидеть при обычном счёте. Например, на большой доске можно сразу сравнить число чёрных и белых клеток, хотя перечислять все клетки неудобно. Если каждая разрешённая фигура имеет определённый состав цветов, раскраска превращается в короткий способ проверки.
Правило должно быть однозначным, потому что иначе один и тот же объект можно будет отнести к разным группам. При одинаковом номере, положении или координатах результат обязан совпадать. Только тогда вывод, сделанный по цветам, относится ко всей задаче, а не к случайному выбору.
На полоске из клеток цвета удобно чередовать по номерам: нечётные клетки получают один цвет, чётные — другой. На клетчатом поле цвет можно определять по чётности суммы координат: если сумма чётная, выбирают один цвет, если нечётная — второй. При переходе в соседнюю клетку одна координата меняется на 1, поэтому чётность суммы меняется и цвета чередуются.
При перемещении или объединении объектов иногда сохраняется их цветовой состав. Например, домино на шахматной доске закрывает одну клетку каждого цвета, поэтому после любого числа таких ходов число закрытых белых и чёрных клеток одинаково. Если в исходной фигуре цветов было поровну, а после удаления или изменения стало не поровну, требуемое действие невозможно.
Раскраску выбирают под условие, а не по привычке. Нужно проверить, какие объекты считаются соседними, каковы размеры фигур, какие ходы разрешены и сколько объектов каждого цвета должно участвовать в одном действии. Хорошее правило превращает эти ограничения в простой подсчёт или проверку сохранения свойства.
В таблице сначала найдите объект и правило, по которому ему назначают цвет. Затем посмотрите, какое свойство получается и как его применяют в задаче. Последний столбец подсказывает, какой вывод можно делать по раскраске.
| Объект | Правило раскрашивания | Что получается | Для чего используется |
|---|---|---|---|
| Клетки полоски | Цвета чередуются по номерам клеток | Клетки с нечётными и чётными номерами имеют разные цвета | Определение цвета клетки по её номеру |
| Клетки шахматной доски | Цвет зависит от чётности суммы координат | У каждой клетки есть один из двух цветов, соседние клетки разноцветны | Сравнение количества клеток разных цветов |
| Клетки, покрываемые домино | Каждое домино закрывает одну клетку каждого цвета | При покрытии сохраняется равенство числа чёрных и белых клеток | Доказательство невозможности покрытия |
| Вершины или позиции в задаче | Цвет зависит от положения или остатка при делении номера | Объекты разбиваются на несколько классов | Проверка сохранения свойства при ходах |
Обычно сначала раскрашивают все объекты, а затем изучают одну фигуру или один разрешённый ход. Если его цветовой состав не меняется в нужном смысле, можно сравнить начальное и конечное состояния. Несовпадение показывает невозможность, но совпадение ещё требует дополнительной проверки.
На полоске из 20 клеток цвета чередуются, первая клетка белая. Требуется узнать цвет 17-й клетки, не перебирая все клетки по очереди. Здесь подходит правило по чётности номера.
Ответ: 17-я клетка белая.
Из шахматной доски 8×8 убрали два противоположных угла. Нужно выяснить, можно ли покрыть остальные клетки домино 1×2. Противоположные углы шахматной доски имеют один цвет, поэтому решающим будет не общее число клеток, а соотношение цветов.
Ответ: покрыть оставшиеся клетки домино нельзя.
Проверим, можно ли полностью покрыть доску 5×5 домино. Используем ту же двухцветную раскраску, потому что домино занимает две соседние клетки. Размер доски даёт нечётное число клеток, поэтому цветов будет поровну быть не может.
Ответ: полностью покрыть доску 5×5 домино нельзя.
Ошибка — считать цвет случайной пометкой, не связывая его с правилом. Так допускают несогласованную раскраску и получают вывод, который нельзя проверить. Проверьте себя: сформулируйте правило словами и примените его к нескольким объектам.
Ошибка — определять цвет клетки только по одной координате, когда правило зависит от их суммы. Это нарушает чередование в некоторых направлениях. Сложите координаты выбранной клетки и сравните чётность именно этой суммы.
Ошибка — проверять только общее число клеток, не сравнивая количество клеток каждого цвета. Общее число может подходить, хотя цветовой баланс делает покрытие невозможным. Перед выводом отдельно посчитайте объекты каждой группы.
Ошибка — считать совпадение количества цветов доказательством возможности покрытия. Равенство является лишь необходимым условием: могут помешать форма, границы или расположение клеток. После проверки цветов исследуйте, можно ли действительно расставить фигуры без пропусков и пересечений.
До этой темы нужны нумерация объектов, координаты клеток и понимание чётности чисел. Эти знания позволяют быстро определить цвет по номеру или сумме координат.
Раскрашивание пригодится в задачах о шахматных досках, покрытиях и допустимых ходах. Оно связывает геометрическое расположение объектов с точным подсчётом.
Дальше та же идея встречается в инвариантах, алгоритмах и комбинаторных задачах. Цвет становится способом описать свойство, которое не меняется при разрешённых действиях.
Зачем раскрашивать клетки, если цвета не указаны в условии?
Цвета вводят самостоятельно как удобные метки. Они помогают разделить объекты на группы и заметить свойство, которое сохраняется при каждом разрешённом действии.
Как понять, какое правило раскрашивания выбрать?
Нужно посмотреть, что связано с условием: соседство, координаты, размеры фигур, ходы или количество объектов. Выбирайте такое правило, при котором один ход или одна фигура имеют простой и заметный состав цветов.
Почему у соседних клеток шахматной доски разные цвета?
Цвет клетки задают по чётности суммы её координат. При переходе на соседнюю клетку одна координата изменяется на 1, поэтому чётность суммы меняется.
Всегда ли равное количество клеток двух цветов означает, что покрытие возможно?
Нет. Равенство цветов — только необходимое условие для некоторых покрытий, но не доказательство возможности. Фигуры могут не помещаться из-за формы, границ или расположения оставшихся клеток.
Можно ли использовать не два, а больше цветов?
Да, если это помогает увидеть ограничение задачи. Например, цвет можно задавать остатком номера при делении, разделяя объекты на три или больше классов.
Правило раскрашивания. Цвет
