Игра в конфигурации: чем сложнее, тем интереснее!
Обсудить 0
- Если вы еще не прочли наш лонгрид об игре в конфигурации — скорее переходите по ссылке, а затем возвращайтесь и изучайте более сложные варианты игры.
Теперь вместо крестиков будем использовать цветные квадратики — составленные из них конфигурации воспринимаются легче. Кроме того, их можно быстро и легко рисовать в Word«е, используя цветовую заливку табличных ячеек.
Игра «Не больше трех»
Единственное правило выставления квадратиков здесь следующее: по вертикали, горизонтали и диагоналям не должно стоять более трех соседних (соприкасающихся) квадратиков. Соответственно, допустимы изолированные и объединенные лишь в пары квадратики. В качестве затравки используется пустое поле.
Самая интересная задача состоит в нахождении минимальных и максимальных полных конфигураций для заданных конечных полей, представляющих собой различные геометрические фигуры.
Даже в простейших случаях мы сталкиваемся с нетривиальными задачами комбинаторной геометрии. Рассмотрим, для начала, квадратное поле 4×4, представленное на рисунке 1. Далее листайте галерею право.
Рассмотрим теперь квадратное поле 5×5 (рис. 5). Далее листайте галерею право.
Перейдем к полям иных форм. Интереснейший случай — крестообразное поле, изображенное на рис. 10.
Рисунок 10
Найдите для него минимальную полную конфигурацию.
Решив подобную задачу для квадратных полей небольших размеров, можно было бы предположить, что и в данном случае элементами минимальной полной конфигурации будут квадраты, составленные из 3×3=9 квадратиков, или близкие к ним фигуры.
На рис. 11 и 12 представлены соответствующие гипотетические решения.
Но, оказывается, это не минимальные полные конфигурации, а… наоборот, максимальные. Число квадратиков в них равно 33.
Минимальные же полные конфигурации совершенно иные. Они представлены на рис. 13 и 14. Число квадратиков в них равно 24. Парадоксальным образом, в них встречаются элементы, входящие в максимальные полные конфигурации для квадратных полей.
Найдите минимальные и максимальные полные конфигурации для ступенчатых диагональных квадратов разных размеров (квадрат 4×4 такого рода представлен на рис. 15).
Рисунок 15
В игре «Не больше трех» интересны и полные конфигурации на бесконечном поле. Поскольку число квадратиков в них бесконечно, в качестве количественной меры следует использовать плотность, равную пределу (если он существует) отношения n/Sk при k→∞, где Sk = k х k — площадь квадрата со стороной k, а n — число заключенных в нем квадратиков. Плотность не должна зависеть от выбора последовательности увеличивающихся квадратов.
Плотность полной конфигурации, изображенной на рис. 16, очевидно, равна 9/16= 0,5625. Исходя из минимальных полных конфигураций для конечных квадратных полей, можно предположить, что данная полная конфигурация тоже минимальна.
Максимальная полная конфигурация на бесконечном поле и ее плотность автору пока не известны. Быть может, на этот вопрос сможет ответить наш читатель?
