7. Zadatak
Za rastavljanje šahovske ploče dimenzija na disjunktne pravokutnike kažemo da je raznovrsno ako su ispunjena sljedeća dva uvjeta:
- svaki pravokutnik u rastavu sadrži jednak broj crnih i bijelih polja;
- ne postoje dva pravokutnika koja sadrže isti broj polja.
Odredi najveći prirodni broj za koji postoji raznovrsno rastavljanje ploče dimenzija na pravokutnika.
Rješenje
Pravokutnik sadrži jednak broj crnih i bijelih polja ako i samo ako je njegova površina paran broj (tj. ako i samo ako je duljina barem jedne stranice paran broj).
Tvrdimo da je odgovor , tj. da raznovrsno rastavljanje može imati najviše pravokutnika.
Pretpostavimo suprotno da postoji barem pravokutnika u raznovrsnom rastavljanju ploče dimenzija . Tada bi ukupna površina ploče morala biti veća ili jednaka zbroju najmanjih pravokutnika u rastavljanju, a to je barem
Budući da je , dobili smo kontradikciju. Dakle, raznovrsno rastavljanje ploče može imati najviše pravokutnika.
Sljedeći primjer pokazuje da zaista postoji raznovrsno rastavljanje ploče na pravokutnika.
Službena dodatna napomena.
Primjer nije jedinstven. Dapače, postoje raznovrsna rastavljanja ploče na pravokutnika koja imaju drugačije površine pravokutnika nego u primjeru u rješenju. Na primjer, imamo sljedeće raznovrsno rastavljanje:
