Unikalne nachylenie kwadratów

Chcemy kafelki $m\times m$-kwadrat przy użyciu dwóch rodzajów kafelków: $1 \times 1$- kwadratowa płytka i $2 \times 2$- kwadratowy kafelek, tak aby każdy leżący pod nim kwadrat był przykryty bez nakładania się. Zdefiniujmy funkcję$f(n)$ co daje rozmiar największego, unikalnego, możliwego do uprawy kwadratu $n$ $1\times 1$- kwadraty i dowolna liczba $2 \times 2$-squares.

Czy ta funkcja jest obliczalna? Co to jest algorytm?

EDYCJA 1: Na podstawie odpowiedzi Stevena unikalne kafelkowanie oznacza, że ​​istnieje jeden sposób na umieszczenie $2 \times 2$-kwadratowe wewnątrz $m \times m$-square z unikalną konfiguracją dla pozycji $n$ $1 \times 1$-kwadratowe wewnątrz $m \times m$-plac.

Oto argument, który ma udowodnić moje spekulacje w komentarzach, że nie istnieją takie unikalne tafle dla żadnego kwadratu $n\gt 5$. Po pierwsze, jak zauważył Sasho w komentarzach,$n$ należy ograniczyć, ponieważ nie ma takich przechyleń, jeśli $n\equiv2$lub . Jeśli jest kwadratem idealnym to oczywiście kwadrat jest jednoznacznie kafelkowy, więc jest wyraźnie zdefiniowane i niezerowe w tych przypadkach. Aby zakończyć argument, wystarczy pokazać, że żadne kafelkowanie obejmujące lub więcej kafelków może być unikalne.$3\pmod 4$$n$$n=k^2$$k\times k$$f(n)$$1$$2\times 2$

Najpierw rozważmy przypadek , powiedzmy . Jeśli mamy kafelki kwadratu przy użyciu kafelków, oczywiście musi być parzyste, powiedzmy ; następnie możemy konstruować tilings, budując kafelki z kafelków, a następnie zastępując z nich „blokami” czterech kafelków . Oczywiste jest, że różne zamienniki zawsze mogą prowadzić do wyraźnych przechyleń, z wyjątkiem przypadków lub gdzie występuje albo jeden$n\equiv 0\pmod 4$$n=4k$$m\times m$$n\ 1\times 1$$m$$m=2j$$j\times j$$2\times2$$k$$1\times 1$$m=4, n=12$$m=4, n=4$$2\times 2$kafelek lub pojedynczy „blok czterech” pozostałych; w takich przypadkach występuje inny nierówny kafelek , który umieszcza płytkę na środku krawędzi, a nie w rogu.$2\times 2$

Na koniec załóżmy, że , w szczególności załóżmy, że (i za pomocą aby zapobiec nieco trywialnemu przypadkowi, w którym po prostu „za mało miejsca” w kwadracie, aby przejść przez następujący argument ). Wówczas żaden kwadrat wielkości lub mniejszy nie może być jednoznacznie pokryty kafelkami: rozważ kafelki z kafelkami na górze kwadratu i w dół po prawej stronie kwadratu (z dodatkowymi kafelkami po prostu schowany po prawej stronie - nie mogą wpłynąć na argument). Teraz „blok” w lewym górnym rogu kwadratu (składający się z dwóch płytek na górze i$n\equiv 1\pmod 4$$n=4t+1$$t\gt 1$$(2t+1)^2$$1\times 1$$1\times 1$$2\times 3$$1\times 1$$2\times 2$kafelek pod nimi) można „odwrócić”, aby uzyskać kafelki, które koniecznie będą różnić się od kafelków, które zbudowaliśmy. Wreszcie żaden kwadrat o rozmiarze większym niż może być w ogóle sąsiadujący: załóżmy, że próbujemy ułożyć kwadrat o rozmiarze dla ; zgodnie z zasadą szufladki nie możemy zmieścić na kwadracie więcej niż płytki, co oznacza, że ​​są pozostały kwadraty - ale ponieważ , , liczba dostępnych płytek.$(2t+1)^2$$(2s+1)^2$$s\gt t$$s^2\ 2\times 2$$(2s+1)^2-4s^2 = 4s^2+4s+1-4s^2=4s+1$$s\gt t$$4s+1\gt 4t+1=n$$1\times 1$

Tak więc jedynymi unikalnymi tilingsami, które istnieją dla są te, które w ogóle nie używają kafelków , a jest niezerowe, gdy jest kwadratem (w którym to przypadku jest równe ).$n\gt 5$$2\times 2$$f(n)$$n$$\sqrt{n}$