Inclinaciones únicas de cuadrados

Queremos en mosaico -square usando dos tipos de mosaicos: -square tile y -square tile de modo que cada cuadrado subyacente se cubra sin superponerse. Definamos una función que proporcione el tamaño del cuadrado más grande que se puede labrar usando cuadrados y cualquier número de cuadrados.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$

¿Es esta función computable? ¿Qué es el algoritmo?

EDITAR1: Basado en la respuesta de Steven, el mosaico único significa que hay una forma de colocar los cuadrados dentro de -square con una configuración única para las posiciones de los cuadrados dentro del -square.m × m n 1 × 1 m × $2 \times 2$$m \times m$$n$ $1 \times 1$$m \times m$

Aquí hay un argumento para probar mi especulación en los comentarios de que no existen tales inclinaciones únicas para ningún no cuadrado . En primer lugar, como señaló Sasho en los comentarios, debe restringirse, porque no existen tales inclinaciones si o . Si es un cuadrado perfecto entonces, obviamente, el cuadrado es enlosable de manera única, por lo que está claramente definido y no es cero en estos casos. Para completar el argumento, solo queda mostrar que ningún mosaico que involucre o más mosaicos puede ser único.n n ≡ 2 $n\gt 5$$n$$n\equiv2$n n = k 2 k × k f ( n ) 1 2 × $3\pmod 4$$n$$n=k^2$$k\times k$$f(n)$$1$$2\times 2$

Primero, considere el caso , digamos . Si tenemos un mosaico de un usando mosaicos, obviamente debe ser par, digamos ; entonces podemos construir inclinaciones construyendo un mosaico mosaicos y luego reemplazando de estos por 'bloques' de cuatro mosaicos . Está claro que los reemplazos diferentes siempre pueden conducir a inclinaciones distintas, excepto en los casos o donde hay un solon = 4 k m × m n 1 × 1 m m = 2 j j × j 2 × 2 k 1 × 1 m = 4 , n = 12 m = 4 , n = 4 2 × $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$azulejo o un solo 'bloque de cuatro' sobrantes; en estos casos, sin embargo, hay un mosaico desigual diferente, uno que coloca un mosaico en el medio de un borde en lugar de en una esquina.$2\times 2$

Finalmente, suponga que , en particular suponga (y con para evitar un caso ligeramente trivial en el que simplemente "no hay suficiente espacio" en el cuadrado para que pase el siguiente argumento ) Entonces hay cuadrada de tamaño o más pequeño puede ser únicamente alicatable: considerar un suelo de baldosas con fichas a lo largo de la parte superior de la plaza y abajo de la derecha de la plaza (con ningún extra azulejos simplemente metido en el lado derecho, no pueden afectar el argumento). Ahora el 'bloque' en la esquina superior izquierda del cuadrado (que consta de las dos fichas en la parte superior y lasn = 4 t + 1 t > 1 ( 2 t + 1 ) 2 1 × 1 1 × 1 2 × 3 1 × 1 2 × 2 ( 2 t + 1 ) 2 ( 2 s + 1 ) 2 s > t s 2 2 × 2 ( 2 s + 1 $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$debajo de ellos) se pueden 'voltear' para producir un mosaico que necesariamente será diferente del mosaico que hemos construido. Finalmente, ningún cuadrado de tamaño mayor que puede ser enlosable en absoluto: supongamos que estamos tratando de enlosar un cuadrado de tamaño para ; entonces, según el principio del casillero, no podemos colocar más de fichas en el cuadrado, lo que significa que hay cuadrados sobrantes, pero como , , el número de mosaico que tenemos disponible.$(2t+1)^2$$(2s+1)^2$$s\gt t$$s^2\ 2\times 2$s > t 4 s + 1 > 4 t + 1 = n 1 × $(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$

Por lo tanto, las únicas inclinaciones únicas que existen para son aquellas que no usan ningún , y solo es distinto de cero cuando es un cuadrado (en cuyo caso es igual a ).2 × 2 f ( n ) n $n\gt 5$$2\times 2$$f(n)$$n$$\sqrt{n}$