Неразрешимость задачи о замощении плоскости набором плиток Вана

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

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

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Определения

Определение: Плитки Вана (англ. Wang tiles) — конечный набор квадратных плиток одинакового размера, таких, что каждой стороне сопоставлено определенное значение(цвет).

Определение:

Замощение плоскости (англ. tiling) — представление плоскости в виде множества непересекающихся плиток Вана.

Замощение плоскости

Задача:

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