Einzigartige Quadrate

Wir wollen Quadrat mit zwei Arten von Kacheln kacheln: Quadrat-Kachel und Quadrat-Kachel, so dass jedes darunter liegende Quadrat ohne Überlappung bedeckt wird. Definieren wir eine Funktion , die die Größe des größten eindeutig bearbeitbaren Quadrats unter Verwendung von Quadraten und einer beliebigen Anzahl von Quadraten angibt.1 × 1 2 × 2 f ( n ) n 1 × 1 2 × $m\times m$$1 \times 1$$2 \times 2$$f(n)$$n$ $1\times 1$$2 \times 2$

Ist diese Funktion berechenbar? Was ist der Algorithmus?

EDIT1: Basierend auf Stevens Antwort bedeutet eine eindeutige Kachelung, dass es eine Möglichkeit gibt, die Quadrate innerhalb des Quadrats mit einer eindeutigen Konfiguration für die Positionen der Quadrate innerhalb der zu platzieren Quadrat.m × m n 1 × 1 m × $2 \times 2$$m \times m$$n$ $1 \times 1$$m \times m$

Hier ist ein Argument, um meine Spekulation in Kommentaren zu beweisen, dass es für nicht quadratische keine solchen eindeutigen Kacheln gibt . Erstens muss, wie von Sasho in den Kommentaren erwähnt, n eingeschränkt werden, da solche Kacheln nicht existieren, wenn n ≡ 2 oder . Wenn ein perfektes Quadrat dann ist das Quadrat offensichtlich eindeutig kachelbar, so dass in diesen Fällen klar definiert und ungleich Null ist. Um das Argument zu vervollständigen, muss nur noch gezeigt werden, dass keine Kacheln mit oder mehr Kacheln eindeutig sein können.$n\gt 5$$n$$n\equiv2$$3\pmod 4$$n$$n=k^2$$k\times k$$f(n)$$1$$2\times 2$

Betrachten Sie zunächst den Fall , sagen wir . Wenn wir eine Kachelung eines Quadrats mit Kacheln haben, muss offensichtlich gerade sein, sagen wir ; dann können wir Kacheln konstruieren, indem wir eine Kachelung von Kacheln und dann davon durch 'Blöcke' von vier Kacheln ersetzen . Es ist klar, dass unterschiedliche Ersetzungen immer zu unterschiedlichen Kacheln führen können, außer in den Fällen oder denen entweder eine einzelne$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$Kachel oder ein einzelner 'Viererblock' übrig; In diesen Fällen gibt es jedoch eine andere inäquivalente Kachelung, bei der eine Kachel in die Mitte einer Kante und nicht in eine Ecke gelegt wird.$2\times 2$

Nehmen wir schließlich an, dass , insbesondere (und mit , um einen leicht trivialen Fall zu verhindern, in dem auf dem Quadrat einfach nicht genügend Platz für das folgende Argument vorhanden ist ). Dann kann kein Quadrat mit einer Größe oder kleiner eindeutig gekachelt werden: Betrachten Sie eine Kachelung mit Kacheln über der Oberseite des Quadrats und rechts unten auf dem Quadrat (mit zusätzlichen Kacheln) nur auf der rechten Seite versteckt - sie können das Argument nicht beeinflussen). Jetzt der 'Block' oben links auf dem Quadrat (bestehend aus den beiden 1 × 1- Kacheln oben und der 2$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$ Kacheln darunter) können umgedreht werden, um eine Kachel zu erzeugen, die sich notwendigerweise von der von uns erstellten Kachel unterscheidet. Schließlich kann kein Quadrat mit einer Größe größer als ( 2 t + 1 ) 2 überhaupt gekachelt werden: Nehmen wir an, wir versuchen, ein Quadrat mit einer Größefürzu kacheln; dann können wir nach dem Pigeonhole-Prinzip nicht mehr alsKacheln auf das Quadratpassen, was bedeutet, dass esQuadrate übrig - aber da,, ist die Anzahl derKacheln verfügbar.$2\times 2$$(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$

Somit sind die einzigen eindeutigen Kacheln, die für diejenigen, die überhaupt keine Kacheln verwenden, und ist nur dann ungleich Null, wenn ein Quadrat ist (in diesem Fall ist es gleich ).$n\gt 5$$2\times 2$$f(n)$$n$$\sqrt{n}$