Pokrytí šachovnice I VŠB-TU Ostrava, fakulta FEI Obor: Předmět: Zpracoval: Datum odevzdání:
Informatika – výpočetní technika Diskrétní matematika (DIM) Přemysl Klas (KLA112) 25.11.2005
1) Abstrakt: Máme šachovnici o rozměrech n x n políček. K dispozici máme neomezený počet dílků ve tvaru kostek známé hry „TETRIS“, každý složený ze čtyř čtverečků stejného rozměru jako jedno políčko šachovnice. Pro která n je možno šachovnici pokrýt dílkem „I“ , dílkem „o“, dílkem „T“, dílkem „L“ a dílkem „S“? Tvrzení dokažte.
2) Příprava a rozbor příkladu: Kostky, které jsou k dispozici (jsou barevně rozlišeny kvůli názornosti):
Pro logické vyřešení problému jsem zvolil tento postup: Ze zadaného vzorce n x n plyne, že šachovnice musí mít tvar čtverce. Abychom našli u každé kostky pokrytí šachovnice bez zbylých volných polí je nutné u každé kostky zvlášť (I, o, T, L, S) najít takový čtverec o n x n políčcích, aby bylo použito jednotlivých dílů co nejméně. Poté je nutno nalézt nejbližší vetší čtverec složitelný z nejbližšího vyššího možného počtu užitých jednotlivých kostek a tímto způsobem nalézt další větší, atd. až je možné vyvodit závěr, z kterého lze přesně vyjádřit počet n potřebných k pokrytí.
3) Řešení jednotlivých úloh: a) pro „I“ : Nejmenší možný čtverec, který lze vytvořit z dílků „I“ lze vytvořit dvěma způsoby:
Jiné možnosti Jiné m uspořádání kostek „I“ neexistují do čtverce 4 x 4
nebo
Z toho tedy plyne, že nejmenší možný čtverec vytvořitelný z kostek „I“ je 4 x 4. Nejbližší větší složený čtverec je:
což je pokrytí 8 x 8 polí.
Pokud budeme ve skládání pokračovat, dojdeme k pokrytí 12 x 12 polí, 16 x 16 polí atd.
Závěr pokrývání šachovnice kostkami „I“: Nejmenší n x n šachovnice kterou lze pokrýt kostkami „I“ má velikost 4 x 4 polí a každé další pokrytí lze získat vynásobením 4 libovolným číslem. Obecně: n může nabývat hodnot
4⋅i
pro
i∈N ,
tedy kostkami „I“ lze pokrýt šachovnici o počtu polí
4i ⋅ 4i pro i ∈ N .
b) pro „o“: Nejmenší možný čtverec, který lze vytvořit z kostek „o“ není nutné skládat, kostka „o“ již tvoří čtverec sama o sobě, tedy nejmenší možný čtverec bude mít rozměry 2 x 2 pole. Nejbližší větší složený čtverec bude tedy vypadat takto:
což tvoří šachovnici o 4 x 4 polích a není možné žádné jiné uspořádání.
Dalším skládáním dojdeme k hodnotám 6 x 6 polí, 8 x 8, atd. Žádná uspořádání 3 x 3 nebo 5 x 5 nejsou možná
Závěr pokrývání šachovnice kostkami „o“: Nejmenší n x n šachovnice kterou lze pokrýt kostkami „o“ má velikost 2 x 2 pole a každé další pokrytí lze získat vynásobením 2 libovolným číslem. Obecně: n může nabývat hodnot
2⋅o
pro
o∈ N ,
tedy kostkami „o“ lze pokrýt šachovnici o počtu polí
2o ⋅ 2o pro o ∈ N .
c) pro „T“: Nejmenší možný čtverec, který lze vytvořit z kostek „T“ bude vypadat takto (2 jediné možné způsoby): což tvoří šachovnici o 4 x 4 polích a není možné žádné jiné uspořádání.
nebo
Nejbližší větší složený čtverec bude tedy vypadat takto:
což tvoří šachovnici o 8 x 8 polích, žádné jiné uspořádání větší než 4 x 4 pole a menší než 8 x 8 polí neexistuje, neboli pro 4 < n < 8 je n = φ
Dalším skládáním dojdeme k hodnotám 12 x 12 polí, 16 x 16, atd.
Závěr pokrývání šachovnice kostkami „T“: Nejmenší n x n šachovnice kterou lze pokrýt kostkami „T“ má velikost 4 x 4 polí a každé další pokrytí lze získat vynásobením 4 libovolným číslem. Obecně: n může nabývat hodnot
4⋅t
pro
t∈N ,
tedy kostkami „T“ lze pokrýt šachovnici o počtu polí
4t ⋅ 4t pro t ∈ N
.
Pozn. Můžeme si všimnout, že řešení s kostkami „T“ je obdobné jako u kostek „I“, obdobně tomu bude i u kostek „L“
d) pro „L“: Nejmenší možný čtverec, který lze vytvořit z kostek „L“ bude vypadat takto (jelikož různých uspořádání je více – konkrétně 8, uvedu zde jen 2 příklady): opět jsme získali šachovnici o 4 x 4 polích
nebo
Nejbližší větší složený čtverec bude tedy vypadat takto:
což tvoří šachovnici o 8 x 8 polích, žádné jiné uspořádání větší než 4 x 4 pole a menší než 8 x 8 polí neexistuje, neboli pro 4 < n < 8 je n = φ
Dalším skládáním dojdeme k hodnotám 12 x 12 polí, 16 x 16, atd.
Závěr pokrývání šachovnice kostkami „L“: Nejmenší n x n šachovnice kterou lze pokrýt kostkami „L“ má velikost 4 x 4 polí a každé další pokrytí lze získat vynásobením 4 libovolným číslem. Obecně: n může nabývat hodnot
4⋅l
pro
l∈N ,
tedy kostkami „L“ lze pokrýt šachovnici o počtu polí
4l ⋅ 4l pro l ∈ N
.
e) pro „S“: Pro kostky „S“ nelze beze zbytku (volných polí) čtverec vytvořit. Například jedno z možných uspořádání:
tímto způsobem lze ve skládání pokračovat do neomezené délky a nikdy nelze dosáhnout úplného pokrytí čtverce.
Závěr pokrývání šachovnice kostkami „S“: Pro kostky „S“ nelze šachovnici pro libovolná n nikdy beze zbytku pokrýt, tedy vždy zůstanou na šachovnici volná nepokrytá pole. Obecně: Pokrytí šachovnice kostkami „S“ nemá řešení, tedy
n =φ
4) Závěr: Optické zobrazení je dobrou ukázkou možností pokrytí šachovnice a vytvoří tak konkrétní představu o tom, jak uspořádání může vypadat. Navíc lze z obrázku logicky vyvodit závěr a obrázek tak vytváří důkaz o tom, jak je možné šachovnici kostkami pokrývat.
Poznámka na závěr: Pro vyjádření rozměrů šachovnice jsem používal značení x pro aritmetické násobení, toto značení je použité pouze pro názornost.
