Inclinações únicas de quadrados

Queremos ladrilhar $m\times m$ quadrado usando dois tipos de ladrilhos: $1 \times 1$ quadrado e $2 \times 2$ quadrado, de forma que todos os quadrados subjacentes sejam cobertos sem sobreposição. Vamos definir uma função $f(n)$ que fornece o tamanho do maior quadrado cultivável exclusivamente usando quadrados $n$ $1\times 1$ e qualquer número de $2 \times 2$ .

Esta função é computável? Qual é o algoritmo?

Edit1: Com base na resposta de Steven, meios telha única que existe uma maneira de colocar os -squares no interior do m × m quadr com uma configuração única para as posições do n 1 × 1 -squares no interior do m × m -quadrado.$2 \times 2$$m \times m$$n$ $1 \times 1$$m \times m$

Aqui está um argumento para provar minha especulação nos comentários de que não existem inclinações únicas para nenhum não quadrado . Em primeiro lugar, como observado por Sasho nos comentários, n deve ser restrito, porque não existem tais inclinações se n ≡ 2 ou $n\gt 5$$n$$n\equiv2$ . Se n é um quadrado perfeito n = k 2 , então, obviamente, o k × k quadrado é exclusivamente tileable, então f ( n ) está claramente definido e diferente de zero nestes casos. Para completar o argumento, ele só continua a mostrar que nenhuma telha envolvendo 1 ou mais 2 × 2 telhas podem ser único.$3\pmod 4$$n$$n=k^2$$k\times k$$f(n)$$1$$2\times 2$

Primeiro, considere o caso , diga n = 4 k . Se temos uma telha de um m × m quadrado usando n 1 × 1 telhas, obviamente, m deve ser ainda, dizem m = 2 j ; em seguida, pode-se construir tilings através da construção de um j x j ladrilhos de 2 × 2 telhas e em seguida, substituindo k destes por 'blocos' de quatro 1 × 1 telhas. É claro que substituições diferentes sempre podem levar a inclinações distintas, exceto nos casos m $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$ ou m = 4 , n = 4, onde restaum único bloco 2 × 2 ou um único bloco de quatro; nesses casos, no entanto, existe um lado a lado diferente e desigual, que coloca um lado 2 × 2 no meio de uma aresta e não em um canto.$m=4, n=12$$m=4, n=4$$2\times 2$$2\times 2$

Finalmente, suponha que , em particular, presuma n = 4 t + 1 (e com t > 1 para evitar um caso um pouco trivial, onde simplesmente não há espaço suficiente na praça para o argumento a seguir). Portanto, nenhum quadrado de tamanho ( 2 t + 1 ) 2 ou menor pode ser unicamente inclinável: considere um ladrilho com ladrilhos 1 × 1 na parte superior do quadrado e abaixo do lado direito do quadrado (comladrilhos 1 × 1 extrasapenas dobrados para o lado direito - eles não podem afetar o argumento). Agora os$n\equiv 1\pmod 4$$n=4t+1$$t\gt 1$$(2t+1)^2$$1\times 1$$1\times 1$ 'bloco' na parte superior esquerda do quadrado (consistindo dos dois 1 × 1 telhas sobre o topo e o 2 × 2 telha abaixo deles) pode ser 'virado' para produzir uma telha que irá necessariamente ser diferente do lado a lado que construímos. Finalmente, nenhum quadrado de tamanho maior que ( 2 t + 1 ) 2 pode ser inclinado: suponha que estamos tentando colocar um quadrado de tamanho ( 2 s + 1 ) 2 para s > t ; então pelo princípio pigeonhole não podemos caber mais do que s $2\times 3$$1\times 1$$2\times 2$$(2t+1)^2$$(2s+1)^2$$s\gt t$ ladrilhos no quadrado, o que significa que existem ( 2 s + 1 ) 2 - 4 s 2 = 4 s 2 + 4 s + 1 - 4 s 2 = 4 s + 1 quadrados restantes - mas como s > t , 4 s + 1 > 4 t + 1 = n , o número de 1 × $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$ telhas que temos disponíveis.

$n\gt 5$$2\times 2$$f(n)$$n$$\sqrt{n}$