Zadaci o poliminima

1. Šahovska tabla se može prekriti pomoću 32 domine. Ako se izrežu polje u levom donjem uglu i polje u gornjem desnom uglu table onda na njoj istaju još 62 polja. Da li se ta preostala polja mogu prekriti pomoću 31 domine?

2. Iz šahovske table su izrezana dva polja različite boje - jedno belo i jedno crno polje. Da li se preostali deo šahovske table može prekriti dominama?

3. Iz šahovske table treba izrezati nekoliko polja tako da se nikoja dva polja preostalog dela table ne mogu prekriti dominom. Koliko iznosi najmanji broj polja koja se moraju izrezati?

poz.

Da bi dobili predstavu kako se rešavaju ovakvi zadaci rešiću drugi zadatak.

2. Kad se izbace dva polja iste boje na tabli ostaje 32 polje jedne boje i 30 polja druge boje. Kako svaka domina pokriva tačno jedno crno i jedno belo polje, zaključujemo da se nemoguće popločati ovakvu tablu dominama.

poz.

U levom donjem uglu i desnom gornjem uglu nalaze se polja iste boje, tako da si ti rešio prvi zadatak kao pomoć, a ne drugi.

A za drugi zadatak rešenje je potvrdno, s tim što za netrivijalan slučaj (isečena dva susedna polja) moramo da ređamo domine menjajući im horizontalan i vertikalan položaj.

Naime, ako krenemo po jednoj koloni šahovske table, ređajući domine vertikalno (tako da ostanu u koloni), nastavićemo da radimo isto po kolonama, dok ne naiđemo na polje koje fali. Tada će nas od tog polja razdvajati jedno ili dva polja.

Dva polja možemo prekriti dominom, a na kraju kolone u kojoj se trenutno nalazimo ostaje jedno nepokriveno polje. Pokrićemo ga horizontalnom dominom, povezujući i sledeću kolonu. Postupak se prosto nastavi do kraja pokrivanja vertikalnim dominama (na kraju kolona horizontalnim). Slučaj koji će nastati kod drugog polja koje fali svodi se na neki od ova dva.

Ako nas deli jedno polje od polja koje fali, odmah ćemo ga prekriti horizontalnom dominom, povezujući i sledeću kolonu. Pa će postupak nastaviti tom sledećom kolonom. Kad ovo pokrivanje završimo, prekrili smo paran broj polja,od kojih je pola belo,a pola crno, odatle sledi da nam je ostao paran broj polja, od kojih je pola belo, a pola crno. Znači, može se opet prekriti dominama.

poz

Potpis

beeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeezi

U pravu si...

poz.