Susunan kotak yang unik

Kami ingin mem-tile -square menggunakan dua jenis ubin: -square kuadrat dan -square kuadrat sehingga setiap kotak yang mendasarinya tertutup tanpa tumpang tindih. Mari kita mendefinisikan fungsi yang memberikan ukuran kuadrat unik unik terbesar yang bisa digunakan menggunakan kuadrat dan sejumlah kuadrat. $m\times m$ $1 \times 1$ $2 \times 2$ $f(n)$ $n$ $1\times 1$ $2 \times 2$

Apakah fungsi ini dapat dihitung? Apa algoritma itu?

EDIT1: Berdasarkan jawaban Steven, ubin unik berarti bahwa ada satu cara untuk menempatkan -bidang di dalam persegi dengan konfigurasi unik untuk posisi -bidang di dalam -square. $2 \times 2$ $m \times m$ $n$ $1 \times 1$ $m \times m$

computability combinatorics Mohammad Al-Turkistany
sumber

Bagaimana penggilingan unik didefinisikan? Misalnya, mungkin ada 4 rangkaian simetris. Apakah mereka unik atau tidak?

Paresh

Miring simetris dianggap sebagai satu konfigurasi.

Mohammad Al-Turkistany

menggunakan 1-by-1 kotak atau menggunakan paling banyak ? jika tidak, tidak selalu didefinisikan: Anda tidak dapat memasang kotak dengan 2 ubin 1-by-1 dan jumlah ubin 2-by-2, karena luasnya dan 2 bukan modulo residu kuadratik. menurut simetri maksud Anda grup dihedral ?

n

$n$

n

$n$

f

$f$

4 x + 2

$4x + 2$

D_{4}

$D_4$

Sasho Nikolov

Baik. Pada kasus tersebut, tentukan . Saya tidak akrab dengan grup D4 dihedral.

f (n) = 0

$f(n)=0$

Mohammad Al-Turkistany

Aku takut aku masih bingung - contoh akan pergi lama jalan menuju membantu memahami, mungkin. Bagaimana jawaban yang diberikan tidak menjawab pertanyaan?

Steven Stadnicki

Berikut argumen untuk membuktikan spekulasi saya dalam komentar bahwa tidak ada tilings unik seperti untuk non-square . Pertama, seperti dicatat oleh Sasho dalam komentar, harus dibatasi, karena tidak ada seperti itu jika atau . Jika adalah kuadrat sempurna maka jelas kuadrat unik tileable, jadi didefinisikan dengan jelas dan tidak nol dalam kasus ini. Untuk melengkapi argumen, tetap saja menunjukkan bahwa tidak ada ubin yang melibatkan atau lebih ubin dapat menjadi unik. $n\gt 5$ $n$ $n\equiv2$ $3\pmod 4$ $n$ $n=k^2$ $k\times k$ $f(n)$ $1$ $2\times 2$

Pertama, pertimbangkan case , misalkan . Jika kita memiliki ubin kuadrat menggunakan ubin, jelas harus genap, katakanlah ; maka kita dapat membangun tilings dengan membangun ubin ubin dan kemudian mengganti ini dengan 'blok' dari empat ubin. Sudah jelas bahwa penggantian yang berbeda selalu dapat mengarah ke kemiringan yang berbeda kecuali dalam kasus atau mana ada satu saja $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$ ubin atau satu 'blok empat' yang tersisa; dalam kasus ini, meskipun, ada ubin berbeda yang berbeda, yang menempatkan ubin di tengah tepi daripada di sudut. $2\times 2$

Akhirnya, misalkan , khususnya (dan dengan untuk mencegah kasus yang agak sepele di mana ada 'ruang tidak cukup' di alun-alun untuk argumen berikut untuk pergi melalui ). Maka tidak ada kuadrat ukuran atau lebih kecil yang dapat ubin unik: pertimbangkan ubin dengan ubin di bagian atas alun-alun dan di sebelah kanan kotak (dengan tambahan ubin hanya terselip di sisi kanan - mereka tidak dapat mempengaruhi argumen). Sekarang 'blok' di kiri atas kotak (terdiri dari dua ubin di atas dan $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$ ubin di bawahnya) dapat 'dibalik' untuk menghasilkan ubin yang tentu akan berbeda dari ubin yang kami bangun. Akhirnya, tidak ada kuadrat ukuran yang lebih besar dari dapat tileable sama sekali: misalkan kita mencoba untuk ubin ukuran persegi untuk ; maka dengan prinsip pigeonhole kita tidak dapat memuat lebih dari ubin ke kotak, yang berarti ada kotak tersisa - tetapi karena , , jumlah petak yang kami miliki. $(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$

Dengan demikian, satu-satunya tilings unik yang ada untuk adalah yang menggunakan no ubin sama sekali, dan hanya nol ketika adalah kotak (dalam hal ini sama dengan ). $n\gt 5$ $2\times 2$ $f(n)$ $n$ $\sqrt{n}$

Steven Stadnicki
sumber

karena saya menemukan bagian di mana Anda menyelipkan sisa 1 dengan 1 ubin ke kanan rapuh (mungkin tanpa alasan), di sini adalah tampilan yang sedikit berbeda pada kasus di mana dan ukuran kotak adalah . perhatikan bahwa atau . dalam kedua kasus dibutuhkan 1 oleh 1 ubin untuk membangun batas ketebalan 1 untuk bujur sangkar. lalu kita pergi dengan 1 oleh 1 ubin. dalam kasus kami memiliki dan Anda telah mengatasinya. kalau tidak kita telah mengurangi paragraf sebelumnya.

n = 4 t + 1

$n = 4t + 1$

x^{2} < (2 t + 1)^{2}

$x^2 < (2t + 1)^2$

x \equiv 1

$x \equiv 1$

x \equiv 3 (\mod 4)

$x \equiv 3 \pmod 4$

2 x - 1 \equiv 1 (\mod 4)

$2x - 1 \equiv 1 \pmod 4$

n^{'} \equiv 0 (\mod 4)

$n' \equiv 0 \pmod 4$

n^{'} = 0

$n' = 0$

x = 2 t + 1

$x = 2t + 1$

Sasho Nikolov

Ubin unik yang valid harus menggunakan kedua jenis ubin. Maaf karena tidak menyatakannya dengan jelas dalam pertanyaan saya.

Mohammad Al-Turkistany

@ MohammadAl-Turkistany Steven membuktikan di atas bahwa tidak ada tilings unik seperti untuk . sebenarnya satu-satunya ubin unik "valid" sesuai dengan definisi Anda adalah untuk (ubin 2-by-2 tunggal dan "sudut" dari 5 1-oleh-1).

n > 5

$n>5$

n = 5

$n=5$

Sasho Nikolov

@ Sebelas Terima kasih atas jawaban Anda, pernyataan saya tentang persyaratan keunikan tidak menarik karena mengarah ke fungsi yang dapat dihitung dengan mudah. Apakah Anda pikir itu dapat diperbaiki dengan mengharuskan kami mengemas jumlah maksimum kuadrat sementara posiblliy membiarkan beberapa kuadrat tidak terbuka? Motivasi saya adalah untuk membangun fungsi yang tidak dapat dihitung dari masalah kombainatorial sederhana.

2 \times 2

$2 \times 2$

m \times m

$m \times m$

Mohammad Al-Turkistany

@ Seven, jawaban Anda memecahkan pertanyaan asli tetapi tidak persis apa yang memotivasi saya untuk mengajukan pertanyaan. Saya harap Anda tidak terganggu dengan memodifikasi pertanyaan seperti yang saya jelaskan di komentar sebelumnya.

Mohammad Al-Turkistany

Susunan kotak yang unik

Jawaban: