Как избегать прямоугольников – 2
Крестики в сетке могут стать углами прямоугольников с горизонтальными и вертикальными сторонами. Крестики в первой сетке образуют два прямоугольника. Однако цель состоит в том, чтобы избежать образования прямоугольников. Крестики во второй сетке расположены таким образом, чтобы исключить образование каких-либо прямоугольников.
CHALLENGE
Разместите как можно больше крестиков в этой сетке 4 на 4, избегая создания прямоугольников.
РАЗВЕДКА
Каков максимальный размер ячеек сетки других размеров? Вы замечаете какие-либо закономерности в своих ответах?
Заметки
CHALLENGE
Решение этой задачи в целом — очень сложная, нерешенная проблема в математике. Однако это не должно мешать студенту экспериментировать с ней и попутно узнавать много интересного.
Предположим, что сетка имеет m строк и n столбцов. В задании «Избегая прямоугольников – 1» мы получили следующие результаты для наилучших ответов.
1 и 2 строки: У нас было m + n – 1 X.
3 строки: У нас было m + n крестиков, используя исходную схему сетки 3 на 3, которая выглядела следующим образом. Используя эту схему, если бы у нас было 3 строки с большим количеством столбцов, мы могли бы просто добавить один крестик в каждый новый столбец.
В случае с расположением столбцов 3х3 потребовался иной подход по сравнению со стратегией с 1 и 2 строками, и возникает соблазн предположить, что примеры с 4 и более строками также потребуют нового мышления. Очевидно, что мы хотим создать набор столбцов, которые никогда не будут иметь общих строк с отметками X.
Одна из стратегий заключается в том, чтобы заполнить все ячейки в крайнем левом столбце, кроме нижней, а затем в остальных столбцах разместить по одному крестику в нижней строке и по одному крестику в другой строке. Это всегда работает и дает (m – 1) + 2 x (m – 1) = 3 x (m – 1) крестиков для квадратной сетки размером m на m. Этот метод заполнения квадрата можно затем расширить (добавив по одному крестику в каждый новый столбец) на любую сетку с m строками, чтобы получить 3 x (m – 1) + (n – m) = n + 2m – 3 крестика, когда m < n. Эта формула работает для всех ответов для сетки любого размера (с более чем одной строкой) на данный момент.
РАЗВЕДКА
Поиск лучших ответов в интернете показывает, что для размера 5 на 5 можно сделать 12 крестиков (которые можно получить, используя схему), а для размера 6 на 6 — 16 крестиков (показано здесь).
После этого числа, начиная с 7 и далее по порядку, идут: 21, 24, 29, 34, 39, 45, 52, 56, 61, 67, 74, 81, 88, 96, 105, 108, 115 и 122. Математики провели множество интересных исследований того, как это работает, и ваши математики тоже могут получить от этого массу удовольствия!
