Logičan zadatak za postavljanje domina na šahovsku ploču. Matematičke olimpijade i olimpijski zadaci
Dato je šahovska tabla 8×8, sa koje su izrezana dva dijagonalno suprotna ugla, i 31 domina; svaka domino može pokriti dva polja na ploči. Da li je moguće cijelu ploču popločati kostima? Dajte obrazloženje za svoj odgovor.
Rješenje
Na prvi pogled se čini da je to moguće. Ploča je 8×8, dakle, ima 64 ćelije, izuzimamo dvije, što znači da ostaje 62. Čini se da 31 kost treba da stane, zar ne?
Kada pokušamo da složimo domine u prvi red, imamo samo 7 polja na raspolaganju, jedna kost ide u drugi red. Zatim stavljamo domine u drugi red, a opet jedna pločica ide u treći red.
U svakom redu će uvijek biti jedna kost koju treba premjestiti u sljedeći red, bez obzira na to koliko rasporeda pokušamo, nikada nećemo moći postaviti sve kosti.
Šahovska ploča je podijeljena na 32 crne i 32 bijele ćelije. Uklanjanjem suprotnih uglova (imajte na umu da su ove ćelije iste boje), ostaje nam 30 ćelija jedne boje i 32 ćelije druge boje. Pretpostavimo da sada imamo 30 crnih i 32 bijela kvadrata.
Svaka kockica koju ćemo staviti na ploču zauzimat će jednu crnu i jednu bijelu ćeliju. Dakle, 31 domina će zauzeti 31 bijelu i 31 crnu ćeliju. Ali na našoj tabli ima samo 30 crnih i 32 bijele ćelije. Stoga je nemoguće razgraditi kosti.
Analiza je preuzeta iz prijevoda knjige G. Luckmana McDowella i namijenjena je samo u informativne svrhe.
Ako vam se svidjela, preporučujemo da kupite knjigu.
Dokažite da je šahovnica 10X10 se ne može rezati duž linija mreže u pravokutnike 1X4. (Rješenja prema D.Yu. Kuznjecovu.)
Rješenje 1 . Podijelite ploču na kvadrate 2x2 i obojite ih u šahovnici (slika 1). Imajte na umu da bilo koji pravougaonik 1x4 sadrži podjednako (2) crne i bijele ćelije, ali s ovim bojanjem, na ploči se nalaze 52 crne ćelije i 48 bijelih ćelija, tj. ne podjednako. To znači da neće biti moguće rezati ploču 10x10 na pravokutnike 1x4.
Rješenje 2 . Obojimo ploču dijagonalnim bojama u 4 boje (slika 2). Imajte na umu da bilo koji pravougaonik sadrži po jednu ćeliju svake od četiri boje, ali uz datu boju, na ploči se nalazi 25 ćelija 1. i 3. boje, 26 ćelija 2. i 24 ćelije 4., tj. ne podjednako. To znači da neće biti moguće rezati ploču 10x10 na pravokutnike 1x4.
1. Izrežite ćelije donjeg desnog i lijevog ugla sa šahovske ploče. Da li je moguće rezultujuću figuru izrezati na domine 1x2? A ako isečete donji desni i gornji levi?
2. Da li je moguće iseći ploču 6x6 na domine tako da među njima bude tačno 11 horizontalnih? (Horizontalno bojenje u dvije boje.)
3. Obojite crtež u četiri boje tako da susedni delovi budu obojeni različitim bojama. Da li je moguće proći sa tri boje? (Pogledajte aktivnost 6: Bojanje geografska karta- 5-6 razred).
4. U kvadratu 4x4 ćelije lijeve polovine su obojene crnom bojom, a ostale bijele. U jednoj operaciji, dozvoljeno je promijeniti boju svih ćelija unutar bilo kojeg pravokutnika u suprotnoj boji. Kako dobiti šahovsku boju od originalne boje u tri operacije?
5. Nekoliko skakavaca sjedi na istoj pravoj liniji, a razmaci među susjedima su jednaki. Svaki minut jedan od njih skače do tačke simetrične njoj u odnosu na drugog skakavca. Može li posle nekog vremena skakavac Saša završiti na mestu gde je na početku sedeo njegov komšija Ljoša?
6. a) Da li je moguće izrezati šahovsku tablu na figure koje se sastoje od 4 ćelije u obliku slova "T"?
b) Da li je moguće izrezati šahovsku tablu 10x10 na takve figure?
7. Da li je moguće kvadrat 8x8 sa odsečenim uglom podeliti na pravougaonike 1x3?
8. Da li se ploča 10x10 može iseći na komade od četiri ćelije u obliku slova "G"? (Horizontalno bojenje u dvije boje.)
9. Ploča 8x8 je izrezana na domine 2x1. Može li postojati 15 vertikalnih i 17 horizontalnih domina?
10. Trokut je podijeljen na trouglove (25 komada), kao što je prikazano na slici. Buba može hodati u trokutu, krećući se između susjednih (sa strane) trokuta. Koliki je maksimalni broj trouglova kroz koje buba može proći ako je svaki trougao posjetila najviše jednom?
11. Koji je najveći broj rombova, od kojih je svaki sastavljen od dva jednakostranična trougla sa stranicom 1, koji se mogu iseći iz jednakostraničnog trougla sa stranicom 5 (vidi sliku prethodnog zadatka).
12. Trouglasti dvorac podijeljen je na 100 identičnih trouglastih dvorana. Na sredini svakog zida su vrata. Koliko soba može posjetiti osoba koja ne želi nigdje posjetiti više od jednom?
Poglavlje 2
Za detaljan prikaz šahovske matematike, koji ćemo upravo započeti, najprirodnije je početi s matematički problemi o samoj ploči, bez postavljanja komada na nju. Ovoj temi je posvećeno ovo poglavlje.
Razmotrimo prije svega nekoliko problema pokrivanja ploče dominama 2 × 1. Svugdje se pretpostavlja da svaka domino pokriva dva polja ploče, a svako polje je prekriveno polovicom domina. Počnimo sa sljedećim starim problemom.
Da li je moguće obložiti dominom kvadrat veličine 8×8 iz kojeg su izrezane ćelije nasuprot uglova (slika 2a)?
Mogli bismo koristiti algebarsko razmišljanje, ali "šahovsko" rješenje je i jednostavnije i elegantnije. Obojimo naš skraćeni kvadrat u crno-bijelo, pretvarajući ga u šahovsku ploču bez dva kutna polja a8 i h1 (slika 2b). Za bilo koje pokrivanje ploče, svaka domino pokriva jedan bijeli i jedan crni kvadrat. Imamo dva manje bela polja od crnih (izrezana polja su bijela), te stoga ne postoji potrebna pokrivenost! Kao što vidimo, bojanje table ne samo da olakšava navigaciju šahistu tokom igre, već služi i kao sredstvo za rješavanje matematičkih zadataka.
U razmatranom problemu nije bilo važno da su kutna polja izrezana iz ploče, već da su iste boje. Jasno je da bez obzira na to kako izrežete par jednobojnih polja, ostatak ploče nećete moći prekriti dominama. Stoga se javlja sljedeći problem.
Pretpostavimo sada da su na šahovskoj tabli izrezana dva polja različitih boja. Da li je uvijek moguće pokriti ostatak ploče sa 31 domino?
Ispostavilo se da je to uvek. Spektakularan dokaz pronašao je poznati američki matematičar R. Gomory. Nacrtajmo na šahovskoj ploči granice između vertikala i horizontala kao što je prikazano na sl. 3. U lavirintu između ovih granica, crno i bijelo polje slijede jedno za drugim, naizmjenično kao dugmad od dvije boje na zatvorenoj niti (puta kojom se ovaj labirint može zaobići je zatvorena). Koja god dva polja različitih boja izrezali iz ploče, nit će puknuti: na jednom mjestu ako su izrezana polja susjedna, a na dva mjesta u suprotnom. U ovom slučaju, svaki komad niti će se sastojati od parnog broja polja. Shodno tome, ovi dijelovi, a time i cijela ploča, mogu se prekriti dominama!
Rice. 3. Labirint Gomori |
Zanimljive ideje vezane za dugmad i niti naći ćete u 11. poglavlju.
Pretpostavimo da su neka polja izrezana iz šahovske ploče tako da se na preostali dio ne mogu staviti domine. Lako je provjeriti da je najmanji broj izrezanih polja sa ovim svojstvom 32 - sva su polja iste boje (bijela ili crna).
Problemi sa šahovskom pločom i domino samo su mali dio velikog niza problema ove vrste. Američki matematičar S. Golomb stvorio je čitavu nauku koju je nazvao polimipo, a njegova knjiga na ovu temu prevedena je u mnogim zemljama svijeta, uključujući i našu. Općenito, poliomino je jednostavno povezana figura koja se sastoji od kvadrata. Sa tačke gledišta šahista, jednostavno povezivanje znači da se sva poliomino polja mogu zaobići potezom topa. U zavisnosti od broja kvadrata 07, poliominoi dolaze u različitim razredima. Monomino sadrži jedno polje, domino dva, tromino tri, tetramino četiri, pentomino pet, heptomino šest kvadrata, itd. Zadržaćemo se na još nekoliko pitanja vezanih za običnu šahovsku tablu. Očigledno, nemoguće je pokriti dssk samo ravnim trominima, tj. dominama 3 × 1, pošto 64 nije deljivo sa 3. Pojavljuje se sledeći problem.
Da li je moguće pokriti šahovsku tablu sa 21 ravnim trominom i jednim monominom? Ako je tako, koja polja može zauzimati monomino?
Jedan od potrebnih dapo premaza na Sl. 4a. Da bismo odredili moguće rasporede monomina, nacrtamo dva sistema paralelnih linija na tabli, kao što je prikazano na sl. 4b.
Lako je vidjeti da za bilo koje pokrivanje svaki tromino pokriva tačno jedno polje kroz koje prolazi puna linija i tačno jedno kroz koje prolazi isprekidana linija. Budući da je broj polja koja se sijeku punim linijama 22, kao i broj polja koja se sijeku isprekidanim linijama, a tromino je 21, monomino može pokriti samo polja koja sijeku obje porodice linija. A postoje samo četiri takva kvadrata: c3, c6, f3 i f6! Rotirajući ploču za 90, 180 i 270°, možete dobiti odgovarajuću pokrivenost za svako od ova četiri polja.
Sljedeći zadatak je nešto drugačiji od onih o kojima je bilo riječi gore.
Da li je moguće pokriti šahovsku tablu dominama na način da je nemoguće povući jednu granicu između vertikala i horizontala bez prelaska domina?
Ako zamislimo da je ploča zid, a domine cigle, tada postojanje navedene granice (šava) ukazuje na krhko zidanje. Drugim riječima, problem se postavlja da li je moguće posložiti "cigle" tako da se "zid" ne uruši. Pravougaonik koji se može pokriti na traženi način naziva se "jak". "Jačina" šahovske table može se videti na Sl. 5. U opštem slučaju, Gardner pokazuje da se domine mogu presavijati u "snažan" pravougaonik ako je njihova površina ravna, a dužina i širina su veće od četiri, sa jedinim izuzetkom kvadrata 6 × 6.
U nastavku ćemo se često baviti pravokutnim šahovskim pločama jedne ili druge veličine. U ovom slučaju, uvijek se pretpostavlja da m×n tabla ima m vertikala i n horizontala (šah). Kažemo da je ploča "parna" ako je broj njenih polja paran, a "neparna" u suprotnom. Gdje god dimenzije ploče nisu navedene, mislimo na standardnu šahovsku ploču za koju je m = n = 8.
Ploča 100x4 je prekrivena dominama. Dokažite da se može rezati duž jedne od granica između vertikala i horizontala bez utjecaja na domine.
Bilo koja od navedenih ivica dijeli ploču na dva dijela, koja se sastoji od parnog broja polja. Polja svakog dijela dijelimo u dvije klase: pokrivene domine koje u cijelosti leže u ovom dijelu i pokrivene domine koje se presjecaju granicom. Pošto je broj polja svakog dela paran (možda nula), kao i broj polja prve klase (svaka domino pokriva dva polja), broj polja druge klase je paran. A to znači da je broj domina koje prelazi granica paran. Ukupno ima 102 razdjelne granice (99 vertikalnih i 3 horizontalne), a ako svaka od njih prelazi domine, tada u pokrivanju učestvuje najmanje 102 × 2 = 204 domine. Imamo ih samo 200! U stvari, pokazali smo da je pravougaonik 100x4 "slab".
Pitanje mogućnosti pokrivanja proizvoljne pravokutne ploče linearnim k-minos (domino k × 1) rješava se sljedećim teoremom.
Ploča m×n može biti prekrivena linearnim k-minosima ako i samo ako je barem jedan od brojeva m ili n djeljiv sa k bez ostatka.
Teoremu ćemo ilustrirati sljedećim primjerom.
Da li je moguće pokriti ploču 10x10 (na takvoj se igra sto kvadrata) ravnim tetraminima?
Ravni tetramino ima dimenzije 4x1, što znači da u principu 25 pločica može pokriti sva polja naše ploče. Međutim, iz teoreme slijedi da je to nemoguće - 10 nije djeljivo sa 4.
Razmotrimo još nekoliko problema o šahovskoj tabli. U rješenju sljedećeg problema vovb koristi se njegovo bojenje.
Neka se tabla sastoji od neparnog broja polja. Na svako od njegovih polja stavićemo neke šahovska figura. Da li je moguće premjestiti sve ove figure na susjedne kvadrate (vertikalno ili horizontalno) tako da dvije ne završe na istom polju?
Zadatak je nemoguć. Zaista, da postoji naznačeno pomjeranje figura, onda bi svaka "bijela" figura (stajala na bijelom polju) postala "crna" (pala na crno polje), a svaka "crna" - "bijela".
Dakle, tabla bi se sastojala od istog broja bijelih i crnih polja, a to je u suprotnosti sa njenom "čudnošću".
Popularni su problemi rezanja šahovske table. Najpoznatiji od njih je sljedeći, vlasništvo S. Loyda.
Na poljima a1, b2, c3, d4 nalaze se četiri viteza. Izrežite ploču na četiri podudarna dijela (koja se poklapaju kada se preklapaju) tako da svaki od njih ima konja.
U problemima rezanja, uvijek se pretpostavlja da se rezovi rade samo duž granica između vertikala i horizontala ploče. Rješenje ovog problema je prikazano na sl. 6. Od vremena Loyda pojavilo se mnogo novih i težih problema na ovu temu. Konkretno, riješeni su problemi rezanja ploče na četiri kongruentna dijela za različite pozicije vitezova (vitezovi, naravno, ovdje igraju samo simboličku ulogu). Još uvijek ima mnogo neriješenih pitanja po ovom pitanju. Na primjer, još uvijek nije poznat broj načina na koje se obična ploča (bez dijelova) može rezati na dva podudarna dijela.
Rice. 6. Loydov problem četiri konja |
Neka se, nakon nekoliko rezova ploče, dobijeni dijelovi pomaknu tako da sljedeći rez može rezati ne jedan, već nekoliko dijelova odjednom. Koliko će rezova biti potrebno da dobijete 64 pojedinačna mjesta na ploči (1×1 kvadrata)?
Prvo prepolovimo ploču, zatim stavimo obje polovice jednu pored druge i izrežemo ploču na četiri identična dijela, itd. Ukupno će biti potrebno 6 rezova (2 e = 64), a manji broj se ne može izostaviti .
Neka se sada dijelovi ploče mogu rezati samo odvojeno. Koliko rezova će biti potrebno da se dobije 64 polja u ovom slučaju?
U pravilu, ovaj zadatak (naročito ako je predložen nakon prethodnog) izaziva određene poteškoće. Očigledno je to zbog neke inercije našeg razmišljanja. Uostalom, odmah je jasno da će biti potrebna 63 rezanja! Zaista, svaki rez povećava broj dijelova za jedan; istovremeno, u početnom trenutku imamo jedan dio (samu tablu), au konačnom trenutku - 64 (sva polja ploče).
Rice. 7. Tri problema na neobičnoj ploči |
U zadatku na sl. 7a, potrebno je da uradite tri zadatka, jedan matematički i dva čisto šahovska:
a) iseći ploču na četiri podudarna dijela;
b) matirati crnog kralja na najkraći način kada se bijeli krene;
c) matirati crnog kralja na najkraći način, dok crni kreću, vjerni igraju kooperativno).
Rješenja: a) kako seći dasku, prikazano na sl. 7b; b) kada bijeli krene, mat se daje u 12. potezu: 1-12. Be1-b4, Ke3-d3-c4, Be4-c2-b3, Kc4-c3, Bb4-d6, Bb3-d5, Kc3-c2, Bd6-c5, Bd5-c4, Bd6-b4 mat (svi potezi crnog kralja su forsirani i ne daju se); c) pravilnom igrom nakon 1. ... Ke6-e7 mat je nemoguć, pošto se crni kralj krije na e8 - 2. Be1-b4+ Ke7-e8, a tamni kvadrat je prisiljen da napusti dijagonalu a3 - e7 zbog opasnosti od zastoja. Međutim, ako crni igraju kooperativno (pomažući bijelim mat), onda se cilj postiže u samo tri poteza:
1. … Ke6-d6
2. Ke3-d4 Ke6-e7
3. Be1-b4+ Ke7-e6
4. Be4-d5 drug. Brojna polja naše ploče se ne koriste tokom parenja, ali da su isključena ne bi bilo problema sa sečenjem daske.
Rice. 8. Paradoks sa sečenjem šahovske table: a) 8×8 = 64; b) 13×5 = 65 |
Razmotrite sada jedan dobro poznati paradoks povezan sa sečenjem šahovske table. Dasku smo izrezali na četiri dijela, kao što je prikazano na sl. 8, a (u ovom slučaju za nas je neisplativo bojati njegova polja), a od rezultirajućih dijelova dodaćemo pravougaonik (slika 8, b). Površina ploče je 64, a površina rezultujućeg pravougaonika je 65. Dakle, prilikom sečenja ploče, odnekud je došlo jedno dodatno polje!
Rješenje paradoksa je da naši crteži nisu sasvim tačni (namjerno smo povukli debele linije da sakrijemo nepreciznosti). Pažljivom konstrukcijom crteža na sl. 8b, umjesto dijagonale pravougaonika, pojavit će se figura u obliku dijamanta, blago izdužena sa stranicama koje su izgleda skoro spojene. Površina ove figure će biti jednaka "ekstra" jedinici.
Poznati popularizator matematike s početka veka, E. Ignatiev, osmislio je „metodu šahovske table“, koja omogućava izvođenje različitih formula. Dajemo dva jednostavna primjera na ovu temu.
Nađimo zbir prvih n prirodnih brojeva koristeći "metodu šahovnice". Da bismo to učinili, na tabli (n + 1) × n (na slici 9, a n = 8) bojimo sva polja prve vertikale, sva polja druge vertikale (osim gornje), treća vertikala (osim dvije gornje) itd. d., na kraju - donja polje nth vertikalno. Kao rezultat, bijela i crna polja na našoj ploči će biti jednaka, odnosno 1 + 2 + ... + n. Pošto se cela tabla sastoji od n (n + 1) polja, dobijamo
2 (1 + 2 + … + n) = n(n + 1),
odakle slijedi dobro poznata formula za zbir aritmetičke progresije:
1 + 2 + … + n = n(n + 1)/2.
Sada dokažemo sljedeću formulu:
8(1 + 2 + ... + n) + 1 = (2n + 1)².
Da biste to učinili, uzmite ploču (2n + 1) × (2n + 1) i obojite određeni broj njenih polja crnom bojom, kao što je prikazano na sl. 9, 6 (za slučaj n = 5). Očigledno, svaki crni dio sadrži (1 + 2 + ... + n) polja. Bez uzimanja u obzir centralnog polja, imamo četiri identična bijela i crna dijela. Tražena formula proizilazi iz činjenice da naša tabla sadrži (2n + 1)² polja i sastoji se od centralnog polja i osam identičnih delova (četiri bela i četiri crna - sl. 9b).
Prilikom razotkrivanja paradoksa, kao i upoznavanja sa „metodom šahovske ploče“, sama ploča se može sigurno zamijeniti listom kariranog papira ili stolom. Postoji ogroman broj problema sa takvim objektima, ali njihovo detaljno razmatranje bi nas previše udaljilo od šaha.
Na kraju poglavlja predstavljamo jedan stari dokaz na šahovskoj tabli... Pitagorine teoreme. Nacrtajte kvadrat na tabli, kao što je prikazano na sl. 10, a. Ploča je podijeljena na ovaj kvadrat i četiri podudarna pravokutna trougla. Na sl. 10, 6 vidimo ista četiri trougla, kao i dva kvadrata. Dakle, trouglovi u oba slučaja zauzimaju istu površinu. Shodno tome, preostali dijelovi ploče bez trokuta zauzimaju istu površinu, na sl. 10,a - jedan kvadrat, a na sl. 10b - dva. Pošto je veliki kvadrat izgrađen na hipotenuzi pravouglog trougla, a mali kvadrati na njegovim nogavicama, onda su "pitagorine pantalone jednake u svim pravcima"!
Naravno, strogo govoreći, naše rezonovanje ne dokazuje Pitagorinu teoremu (proučavao se samo određeni slučaj), već je samo ilustruje. Ali takav dokaz ide bez upotrebe šahovske ploče - za bilo koji pravokutni trokut možete odabrati kvadrat koji se lomi na sličan način.
Upravo je ovo rješenje dato u knjizi T. Saatija "Metode cjelobrojne optimizacije i srodni ekstremni problemi" (M., "Mir", 1973).
S. Golomb. Polyomino. M., Mir, 1974.
Dokazao je to A. Soifer u članku "Šokerske daske i polimipo" ("Kvant", 1972, br. 11); tamo je dat i niz novih poliomino problema.
E. Ignatiev. U domenu domišljatosti, ili aritmetike za svakoga. Book. 1 - 3. M. - Str., Gosizdat, 1923.
6. U kutiji je 235 šibica. Dva igrača ih vode redom. U jednom potezu možete uzeti od 1 do 6 šibica. Igrač pobjeđuje
uzimajući posljednju utakmicu. Ko pobjeđuje kada se igra ispravno?
62
7. Ugaoni kvadrat je izrezan iz ploče 8 × 8. Da li je moguće položiti ploču u pravougaonike 1×3?
8. Od 30 mečeva, dva igrača uzimaju po svom nahođenju od 1
do 6 utakmica. Pobjeđuje onaj koji uzme posljednju utakmicu.
9. Tri su gomile kamenja. Stanje je trojka brojeva
(x
1
, x
2
, x
3
), gdje je x i
- broj kamenja u i-toj gomili. Pomicanje je operacija prijenosa s gomile na hrpu broja kamenova jednakog broju kamenja u hrpi gdje se vrši prijenos. Iz početnog stanja (11, 7, 6) dobiti stanje (8, 8, 8).
10. Podijelite krug na maksimalan broj dijelova koristeći četiri ravne linije.
11. Odrežite grčki križ sa dvije ravne linije tako da
da se od dobijenih delova formira pravougaonik čija je jedna strana duplo veća od druge.
12. U 9 je zaliha tečnosti i praznih posuda od 12 litara
i 5 l. Potrebno je izmjeriti tačno 6 litara. Koliko se litara može izmjeriti takvim posudama iz rezerve od 12 litara?
13. Odrediti broj nizova dužine n iz (0, 1, 2),
u kojoj ne postoje dvije uzastopne jedinice.
14. Da li je moguće pokriti kvadrat 10 × 10 figurama oblika
15. Da li je moguće pokriti kvadrat 10 × 10 figurama oblika
63
16. Da li je moguće pokriti kvadrat 8×8 sa izrezanom ugaonom ćelijom sa figurama oblika
17. Da li je moguće obložiti figurama oblika 8 × 8 šahovsku tablu u kojoj je izrezan kvadrat:
18. Da li je moguće postaviti šahovsku tablu sa izrezbarenim kutnim kavezom sa komadima forme
19. Da li je moguće izvršiti prelazak četiri para vitezova-štionika uz pomoć čamca za dva čovjeka, ako štitonoša ne može biti na istoj obali sa tuđim vitezom(ima) u odsustvu svog gospodara?
20. Razviti algoritam za pronalaženje dva najmanja broja u neuređenom nizu od n brojeva.
21. Od 27 mečeva koji leže na stolu, dva igrača naizmjenično uzimaju najmanje jednu i ne više od četiri meča. Pobjednik je onaj koji će na kraju igre imati paran broj mečeva. Razviti algoritam za igru prvog igrača.
64
22. Dva učesnika igre naizmjenično zovu broj od 1 do 10.
Pozivajući broj, igrač ga dodaje već postojećem zbroju brojeva (pozivajući prvi broj, igrač ga dodaje na nulu). Igrač koji postigne 100 pobjeđuje.
Razviti algoritam za igru prvog igrača.
23. Pronađite za minimalni broj pitanja (mogući odgovori:
"da", "ne") skriveni 5-cifreni broj, ako je zbir prve tri cifre 17.
24. Pronađite za minimalni broj pitanja (mogući odgovori:
"da", "ne") skriveni 4-cifreni broj, ako je zbir druge i četvrte cifre 7.
25. Na koliko načina se može zamijeniti 100 rubalja? kovanice u
5, 10, 20 i 50 rubalja?
26. Rekurzivno izračunajte broj šestocifrenih brojeva čiji je zbir prve četiri cifre 26, a zbir posljednje dvije 14.
27. Rekurzivno izračunaj broj particija broja 37 sa pet članova, od kojih prvi ne prelazi 7, a drugi
- 5, a treći i četvrti uzimaju vrijednosti iz skupa
{5, 6, 7, 8}.
28. Rekurzivno izračunaj broj sedmocifrenih brojeva čiji je zbir prva četiri broja 21, a zbir posljednjih pet 19.
29. Rekurzivno izračunaj broj particija broja 27 sa četiri člana, od kojih prvi ne prelazi 7,
drugi je 8, a treći i četvrti uzimaju vrijednosti iz skupa (3, 5, 7).
30. Izračunaj rekurzivno broj petocifrenih brojeva čije prve tri cifre imaju zbir 21, a posljednje tri cifre 12.
65
31. Rekurzivno izračunaj broj sedmocifrenih brojeva u kojima je zbir prve i treće cifre 12, a zbir preostalih pet 19.
32. Izračunajte rekurzivno
(2n − 2)(2n − 4) × . . . ×2
(n + 1)(n + 3) × . . . × (n + 2n − 1)
a n−5
b
−(n+3)
33. Rekurzivno izračunaj broj sedmocifrenih brojeva čiji je zbir prve četiri cifre 17, a zbir posljednje tri 16.
34. Izračunaj rekurzivno broj particija broja 17 po četiri člana, od kojih prvi ne prelazi 4, drugi - 8, a treći i četvrti uzimaju vrijednosti (3, 4, 8).
35. Rekurzivno izračunaj broj sedmocifrenih brojeva čiji je zbir kvadrata prva četiri broja 17, a zbir kvadrata posljednja dva 16.
36. Rekurzivno izračunaj broj particija broja 25 sa četiri člana, od kojih prvi ne prelazi 8,
drugi je 3, a treći i četvrti uzimaju vrijednosti iz skupa (2, 5, 9).
37. Rekurzivno izračunajte broj N topova na tabli
N × N tako da su topovi simetrični u odnosu na obje dijagonale i da se međusobno ne napadaju.
38. Rekurzivno izračunajte broj binarnih sekvenci od n elemenata u kojima nedostaju dva susjedna.
39. Zadana je rešetka N × M:
66
M
N
A
B
Izračunajte rekurzivno broj putanja od A do B. Putanja je niz kretanja duž mreže koja vodi slijeva na desno i odozdo prema vrhu.
40. Dati su brojevi a
1
, . . . , a n
određenim redosledom. Za izračunavanje proizvoda a
1
·. . a n
uz održavanje redoslijeda faktora, postoji mnogo načina za postavljanje zagrada između faktora. Izračunajte rekurzivno broj načina za postavljanje zagrada.
41. Rekurzivno izračunajte broj osmocifrenih brojeva čiji je zbir prvih pet cifara 29, a zbir posljednje tri cifre 21.
67
3
. metode analize algoritama
3.1. Algoritamske klase
U prethodnim poglavljima razmatrali smo različite pristupe koji se mogu koristiti u konstrukciji algoritama. Da bi se pronašlo rješenje, analizirala efikasnost ovog rješenja, mogu se iznijeti različite pretpostavke, koristiti već poznati drugi algoritmi, preformulisati stanje problema itd. Možete potražiti neke slične probleme sa poznatim rješenjem i koristiti ovo rješenje da pronađete algoritam za traženi problem.
Međutim, postoji mnogo konkretnih problema za koje su pronađena rješenja. Ima još više zadataka neriješenih ili riješenih uz neka ograničenja i uvjete. Traženje sličnih problema među čitavim skupom problema, vrednovanje postojećih rješenja prema stepenu njihove "podobnosti" može biti težak, dugotrajan i ne uvijek rješiv problem. Bilo bi korisnije i produktivnije pokušati definirati klase problema koje objedinjuje zajednički problem, zajedničke metode i pristupi rješavanju, a zatim potražiti klasu kojoj se može pripisati naš konkretni problem koji treba riješiti. Naravno, ovakvih časova ne bi trebalo biti previše, ali s druge strane, ne bi trebalo da ih bude premalo, tako da svaki novi zadatak definirajte vlastitu, novu klasu, za koju je malo vjerovatno da će se koristiti za rješavanje drugih problema.
Kao primjer problema koji pripada određenoj klasi, razmotrite dobro poznati problem identifikacije krivotvorenog novčića.
Zadatak 3.1 (problem o falsifikovani novčić). ima n novčića,
među kojima može biti i jedan lažnjak. Krivotvoreni novčić se razlikuje od ostalih po težini, a na raspolaganju imamo vagu sa dvije čaše. Potrebno je utvrditi krivotvoreni novčić za minimalni broj vaganja ili utvrditi,
da nema falsifikovanih kovanica.
68
Rješenje. Problem krivotvorenog novčića riješen je u odl. 2.2,
ali tada se znalo da je krivotvoreni novčić nužno lakši. Pokušajmo sada riješiti ovaj problem za opštiji slučaj. Bilo kakvo rješenje ovog problema (ne nužno optimalno)
može se tumačiti kao niz vaganja. Međutim, jasno je da izbor kovanica za vaganje u bilo kojem koraku ovisi o tome koji su novčići korišteni i rezultatima vaganja u prethodnim koracima. Slijed vaganja ćemo prikazati na sljedeći način. Novčiće ćemo prenumerisati i definirati ih kao skup S = (1, 2, . . . , n). Skupovi brojeva kovanica izmjerenih na lijevoj i desnoj posudi vage mogu se označiti sa S
L
i S
R
respektivno. Jasno je da ponderisanje ima smisla samo ako su kardinaliteti skupova S
L
i S
R
utakmica, tj. Svaka vaga ima isti broj novčića. Vaganje će biti označeno znakom ":", a zatim svako vaganje
(S
L
) : (S
R
) postoje tri moguća ishoda. Puno novčića
S
L
može biti lakši, teži ili iste težine kao set S
R
. Tada ćemo ove rezultate ponderiranja označiti kao
"" ili "=", respektivno. Primjer vaganja za četiri novčića prikazan je na sl. 3.1. Ovali predstavljaju vaganja, kvadrati predstavljaju rezultate, ukazujući na broj krivotvorenog novčića i da li je lakši ili teži od ostalih.
Slučaj bez krivotvorenog novčića označen je kao "0", precrtani kvadrati odgovaraju slučajevima koji se ne mogu dogoditi.
Procijenićemo maksimalan broj vaganja koji je potreban za rješavanje problema, tj. najgorem slučaju. Kao što se može vidjeti sa sl. 3.1, problem se rješava u 3 vaganja u najgorem slučaju. Imajte na umu da čak iu najboljem slučaju trebamo najmanje 2
vaganje. Može li se postići bolji rezultat?
Na sl. 3.1 predstavlja još jedno rješenje za problem vaganja četiri novčića. U prvom koraku vagamo ne par novčića, već sve novčiće, dijeleći ih u dva seta. Kao rezultat toga, postigli smo da je u najboljem slučaju potrebno samo jedno vaganje,
međutim, u najgorem slučaju, broj vaganja je opet 3.
69
(1) : (2)
(1) : (3)
(1) : (4)
0 4 T
4 L
3 T
3 L
(1) : (4)
2 T
1 L
(1) : (4)
2 L
1 T
=
=
=
>
>
>
>
>
=
=
Rice. 3.1. Rješavanje problema krivotvorenog novčića
Imajte na umu da, za razliku od prve opcije vaganja,
prikazano na sl. 3.1, u drugoj verziji, ne samo da smo definirali šemu vaganja, već smo uveli i novi koncept kandidata za krivotvorene novčiće. Zaista, razmotrite rezultat prvog vaganja, (1, 2) : (3, 4). Neka (1, 2) L
= (1, 2) i S
R
= (3, 4). Onda
S
L
R
. Iz ovog rezultata nije moguće suditi da li je krivotvoreni novčić lakši ili teži od svih ostalih,
i u kom je kompletu. Međutim, može se pretpostaviti
(i još preciznije - može se tvrditi) da ako lažni novčić pripada skupu S
L
, tada je krivotvoreni novčić lakši od ostalih, takav skup označavamo slovom L. U našem slučaju, ako su kovanice s brojevima 1 ili 2 krivotvorene, onda su lakši od pravih. Ako je krivotvoreni novčić sa brojevima 3 ili
4, onda su teži od pravih, odgovarajući skup ćemo označiti slovom T. Na sl. 3.2 laki i teški falsifikovani kandidati označeni su oznakama na ivicama drveta.
Očigledno, na pitanje o optimalnom broju vaganja može se odgovoriti nastavljajući s sortiranjem mogućih shema za odabir kovanica. Budući da je broj novčića konačan, prije ili kasnije takvo nabrajanje može biti završeno. Za sada, hajde da se zadržimo na dva dobijena rešenja i pokušamo da analiziramo šta su ona dala
70
(1.2) L
(3.4) T
(1.2) T
(3.4) L
(1,2) : (3,4)
(3) : (4)
4 T
3 T
(1) : (2)
1 L
=
=
>
>
>
=
0 2 L
(3) : (4)
3 L
4 L
(1) : (2)
2 T
=
>
>
=
1 T
Rice. 3.2. Još jedno rješenje problema krivotvorenog novčića nam je sa stanovišta općeg pristupa rješavanju problema.
Kao što je poznato, svaka strategija vaganja novčića može se opisati korištenjem ternarnog ili ternarnog stabla. Drugim riječima, problem koji se razmatra pripada klasi problema,
opisano ternarnim stablima. Takva klasifikacija problema omogućava analizu ne svakog konkretnog rješenja, već svih rješenja općenito, na osnovu poznatih svojstava stabala.
Dakle, iteracija je gotova mogući načini ponderisanje je zapravo pretraga kroz različita ternarna stabla, kojih, naravno, ima eksponencijalno mnogo. S druge strane, pokušajmo da utvrdimo šta je općenito moguće postići rješavanjem datog problema, koristeći njegovu pripadnost ovoj klasi.
Od sl. 3.1 i 3.2, može se vidjeti da, oslikavajući redoslijed vaganja pomoću drveta, svako vaganje pripisujemo vrhu drveta koji nije list (prikazano pomoću ovala), dok ishodi, uključujući i one nemoguće,
odgovara lišću drveta (prikazano kvadratima). Svi čvorovi stabla mogu se poredati po nivoima,
71
AT
a
=
=
>
AT
a
I
I
I
=
>
AT
a
I
I
I
=
>
AT
a
I
I
I
=
>
AT
a
I
I
I
=
>
AT
a
=
>
AT
a
=
>
AT
a
>
To
AT
L
At
0
At
1
At
l
-
1
At
l
……
………………
………
…
…
……
…
…
…
…
…
……
……
…
…
G
a =
l
Rice.
3.3.
T
proljetno drvo težine
72
one. po njihovoj udaljenosti od korena drveta. Broj nivoa jednak je broju ivica koje moraju proći od korijena da bi došli do vrha. dati nivo(Sl. 3.3). Ako je dubina stabla nivo lista koji je najudaljeniji od korijena, tada je ova vrijednost jednaka broju pondera u najgorem slučaju.
Koliko je mogućih ishoda u našem problemu? Svaki od n novčića može se ispostaviti kao lažni laki ili lažni teški novčić, a možda uopće ne postoji lažni novčić.
Dakle, imamo 2n + 1 ishoda. To znači da u stablu
koji odgovara shemi vaganja, mora biti najmanje
2n + 1 listova. Ternarno stablo dubine l sadrži najviše,
od 3
ja odlazim. Iz ovoga možemo procijeniti minimalnu moguću dubinu stabla
3
l
≥ 2n + 1,
i stoga
l ≥ log
3
(2n + 1).
(3.1)
Dakle, za n = 4, minimalni mogući broj vaganja je veći ili jednak 2. Ovdje ne mislimo na minimalni broj vaganja za ovu šemu - kao na sl. 3.2, a postoje slučajevi kada je rješenje problema pronađeno već nakon prvog vaganja - procjenjujemo najgoru opciju, tj. maksimalni broj pondera za datu shemu, drugim riječima, tražimo minimum između maksimalnih dubina svih stabala sa najmanje 2n + 1 list.
Međutim, može se pokazati da ne postoji metoda ponderisanja koja bi dala jednakost u procjeni (3.1).
TEOREMA 3.1
Broj vaganja u najgorem slučaju za problem krivotvorenog novčića procjenjuje se kao l > log
3
(2n + 1).
Dokaz. Kao što je već spomenuto, za n novčića postoji 2n + 1 mogući ishod. Svako vaganje može imati tri moguća rezultata, a svaki rezultat ima svoj
73
šema daljih vaganja. Istovremeno, shema ima svoj broj mogućih ishoda, uzimajući u obzir rezultat posljednjeg vaganja. Neka pri prvom vaganju |S
L
| = |S
R
| = k, tj.
k novčića se koristi na jednoj vagi i k novčića na drugoj,
gdje je k ≤ n/2 . Ako je u isto vrijeme S
L
R
, zatim kovanice iz S
L
proglašavamo kandidate za lake krivotvorene kovanice, te kovanice iz S
R
- Kandidati za teške krivotvorene kovanice. Na ovaj način,
sa rezultatom prvog vaganja moguće je 2k ishoda.
Slično, za S
L
>S
R
Moguća su 2k drugih ishoda. Stoga, za S
L
=S
R
mogućih je preostalih 2n + 1 − 4k ishoda.
Ako je jednakost u (3.1), to znači da je ternarno stablo kompletno i da su svi njegovi listovi na l-tom nivou.
Ali za to je potrebno da se nakon svakog vaganja mogući ishodi ravnomjerno raspodijele na tri grane i jednakost
2k = 2n + 1 − 4k,
što je nemoguće jer je 2k uvijek paran broj, i
2n + 1 − 4k je uvijek neparan.
Važna ideja korištena je u dokazu teoreme 3.1:
Da bi drvo ponderiranja bilo optimalno, ili barem što bliže optimalnom, potrebno je da se rezultati ravnomjerno rasporede na sve rezultate svakog vaganja.
Tako smo dobili procjenu za najgori broj vaganja u problemu krivotvorenog novčića povezujući ovaj problem s klasom problema
opisano ternarnim stablima. Sada razmotrite malo izmijenjen problem.
Problem 3.2 (problem o krivotvorenom novčiću u prisustvu standarda). Postoji n kovanica, među kojima može biti jedan krivotvoreni, i još jedan novčić, za koji se pouzdano zna da je pravi. Potrebno je utvrditi krivotvoreni novčić u minimalnom broju vaganja ili utvrditi da nema krivotvorenih kovanica.
74
Rješenje. Ovaj problem se razlikuje od prethodnog po prisustvu dodatnog referentnog novčića, ali se ispostavilo da ovaj dodatni novčić omogućava konstruisanje optimalnih stabala težine za koje je zadovoljena jednakost u (3.1). Označiti sa n l
broj za koji vrijedi jednakost
3
l
= 2nl
+ 1.
(3.2)
Razmatrajući prethodni problem u teoremi 3.1, dobili smo: da bi jednakost (3.1) bila zadovoljena, drvo pondera mora biti potpuno. Stoga, ako je moguće izgraditi takvo optimalno stablo od l nivoa, onda će se specificirati shema l pondera za n l
kovanice. Imajte na umu da je tačna sljedeća relacija:
n l
= 3nl−1
+ 1.
(3.3)
Budući da za n
0
= 0 u (3.2) dobijamo jednakost, 3 0
= 2 0 + 1,
onda odavde koristeći (3.3) možemo dobiti n
1
= 1,n
2
=
4,n
3
= 13 itd. Rješenje (3.2) je niz
0, 1, 4, 13, 40, . . ..
Dakle, kada vrijedi jednakost (3.2), skup od n
l novčića je podijeljeno na tri jednaka dijela sa n l−1
kovanica i još je jedan novčić ostao. Razmotrimo različite situacije koje se mogu pojaviti tokom procesa vaganja.
Shema 1. Neka na početku vaganja imamo n i
kovanice, gdje je n i
pripada nizu (3.3) za neki i. Stavimo n i−1
kovanice, gdje n
i
= 3n i−1
+ 1,
zatim dodajemo referentni novčić u lijevi dio vage, a jedan od preostalih n i−1
+ 1 novčić. Ponderisane skupove, kao i ranije, označimo sa S
L
i S
R
Sada neka kao rezultat vaganja S
L
=S
R
. Budući da je referentni novčić učestvovao u vaganju, očigledno je da se lažni novčić, ako ga ima, nalazi među neupotrijebljenim n
i−1
novčića, a problem se svodi na problem sa n i−1
kovanice. Gde
75
Kao rezultat ponderisanja, još uvijek imamo 2n i−1 mogućih
+ 1 =
3
i−1
ishodi. Sada neka S
L
R
. To znači da je krivotvoreni novčić ili u kompletu S
L
a istovremeno je lakši od ostalih, odnosno u skupu S
R
i tada je teži od ostalih.
Štaviše, postoji n i−1
sumnjivi laki novčići i n i−1
+ 1 sumnjivo težak i zajedno ovo opet daje 2n i−1
+ 1 = 3
i−1
mogući ishodi.
Konačno, neka S
L
>S
R
. Tada imamo n i−1
kandidati za teške novčiće i n i−1
+1 kandidata za pluća i ukupno 2n i−1
+1 =
3
i−1
ishodi. Dakle, sa takvom šemom prvog vaganja, zapravo dobijamo to 3
i početni rezultati su ravnomjerno raspoređeni prema rezultatima vaganja. Da biste utvrdili da li je moguće postaviti šemu vaganja tako da se nakon svakog vaganja rezultati podijele na jednak broj dijelova, razmotrite rezultate vaganja. Očigledno, za S
L
=S
R
dolazimo do istog problema, samo sa manjom dimenzijom, i uvek možemo ponovo izvršiti ponderisanje prema šemi 1, ali sa manjom vrednošću i.
Šema 2. Neka sada S
L
R
. U ovom slučaju strategiju ponderiranja definiramo na sljedeći način. Početni podatak je da u nekom koraku i u nizu pondera imamo 3
i
= 2n i
+ 1 novčić, među kojima n i
lakih lažnih kandidata i n i
+ 1 kandidat za teške, dok je broj n i
je broj oblika (3.3)
n i
= 3n i−1
+ 1.
Stavite na svaku skalu tavicu n i−1
laki kandidati i n
i−1
+1 težak. Pošto postoji samo 2n i
+1 = 2(3n i−1
+1)+1 = 6n i−1
+3
kovanice i vagati
2n i−1
+ 2n i−1
+ 2 = 4n i−1
+ 2
kovanica, onda još ima 2n i−1
+ 1 novčića, među kojima n i−1
+ 1
pluća i n i−1
težak. Budući da je na obje vage isti broj lakih i teških kovanica, onda ako vaga nije uravnotežena,
ovo daje n i−1
kandidati za lake kovanice (iz posude koja se pokazala lakšom) i n i−1
+ 1 kandidat za teške (iz posude koja se ispostavila
76
teže). Ovo nas dovodi do originalnih podataka iste sheme
(šeme 2), ali za 3
i−1
= 2n i−1
+ 1 novčić. Ako je vaga izbalansirana, to znači da moramo tražiti lažni novčić među neizvaganim n i−1
+ 1 pluća i n i−1
teške kovanice, što odgovara šemi 3. Očigledno, 2n i−1
+1 ishoda, tj. opet je skup svih mogućih ishoda podijeljen na tri jednaka dijela.
Šema 3. Neka sada S
L
>S
R
. U ovom slučaju imamo 3
i
=
2n i
+ 1 novčić, među kojima n i
+ 1 laki lažni kandidati, i n i
kandidati teške kategorije. Svi argumenti su slični šemi 2, s tom razlikom što prilikom vaganja treba staviti n i−1
+ 1 laki kandidati, i n i−1
težak. Ako vaga nije izbalansirana, to nam opet daje uzorak 3 za 3
i−1
novčića, inače dobijamo uslove za vaganje koji odgovaraju šemi 2. Opet, u svim slučajevima, skup mogućih ishoda se deli na tri jednaka dela od 2n i−1
+ 1.
Dakle, imamo tri puta
1 2
3
=
>
=
=
Rice. 3.4. Prijelazi između shema ponderiranja u problemu krivotvorenog novčića osobnog stanja opisanog iznad i pravila ponderiranja za svaku državu. Ovisno o rezultatu vaganja, prelazimo u drugo stanje (ili ostajemo u istom stanju), ali za manji broj novčića. Prilikom svakog vaganja, broj mogućih ishoda se ravnomjerno raspoređuje prema rezultatima vaganja. Šema prijelaza između stanja prikazana je na sl. 3.4. Primjer vaganja za 27 novčića prikazan je na sl. 3.5.
77
Zadatak 1: Može li se kvadrat veličine 5 × 5 izrezati na pravokutnike 1 × 2 (domino). Zadatak 2: Nasuprotni uglovi su izrezani iz šahovske ploče 8×8. Može li se ostatak izrezati na pravokutnike 1 × 2 (domino)? Rješenje: br. Svaka domino zauzima jedno crno i jedno bijelo polje, a na ploči se nalazi različit broj crnih i bijelih polja bez uglova. Zadatak 3: Iz suprotnih uglova ploče 10 × 10 izrezana su dva kvadrata 3 × 3. Može li se ostatak izrezati u domine? Zadatak 4: Smislite povezanu figuru na šahovskoj tabli, u kojoj se nalazi jednak broj crnih i bijelih ćelija, ali koja se ne može podijeliti na domine. Zadatak 5: Da li je moguće izrezati kvadrat 10 × 10 na 25 komada? Zadatak 6:Rješenje: Obojite ploču po uzorku na šahovnicu. Postojaće paran broj crnih ćelija, a jedna ili tri će pasti u svaku figuru. Zadatak 7: Da li je moguće izrezati kvadrat 10 × 10 na 25 komada? Rješenje:
Obojite ploču u četiri boje (vidi sliku). Svaka figura zauzima jednu ćeliju svake boje, a ćelije prve i druge boje imaju različit broj.
Smjer: Obojite ploču u tri boje.
Zadatak 12: Koliki je maksimalni broj šipki 1 × 1 × 4 koji se mogu izrezati iz kocke 6 × 6 × 6? Zadatak 13: Pravougaonik je podijeljen na figure i . Jedan od izgubljenih, ali zamijenjen sa. Dokažite da novi skup ne može pokriti originalni pravougaonik. Zadatak 14: Može li se kvadrat veličine 16 × 16 podijeliti na 64 pravokutnika 1 × 4, od kojih će 31 biti okomito, a preostala 33 vodoravna? Rješenje: Obojite svaku četvrtu vertikalu. Zadatak 15: Za koje n se kvadrat n × n može podijeliti na a) ;b)? Rješenje: Za n deljivo sa četiri.
Zadatak 16: Pravougaonik m × k podijeljen je na 1 × n pravokutnika. Dokažite da je m deljivo sa n ili da je k deljivo sa n.c) za bilo koji n. Rješenje:
Boja u n boja.
Zadatak 17: Dokažite da se pravougaonik m × n može podijeliti na a × b pravougaonike ako i samo ako su ispunjeni sljedeći uvjeti:1) m i n su predstavljeni kao ka + lb (k i l su nenegativni cijeli brojevi)
2) m i n su djeljivi sa a.
3) m ili n je deljivo sa b.
Zadatak 18: Pravougaonik m × n naziva se jak ako se može podijeliti na domine na način da bilo koji rez pravokutnika siječe barem jednu domino. dokazati da:a) 2 × n pravougaonik - lomljiv
b) 3 × n pravougaonik - lomljiv
c) 4 × n pravougaonik - lomljiv
d) Pravougaonici 5×6 i 6×8 - jaki
e) ako je m × n pravougaonik jak, tada je i m × (n + 2) pravougaonik jak.
f) * 6×6 pravougaonik - lomljiv
g) Koji pravougaonici su jaki, a koji nisu? Rješenje: f) Savjet: Svaka linija u kvadratu 6×6 prelazi paran broj domina.
g) Svi m × n pravokutnici gdje je mn paran, m,n ≥ 5, osim 6 × 6.
Zadatak 19:Ugao je figura forme.
a) Može li se pravougaonik 5 × 9 razbiti na uglove?
b) Dokaži da se pravougaonik sa stranicama većim od 100 i površinom deljivim sa 3 može razbiti na uglove.
c) Koji se pravougaonici mogu podijeliti na uglove, a koji ne?
Zadatak 20:Može li se ploča 2 n × 2 n bez ugla kvadrata podijeliti na uglove? Rješenje: Da, možeš. Pregrada je konstruisana indukcijom.
Zadatak 21: Za koji n se tabla (2n + 1) × (2n + 1) bez kutne ćelije može podijeliti na domine, među kojima su podjednako vertikalne i horizontalne? Rješenje: Za čak n.
