Плитка треугольной сетки

Question

Дизайн и объяснение алгоритма рекурсивного разделения и покоя. У кого-нибудь есть идеи?

Для равнобедренной правой треугольной сетки для некоторого k ≥ 2, как показано на рисунке 1 (b), эта проблема просит вас полностью покрыть ее, используя плитки, представленные на рисунке 1 (a). Нижний левый угол сетки не должен быть закрыт. Никакие две плитки не могут перекрываться, и все плитки должны оставаться полностью внутри данной треугольной сетки. Вы должны использовать все четыре типа плиток, показанных на рисунке 1 (a), и не использовать тип плитки для покрытия более 40% общей площади сетки. Вы можете повернуть плитки, если необходимо, перед тем, как поместить их в сетку.

Answer 1

Это идея индукции в самом деле, и это похоже на известный пример "L-Tile" covering

Как вы сказали, вы решили задачу к = 2, это хорошо и правильно отправной точкой для решения небольшой во-первых, но я думаю, что эта проблема немного сложна для случая k = 2, в основном из-за каждый тип не может превышать 40% constrain.

Тогда при к> 2, скажем, к = 3 в вашем примере, мы стараемся использовать то, что вы решили, то есть при к = 2

С очень простым наблюдением, то можно заметить, что при к = п, это может фактически быть составлен из 4 K = N-1 случаев (см рисунок ниже)

Теперь заштрихованная часть в средней форме отверстие, которое может заполненную 1 типа в, так что мы можем сначала заполнил 4 маленьких корпуса n-1 и заполнил отверстие с помощью типа B ...

Но тогда эта конструкция сталкивается с проблемой: типа B будет превышать 40% площади!

Рассмотрите k = 2, независимо от того, как вы заполняете область, 2 типа B необходимо использовать, у меня нет сильного доказательства, но какой-либо грубой силой след & ошибки вы должны быть уверены. Тогда для k = 3 мы имеем 4 маленьких треугольника, то есть имеем 2 * 4 = 8 Тип B, плюс еще 1, чтобы заполнить отверстие, даст нам 9 типа B, каждый из которых использует 1,5 кв. Единиц, общая сумма которых составляет 13,5 кв.

При k = 3 общая площадь составляет (2^3)^2/2 = 32 кв. Единиц 13,5/32 = 0,42 .... которые нарушают ограничение!

А что делать? Вот почему мы должны использовать трюк для обработки случая k = 2 (я предполагаю, что вы прошли эту часть, как вы сказали, что знаете, как делать k = 2)

Во-первых, мы знаем, что использование наш конструктивный метод построения большого треугольника из 4 меньших треугольников, только Тип B будет нарушать это ограничение (то есть область 40%), вы можете убедиться сами. Поэтому мы хотим уменьшить общее количество используемого типа B, но каждый меньший треугольник должен использовать как минимум 2 типа B, поэтому единственное место, которое мы можем уменьшить, это пустое отверстие в середине большого треугольника, можем ли мы использовать другой тип вместо типа B? В то же время мы хотим, чтобы остальные части малого треугольника оставались неизменными, поэтому мы можем использовать один и тот же аргумент для индукции (т.вообще говоря, форма 2^п треугольник из 4 2^(п-1) треугольников, используя тот же метод строительства)

ответ ДА, если специальная конструкция к = 2 случая Смотрите мою конструкцию ниже: (Там может быть, другие строительные работы тоже, но мне нужно знать только один)

хитрость заключается в том я намеренно переместить 1 Type B рядом с пустым (серый) треугольник Давайте остановимся здесь для бит и выполните некоторую проверку:

Для построения Ak = 2 случая, мы используем

• 2 типа А = 2 sq.units < 40%
• 2 Тип B = 3 sq.units < 40%
• 1 Тип C = 1.5 sq.units < 40%
• 1 Тип D = 1 sq.unit < 40%

Всего использование 7,5 sq.units, хорошие

Теперь представьте, что мы используем точно такой же метод, чтобы построить эти четыре треугольника, чтобы сделать большой, средний по-прежнему будет пустым отверстием с формой типа B, но вместо того, чтобы заполнить его 1 типом B, мы заполняем отверстие ВМЕСТЕ С 3-мя типами B рядом с ними (посмотрите назад случай k = 2), используя тип A & D (я использую ту же цветовую схему, что и выше для удобства понимания), мы делаем это для всех 3 маленьких треугольники, которые составляли отверстие посередине.

Вот последняя часть (я знаю, что это долго ...) Мы уменьшить число типа B использовали при построении большого треугольника из мелких, но в то же время мы увеличиваем номер типа A & D б/у! Так ли этот новый метод строительства действителен?

Прежде всего обратите внимание на то, что он не меняет никаких частей небольших треугольников, кроме типа B, рядом с серым треугольником, то есть если 40% -ное ограничение выполняется, этот метод является индуктивным и рекурсивным, чтобы заполнить 2^n боковой треугольник

Затем давайте посчитаем число каждого используемого типа.

к = 3, общего количества единиц составляет 32, мы использует:

• 2 * 4 + 3 = 11 Тип A = 11 sq.units < 40%
• 2 * 4-3 = 5 Тип B = 7,5 sq.units < 40%
• 1 * 4 = 4 типа C = 6 sq.units < 40%
• 1 * 4 + 3 = 7 Тип D = 7 sq.unit < 40%

Всего мы охватываем 31.5 единиц, хорошо, теперь давайте докажем, что ограничение на 40% выполняется для k = n> 3

Позвольте FA (n-1) быть общей площадью типа A, используемой для заполнения 2^n-1 треугольников, используя нашу новую Аналогично, FB (n-1), FC (n-1), FD (n-1) с аналогичными определениями

Предположим, что F * (n-1) истинно, т.е. не превышает 40% от общей площади , докажем, что F * (n) истинно.

Мы получили

FA(n) = FA(n-1)*4 + 3*1

FB(n) = FB(n-1)*4 - 3*1.5

FC(n) = FC(n-1)*4

FD(n) = FD(n-1)*4 + 3*1

Мы показываем только доказательство для FD (п), другие три должны быть оборудована устройством с аналогичным методом (MI)

Используя метод замещения, FD(n) = 2*(4^(n-2)) - 1 for n>=3 (Вы должны, по крайней мере, попытаться придумать с этим уравнением самостоятельно)

Мы хотим показать FD(n)/(2^2(n)/2) < 0.4

т.е. 2FD(n)/4^n < 0.4

Рассмотрим LHS,

LHS = (4 * (4^(n-2)) - 1)/4^n

< 4^(n-1)/4^n = 1/4 < 0,4 QED

Это означает, что при использовании этого метода весь тип AD не будет превышать 40% от общей площади для любого 2^k-стороннего треугольника, при k> = 3, наконец, мы покажем, что индуктивно, существует метод, удовлетворяющий всем ограничениям для построения такой треугольник.

TL; DR

1. Твердая часть должна удовлетворять область 40% ограничивают
2. Используйте специальную конструкцию, на к = 2 при первом, попробуйте использовать его, чтобы построить к = 3 случая (тогда k = 4, k = 5 ... идея индукции!)
3. При использовании случая k = n-1 для построения k = n случая запишите формулу общей площади, потребляемой каждым типом, и покажите, что они не превысят 40% от общей площади
4. Комбинированная точка 2 & 3, это индукционный метод, показывающий, что для любого k> = 2 существует способ (который мы описали) заполнить 2^k-сторонний треугольник без нарушения каких-либо ограничений