Logična naloga za postavljanje domin na šahovnico. Matematične olimpijade in olimpiadni problemi
Dana je šahovnica 8×8, iz katere sta izrezana dva diagonalno nasprotna vogala, in 31 domin; vsaka domina lahko pokrije dve polji na plošči. Ali je mogoče s kostmi tlakovati celotno ploščo? Svoj odgovor utemelji.
rešitev
Na prvi pogled se zdi, da je to mogoče. Tabla je 8×8, celic je torej 64, izvzamemo dve, kar pomeni, da jih ostane 62. Zdi se, da bi moralo stati 31 kosti, kajne?
Ko skušamo zložiti domine v prvo vrsto, imamo na razpolago samo 7 polj, ena kost gre v drugo vrsto. Nato v drugo vrsto postavimo domine, spet gre ena ploščica v tretjo vrsto.
V vsaki vrsti bo vedno ena kost, ki jo je treba premakniti v naslednjo vrstico, ne glede na to, koliko postavitev poskusimo, nikoli ne bomo mogli položiti vseh kosti.
Šahovnica je razdeljena na 32 črnih in 32 belih celic. Če odstranimo nasprotna vogala (upoštevajte, da so te celice iste barve), nam ostane 30 celic ene barve in 32 celic druge barve. Recimo, da imamo zdaj 30 črnih in 32 belih kvadratov.
Vsaka kocka, ki jo bomo postavili na tablo, bo zasedla eno črno in eno belo celico. Zato bo 31 domin zasedlo 31 belih in 31 črnih celic. Toda na naši tabli je le 30 črnih in 32 belih celic. Zato je kosti nemogoče razgraditi.
Analiza je povzeta po prevodu knjige G. Luckman McDowell in je zgolj informativne narave.
Če vam je bila knjiga všeč, vam priporočamo nakup.
6. V škatlici je 235 vžigalic. Izmenoma jih vzameta dva igralca. V eni potezi lahko vzamete od 1 do 6 vžigalic. Igralec zmaga
vzeti zadnjo tekmo. Kdo zmaga ob pravilni igri?
62
7. Iz plošče 8 × 8 je izrezan kotni kvadrat. Ali je mogoče ploščo položiti v pravokotnike 1×3?
8. Od 30 tekem dva igralca po lastni presoji vzameta od 1
do 6 tekem. Zmaga tisti, ki vzame zadnjo vžigalico.
9. Tam so trije kupi kamenja. Država je trojček števil
(x
1
, x
2
, x
3
), kjer je x i
- število kamnov v i-tem kupu. Premik je operacija prenašanja s kupa na kup števila kamnov, ki je enako številu kamnov v kupu, kjer se izvaja prenos. Iz začetnega stanja (11, 7, 6) dobite stanje (8, 8, 8).
10. Krog razdelite na največje število delov s štirimi ravnimi črtami.
11. Izrežite grški križ z dvema ravnima črtama tako, da
da iz nastalih delov oblikujemo pravokotnik, katerega ena stran je dvakrat večja od druge.
12. V 9 je 12-litrska zaloga tekočine in prazne posode
in 5 l. Potrebno je izmeriti natančno 6 litrov. Koliko litrov lahko izmerimo s takimi posodami iz rezerve 12 litrov?
13. Določite število zaporedij dolžine n iz (0, 1, 2),
v katerem ni dveh zaporednih enot.
14. Ali je mogoče kvadrat 10 × 10 prekriti s figurami oblike?
15. Ali je mogoče kvadrat 10 × 10 prekriti s figurami oblike?
63
16. Ali je mogoče kvadrat 8×8 z izrezano kotno celico prekriti s figurami oblike
17. Ali je mogoče prekriti s figurami v obliki šahovnice 8 × 8, v kateri je izrezan kvadrat:
18. Ali je mogoče položiti šahovnico z izrezljano kotno kletko s kosi oblike
19. Ali je možno opraviti prečkanje štirih parov vitezov s pomočjo dvočlanskega čolna, če štitonoša ne more biti na isti obali s tujim vitezom v odsotnosti poveljnika?
20. Razvijte algoritem za iskanje dveh najmanjših števil v neurejenem zaporedju n števil.
21. Od 27 vžigalic, ki ležijo na mizi, dva igralca izmenično vzameta vsaj eno in ne več kot štiri vžigalice. Zmagovalec je tisti, ki bo imel na koncu igre sodo število tekem. Razvijte algoritem za igro prvega igralca.
64
22. Dva udeleženca v igri izmenično kličeta številko od 1 do 10.
Ko pokliče številko, jo igralec prišteje k že obstoječi vsoti števil (če pokliče prvo številko, jo igralec doda k ničli). Zmaga igralec, ki doseže 100.
Razvijte algoritem za igro prvega igralca.
23. Poiščite najmanjše število vprašanj (možni odgovori:
"da", "ne") skrito 5-mestno število, če je vsota prvih treh števk 17.
24. Poiščite najmanjše število vprašanj (možni odgovori:
"da", "ne") skrito 4-mestno število, če je vsota druge in četrte števke 7.
25. Na koliko načinov je mogoče zamenjati 100 rubljev? kovanci v
5, 10, 20 in 50 rubljev?
26. Rekurzivno izračunaj število šestmestnih števil, katerih vsota prvih štirih števk je 26, vsota zadnjih dveh pa 14.
27. Rekurzivno izračunajte število razdelkov števila 37 s petimi členi, od katerih prvi ne presega 7, drugi
- 5, tretji in četrti pa vzameta vrednosti iz niza
{5, 6, 7, 8}.
28. Rekurzivno izračunaj število sedemmestnih števil, katerih vsota prvih štirih števil je 21, vsota zadnjih petih pa 19.
29. Rekurzivno izračunajte število razdelkov števila 27 na štiri člene, od katerih prvi ne presega 7,
drugi je 8, tretji in četrti pa vzameta vrednosti iz niza (3, 5, 7).
30. Rekurzivno izračunaj število petmestnih števil, katerih seštevek prvih treh števk je 21, zadnje tri pa 12.
65
31. Rekurzivno izračunaj število sedemmestnih števil, pri katerih je vsota prve in tretje števke 12, vsota preostalih pet pa 19.
32. Računajte rekurzivno
(2n − 2)(2n − 4) × . . . ×2
(n + 1)(n + 3) × . . . × (n + 2n − 1)
a n−5
b
−(n+3)
33. Rekurzivno izračunaj število sedemmestnih števil, katerih vsota prvih štirih števk je 17, vsota zadnjih treh pa 16.
34. Rekurzivno izračunajte število particij števila 17 s štirimi izrazi, od katerih prvi ne presega 4, drugi - 8, tretji in četrti pa sprejmejo vrednosti (3, 4, 8).
35. Rekurzivno izračunaj število sedemmestnih števil, katerih vsota kvadratov prvih štirih števil je 17, vsota kvadratov zadnjih dveh pa 16.
36. Rekurzivno izračunajte število razdelkov števila 25 na štiri člene, od katerih prvi ne presega 8,
drugi je 3, tretji in četrti pa vzameta vrednosti iz niza (2, 5, 9).
37. Rekurzivno izračunajte število N postavitev top na plošči
N × N tako, da so topovi simetrični glede na obe diagonali in se ne napadajo.
38. Rekurzivno izračunajte število binarnih zaporedij n elementov, v katerih manjkata dva sosednja.
39. Podana je mreža N × M:
66
M
n
A
B
Rekurzivno izračunajte število poti od A do B. Pot je zaporedje potez vzdolž mreže, ki vodi od leve proti desni in od spodaj navzgor.
40. Podana so števila a
1
, . . . , a n
v določenem vrstnem redu. Za izračun produkta a
1
·. . .a n
ob ohranjanju vrstnega reda dejavnikov obstaja veliko načinov za postavljanje oklepajev med dejavnike. Rekurzivno izračunajte število načinov za oklepaje.
41. Rekurzivno izračunaj število 8-mestnih števil, katerih vsota prvih petih števk je 29 in vsota zadnjih treh števk 21.
67
3
. metode analize algoritmov
3.1. Razredi algoritmov
V prejšnjih razdelkih smo obravnavali različne pristope, ki jih lahko uporabimo pri izdelavi algoritmov. Za iskanje rešitve, za analizo učinkovitosti te rešitve je mogoče postaviti različne predpostavke, uporabiti že znane druge algoritme, preoblikovati pogoj problema itd. Lahko poiščete nekaj podobnih težav z znano rešitvijo in uporabite to rešitev za iskanje algoritma za zahtevano težavo.
Vendar pa obstaja veliko posebnih problemov, za katere so bile najdene rešitve. Še več je nerešenih ali rešenih nalog z nekaterimi omejitvami in pogoji. Iskanje podobnih problemov med celotnim nizom problemov, ocenjevanje obstoječih rešitev glede na njihovo stopnjo "primernosti" je lahko težaven, dolgotrajen in ne vedno rešljiv problem. Bolj koristno in produktivno bi bilo poskusiti definirati razrede problemov, ki jih združuje skupni problem, skupne metode in pristopi k reševanju, nato pa poiskati razred, ki mu je mogoče pripisati naš določen problem, ki ga je treba rešiti. Seveda takih razredov ne sme biti preveč, po drugi strani pa jih ne sme biti premalo, da bi vsak nova naloga definirajte svoj lasten, nov razred, za katerega je malo verjetno, da ga boste uporabili za reševanje drugih problemov.
Kot primer težave, ki pripada določenemu razredu, razmislite o dobro znani težavi prepoznavanja ponarejenega kovanca.
Naloga 3.1 (problem o ponarejen kovanec). Obstaja n kovancev,
med katerimi je lahko en ponaredek. Ponarejeni kovanec se od preostalih razlikuje po teži, na razpolago pa imamo tehtnico z dvema skodelicama. Ponarejen kovanec je treba določiti z minimalnim številom tehtanj ali ugotoviti,
da ni ponarejenih kovancev.
68
rešitev. Težava s ponarejenimi kovanci je bila rešena v odd. 2.2,
takrat pa se je vedelo, da je ponarejen kovanec nujno lažji. Zdaj pa poskusimo rešiti ta problem za bolj splošen primer. Kakršna koli rešitev tega problema (ne nujno optimalna)
lahko razlagamo kot zaporedje tehtanj. Jasno pa je, da je izbira kovancev za tehtanje v katerem koli koraku odvisna od uporabljenih kovancev in rezultatov tehtanja v prejšnjih korakih. Zaporedje tehtanj bomo prikazali takole. Kovance preštevilčimo in definiramo kot množico S = (1, 2, . . . , n). Nize števil kovancev, stehtanih na levi in desni plošči tehtnice, lahko označimo s S
L
in S
R
oz. Jasno je, da je ponderiranje smiselno le, če so kardinalnosti množic S
L
in S
R
ujemanje, tj. Vsaka tehtnica ima enako število kovancev. Tehtanje bo označeno z znakom ":", nato vsako tehtanje
(S
L
) : (S
R
) možni so trije izidi. Veliko kovancev
S
L
je lahko lažji, težji ali enake teže kot komplet S
R
. Potem bomo te rezultate uteževanja označili kot
"" ali "=". Primer tehtanja štirih kovancev je prikazan na sl. 3.1. Ovali predstavljajo tehtanja, kvadrati pa rezultate, ki označujejo številko ponarejenega kovanca in ali je lažji ali težji od drugih.
Primer, da ni ponarejenega kovanca, je označen z "0", prečrtani kvadratki ustrezajo primerom, ki se ne morejo zgoditi.
Ocenili bomo največje število tehtanj, potrebnih za rešitev problema, tj. v najslabšem primeru. Kot je razvidno iz sl. 3.1 se problem v najslabšem primeru reši v 3 tehtanjih. Upoštevajte, da tudi v najboljšem primeru potrebujemo vsaj 2
tehtanje. Je mogoče doseči boljši rezultat?
Na sl. 3.1 predstavlja drugo rešitev problema tehtanja štirih kovancev. Na prvem koraku ne stehtamo nekaj kovancev, ampak vse kovance, ki jih razdelimo v dva niza. Posledično smo dosegli, da je v najboljšem primeru potrebno le eno tehtanje,
vendar je v najslabšem primeru število tehtanj spet 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
=
=
=
>
>
>
>
>
=
=
riž. 3.1. Reševanje problema ponarejenih kovancev
Upoštevajte, da je v nasprotju s prvo možnostjo tehtanja
prikazano na sl. 3.1, v drugi različici nismo le definirali sheme tehtanja, ampak smo uvedli tudi nov koncept kandidatov za ponarejene kovance. Dejansko upoštevajte rezultat prvega tehtanja, (1, 2) : (3, 4). Naj (1, 2) L
= (1, 2) in S
R
= (3, 4). Potem
S
L
R
. Iz tega rezultata ni mogoče presoditi, ali je ponarejeni kovanec lažji ali težji od vseh ostalih,
in v kakšnem kompletu je. Vendar pa je mogoče domnevati
(in še natančneje - lahko trdimo), da če ponarejeni kovanec pripada množici S
L
, potem je ponarejen kovanec lažji od ostalih, tak komplet označimo s črko L. V našem primeru, če so kovanci s številko 1 ali 2 ponarejeni, potem so lažji od pravih. Če so ponarejeni kovanci s številko 3 oz
4, potem so težje od pravih, bomo ustrezen niz označili s črko T. Na sl. 3.2 Lahki in težki kandidati za ponaredke so označeni z oznakami na robovih drevesa.
Očitno lahko na vprašanje o optimalnem številu tehtanj odgovorimo tako, da nadaljujemo z razvrščanjem možnih shem za izbiro kovancev. Ker je število kovancev končno, je takšno štetje prej ali slej mogoče zaključiti. Za zdaj se osredotočimo na dve dobljeni rešitvi in poskusimo analizirati, kaj sta dali
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
riž. 3.2. Druga rešitev problema ponarejenega kovanca za nas z vidika splošnega pristopa k reševanju problema.
Kot je znano, lahko vsako strategijo tehtanja kovancev opišemo s trojnim ali ternarnim drevesom. Z drugimi besedami, obravnavani problem spada v razred problemov,
ki jih opisujejo ternarna drevesa. Takšna klasifikacija problema omogoča analizo ne vsake posamezne rešitve, temveč vseh rešitev na splošno, ki temeljijo na znanih lastnostih dreves.
Tako, ponovitve konec možne načine uteževanje je pravzaprav iskanje po različnih ternarnih drevesih, ki jih je seveda eksponentno veliko. Po drugi strani pa poskusimo ugotoviti, kaj je na splošno mogoče doseči pri reševanju danega problema z uporabo njegove pripadnosti temu razredu.
Iz sl. 3.1 in 3.2 je razvidno, da pri upodabljanju zaporedja tehtanj z uporabo drevesa vsako tehtanje pripišemo oglišču drevesa, ki ni list (prikazano z ovali), medtem ko izidi, vključno z nemogočimi,
ustrezal listom drevesa (prikazano s kvadratki). Vsa drevesna vozlišča je mogoče razporediti po nivojih,
71
AT
a
=
=
>
AT
a
in
in
in
=
>
AT
a
in
in
in
=
>
AT
a
in
in
in
=
>
AT
a
in
in
in
=
>
AT
a
=
>
AT
a
=
>
AT
a
>
Za
AT
L
pri
0
pri
1
pri
l
-
1
pri
l
……
………………
………
…
…
……
…
…
…
…
…
……
……
…
…
G
a =
l
riž.
3.3.
T
spomladansko drevo teže
72
tiste. po njihovi oddaljenosti od korenine drevesa. Število ravni je enako številu robov, ki morajo preteči od korena, da pridejo do vrha. dani ravni(slika 3.3). Če je globina drevesa raven lista, ki je najbolj oddaljen od korenine, potem je ta vrednost enaka številu uteži v najslabšem primeru.
Koliko možnih rezultatov je v našem problemu? Vsak od n kovancev se lahko izkaže za ponarejen lahek ali ponarejen težki kovanec, ponarejenih kovancev pa morda sploh ni.
Tako imamo 2n + 1 rezultatov. To pomeni, da v drevesu
ki ustreza shemi tehtanja, mora biti najmanj
2n + 1 listi. Ternarno drevo globine l vsebuje največ,
kot 3
odhajam. Iz tega lahko ocenimo najmanjšo možno globino drevesa
3
l
≥ 2n + 1,
in zato
l ≥ log
3
(2n + 1).
(3.1)
Tako je za n = 4 najmanjše možno število tehtanj večje ali enako 2. Tu ne mislimo na najmanjše število tehtanj za to shemo - kot na sl. 3.2, in obstajajo primeri, ko je rešitev problema najdena že po prvem tehtanju - ocenimo najslabšo možnost, t.j. največje število uteži za dano shemo, z drugimi besedami, iščemo najmanjšo med največjimi globinami vseh dreves z vsaj 2n + 1 listi.
Lahko pa se pokaže, da ni metode ponderiranja, ki bi dala enakost v oceni (3.1).
IZREK 3.1
Število tehtanj v najslabšem primeru za problem ponarejenih kovancev je ocenjeno kot l > log
3
(2n + 1).
Dokaz. Kot že omenjeno, je za n kovancev 2n + 1 možnih izidov. Vsako tehtanje ima lahko tri možne rezultate in vsak rezultat ima svojega
73
shema nadaljnjih tehtanj. Hkrati ima shema svoje število možnih rezultatov ob upoštevanju rezultata zadnjega tehtanja. Naj pri prvem tehtanju |S
L
| = |S
R
| = k, tj.
k kovancev se uporabi na eni tehtnici in k kovancev na drugi,
kjer je k ≤ n/2. Če hkrati S
L
R
, nato kovanci iz S
L
razglasimo kandidate za lahke ponarejene kovance in kovance S
R
- Kandidati za težke ponarejene kovance. V to smer,
z rezultatom prvega tehtanja je možnih 2k izidov.
Podobno velja za S
L
>S
R
2k drugih rezultatov je možnih. Zato je za S
L
= S
R
možnih je preostalih 2n + 1 − 4k izidov.
Če v (3.1) velja enakost, to pomeni, da je trojno drevo popolno in so vsi njegovi listi na l-ti ravni.
Toda za to je potrebno, da se po vsakem tehtanju možni izidi enakomerno porazdelijo na tri veje in enakost
2k = 2n + 1 − 4k,
kar je nemogoče, saj je 2k vedno sodo število in
2n + 1 − 4k je vedno liho.
V dokazu izreka 3.1 je bila uporabljena pomembna ideja:
Da bi bilo drevo tehtanja optimalno ali vsaj čim bližje optimalnemu, je nujno, da so rezultati enakomerno porazdeljeni na vse rezultate posameznega tehtanja.
Tako smo dobili oceno za najslabše število tehtanj v problemu ponarejenih kovancev, tako da smo ta problem povezali z razredom problemov
ki jih opisujejo ternarna drevesa. Zdaj razmislite o nekoliko spremenjenem problemu.
Problem 3.2 (problem ponarejenega kovanca ob prisotnosti standarda). Obstaja n kovancev, med katerimi je lahko en ponaredek in še en kovanec, za katerega se zagotovo ve, da je pravi. Ponarejen kovanec je treba določiti v minimalnem številu tehtanj oziroma ugotoviti, da ni ponarejenih kovancev.
74
rešitev. Ta problem se od prejšnjega razlikuje po prisotnosti dodatnega referenčnega kovanca, vendar se izkaže, da ta dodatni kovanec omogoča sestavo dreves z optimalno težo, za katera je izpolnjena enakost v (3.1). Označimo z n l
število, za katero enakost velja
3
l
= 2n l
+ 1.
(3.2)
Pri obravnavi prejšnjega problema v izreku 3.1 smo dobili: da je enakost (3.1) izpolnjena, mora biti utežno drevo popolno. Torej, če je mogoče zgraditi tako optimalno drevo l ravni, bo podalo shemo l uteži za n l
kovanci. Upoštevajte, da velja naslednje razmerje:
n l
= 3nl−1
+ 1.
(3.3)
Ker za n
0
= 0 v (3.2) dobimo enakost 3 0
= 2 0 + 1,
potem lahko od tu z uporabo (3.3) dobimo n
1
= 1,n
2
=
4,n
3
= 13 itd. Rešitev (3.2) je zaporedje
0, 1, 4, 13, 40, . . ..
Če torej velja enakost (3.2), je množica n
l kovancev je razdeljenih na tri enake dele z n l−1
kovancev in ostal je še en kovanec. Razmislimo o različnih situacijah, ki se lahko pojavijo med postopkom tehtanja.
Shema 1. Naj imamo na začetku tehtanja n i
kovanci, kjer n i
pripada zaporedju (3.3) za nekatere i. Postavimo n i−1
kovanci, kjer je n
jaz
= 3n i−1
+ 1,
nato dodamo referenčni kovanec na levo ploščo tehtnice in enega od preostalih n i−1
+ 1 kovanec. Utežene množice označimo kot prej s S
L
in S
R
Zdaj naj kot rezultat tehtanja S
L
= S
R
. Ker je pri tehtanju sodeloval referenčni kovanec, je očitno, da je ponarejeni kovanec, če sploh obstaja, med neporabljenimi n.
i−1
kovancev, problem pa je reduciran na problem z n i−1
kovanci. pri čemer
75
Zaradi ponderiranja imamo še vedno možnih 2n i−1
+ 1 =
3
i−1
rezultati. Zdaj pa naj S
L
R
. To pomeni, da je ponarejeni kovanec bodisi v nizu S
L
in je hkrati lažji od ostalih, oziroma v kompletu S
R
in potem je težji od drugih.
Poleg tega obstaja n i−1
sumljivih lahkih kovancev in n i−1
+ 1 sumljivo težko in skupaj to spet da 2n i−1
+ 1 = 3
i−1
možni rezultati.
Končno naj S
L
>S
R
. Potem imamo n i−1
kandidati za težke kovance in n i−1
+1 kandidatov za pljuča in skupno 2n i−1
+1 =
3
i−1
rezultati. Torej s tako shemo prvega tehtanja dejansko dobimo tisto 3
i začetni rezultati so bili enakomerno porazdeljeni glede na rezultate tehtanja. Če želite ugotoviti, ali je mogoče shemo tehtanja nastaviti tako, da se rezultati po vsakem tehtanju razdelijo na enako število delov, upoštevajte rezultate tehtanja. Očitno je za S
L
= S
R
pridemo do istega problema, le z manjšo dimenzijo, in lahko vedno znova izvedemo utež po shemi 1, vendar z manjšo vrednostjo i.
Shema 2. Naj zdaj S
L
R
. V tem primeru strategijo uteževanja definiramo na naslednji način. Začetni podatek je, da imamo na nekem koraku i v zaporedju uteži 3
jaz
= 2n i
+ 1 novcev, med katerimi n i
lahki ponaredki kandidatov in n i
+ 1 kandidatov za težke, medtem ko je število n i
je število oblike (3.3)
n i
= 3n i−1
+ 1.
Na vsako tehtnico položite ponev n i−1
lahki kandidati in n
i−1
+1 težka. Ker obstaja samo 2n i
+1 = 2(3n i−1
+1)+1 = 6n i−1
+3
kovancev in stehtajte
2n i−1
+ 2n i−1
+ 2 = 4n i−1
+ 2
kovancev, potem je še vedno 2n i−1
+ 1 kovancev, med katerimi je n i−1
+ 1
pljuča in n i−1
težka. Ker je na obeh tehtnicah enako število lahkih in težkih kovancev, če tehtnici nista uravnoteženi,
to daje n i−1
kandidati za lahke kovance (iz sklede, za katero se je izkazalo, da je lažja) in n i−1
+ 1 kandidat za težko (iz sklede, ki se je izkazala za
76
težji). To nas pripelje do izvirnih podatkov iste sheme
(sheme 2), ampak za 3
i−1
= 2n i−1
+ 1 kovanec. Če je tehtnica uravnotežena, potem to pomeni, da moramo ponarejen kovanec iskati med neutehtanimi n i−1
+ 1 pljuča in n i−1
težkih kovancev, kar ustreza shemi 3. Očitno je 2n i−1
+1 rezultati, tj. spet je niz vseh možnih rezultatov razdeljen na tri enake dele.
Shema 3. Naj zdaj S
L
>S
R
. V tem primeru imamo 3
jaz
=
2n i
+ 1 novcev, med katerimi n i
+ 1 lahki ponarejeni kandidati in n i
kandidatov v težki kategoriji. Vsi argumenti so podobni shemi 2, s to razliko, da morate pri tehtanju dati n i−1
+ 1 lahkih kandidatov in n i−1
težka. Če tehtnica ni uravnotežena, dobimo vzorec 3 za 3
i−1
kovancev, sicer dobimo pogoje za tehtanje, ki ustrezajo shemi 2. Tudi v vseh primerih je niz možnih izidov razdeljen na tri enake dele 2n i−1
+ 1.
Tako imamo trikrat
1 2
3
=
>
=
=
riž. 3.4. Prehodi med shemami ponderiranja v zgoraj opisanem problemu ponarejenih kovancev osebnega stanja in pravilom ponderiranja za vsako stanje. Glede na rezultat tehtanja preidemo v drugo stanje (ali ostanemo v istem stanju), vendar za manjše število kovancev. Pri vsakem tehtanju se število možnih izidov enakomerno porazdeli glede na rezultate tehtanja. Shema prehodov med stanji je prikazana na sl. 3.4. Primer tehtanja za 27 kovancev je prikazan na sl. 3.5.
77
Dokaži, da je šahovnica 10X10 ni mogoče razrezati vzdolž mrežnih črt v pravokotnike 1X4. (Rešitve po D.Yu. Kuznetsovu.)
rešitev 1 . Ploščo razdelite na polja 2x2 in jih pobarvajte v šahovnici (slika 1). Upoštevajte, da vsak pravokotnik 1x4 vsebuje enako (2) črne in bele celice, vendar je s to barvo na tabli 52 črnih celic in 48 belih celic, tj. ne enako. To pomeni, da plošče 10x10 ne bo mogoče razrezati na pravokotnike 1x4.
rešitev 2 . Tablo pobarvajmo z diagonalnim barvanjem v 4 barve (slika 2). Upoštevajte, da vsak pravokotnik vsebuje po eno celico vsake od štirih barv, vendar je z določeno barvo na tabli 25 celic 1. in 3. barve, 26 celic 2. in 24 celic 4. barve, tj. ne enako. To pomeni, da plošče 10x10 ne bo mogoče razrezati na pravokotnike 1x4.
1. Izrežite spodnji desni in levi kotni celici iz šahovnice. Ali je mogoče dobljeno figuro razrezati na domine 1x2? In če odrežete spodnji desni in zgornji levi?
2. Ali je mogoče ploščo 6x6 razrezati na domine tako, da je med njimi natanko 11 vodoravnih? (Vodoravno barvanje v dveh barvah.)
3. Risbo pobarvaj v štirih barvah, tako da so sosednji deli pobarvani v različnih barvah. Se da spraviti s tremi barvami? (Glejte Dejavnost 6: Barvanje geografski zemljevid- 5-6 razred).
4. V kvadratu 4x4 so celice leve polovice pobarvane črno, preostale pa bele. V eni operaciji je dovoljeno prebarvati vse celice znotraj katerega koli pravokotnika v nasprotno barvo. Kako iz originalne barve v treh operacijah dobiti šahovsko barvo?
5. Več kobilic sedi na isti ravnini, razdalje med sosedami pa so enake. Vsako minuto eden od njih skoči na točko, ki je simetrična z njim glede na drugo kobilico. Ali lahko čez nekaj časa kobilica Sasha konča na mestu, kjer je na začetku sedel njegov sosed Lyosha?
6. a) Ali je mogoče šahovnico razrezati na figure, sestavljene iz 4 celic v obliki črke »T«?
b) Ali je mogoče šahovnico 10x10 razrezati na takšne figure?
7. Ali je mogoče kvadrat 8x8 z odrezanim vogalom razdeliti na pravokotnike 1x3?
8. Ali je mogoče ploščo 10x10 razrezati na kose štirih celic v obliki črke "G"? (Vodoravno barvanje v dveh barvah.)
9. Plošča 8x8 je razrezana na domine 2x1. Ali je lahko 15 navpičnih in 17 vodoravnih domin?
10. Trikotnik je razdeljen na trikotnike (25 kosov), kot je prikazano na sliki. Hrošč lahko hodi v trikotniku in se premika med sosednjimi (ob strani) trikotniki. Skozi koliko trikotnikov lahko pelje hrošč, če vsak trikotnik ni obiskal največ enkrat?
11. Katero največje število rombov, od katerih je vsak sestavljen iz dveh enakostraničnih trikotnikov s stranico 1, lahko izrežemo iz enakostraničnega trikotnika s stranico 5 (glej sliko prejšnje naloge).
12. Trikotni grad je razdeljen na 100 enakih trikotnih dvoran. Sredi vsake stene so vrata. Koliko sob lahko obišče oseba, ki ne želi več kot enkrat obiskati nikamor?
2. poglavje šahovnica
Za podroben prikaz šahovske matematike, ki ga bomo začeli, je najbolj naravno začeti z matematične težave o sami plošči, ne da bi nanjo še položili kakršno koli figuro. Tej temi je posvečeno to poglavje.
Najprej razmislimo o več problemih prekrivanja deske z dominami 2 × 1. Povsod se predpostavlja, da vsaka domina pokriva dve polji na plošči, vsako polje pa pokriva ena polovica domin. Začnimo z naslednjim starim problemom.
Ali je mogoče z dominami prekriti kvadrat velikosti 8×8, iz katerega so izrezane nasprotne kotne celice (slika 2a)?
Lahko bi uporabili algebraično sklepanje, vendar je "šahovska" rešitev enostavnejša in elegantnejša. Pobarvajmo naš prisekan kvadrat črno-belo in ga spremenimo v šahovnico brez dveh kotnih polj a8 in h1 (slika 2b). Za poljubno prekrivanje plošče vsaka domina pokriva eno belo in eno črno polje. Imamo dve beli polji manj kot črnih (izrezana polja so bela), zato potrebne pokritosti ni! Kot lahko vidimo, barvanje plošče šahistu ne le olajša navigacijo med igro, ampak služi tudi kot sredstvo za reševanje matematičnih problemov.
Pri obravnavanem problemu ni bilo pomembno, da so kotna polja izrezana iz plošče, ampak da so enake barve. Jasno je, da ne glede na to, kako izrežete par enobarvnih polj, preostalega dela plošče ne boste mogli prekriti z dominami. Tako se pojavi naslednji problem.
Recimo, da sta na šahovnici izrezani dve polji različnih barv. Ali je preostanek plošče vedno mogoče prekriti z 31 dominami?
Izkazalo se je, da vedno. Spektakularen dokaz je našel slavni ameriški matematik R. Gomory. Narišimo na šahovnico meje med navpičnicami in vodoravnicami, kot je prikazano na sl. 3. V labirintu med temi robovi si sledijo črna in bela polja, ki se izmenjujejo kot dvobarvni gumbi na sklenjeni niti (pot, po kateri je mogoče ta labirint obiti, je zaprta). Kateri koli dve različni polji izrežemo iz plošče, se bo nit pretrgala: na enem mestu, če sta izrezani polji sosednji, in na dveh mestih drugače. V tem primeru bo vsak kos niti sestavljen iz sodega števila polj. Posledično lahko te figure in s tem celotno ploščo prekrijete z dominami!
riž. 3. Labirint Gomory |
Zanimive zamisli v zvezi z gumbi in nitmi boste našli v 11. poglavju.
Predpostavimo, da je nekaj polj izrezano iz šahovnice, tako da na njen preostali del ni mogoče postaviti domin. Enostavno preverimo, da je najmanjše število izrezanih polj s to lastnostjo 32 - to so vsa polja iste barve (bela ali črna).
Problemi s šahovnico in domino so le majhen del ogromne vrste tovrstnih problemov. Ameriški matematik S. Golomb je ustvaril celo znanost, ki jo je poimenoval polimipo, njegova knjiga na to temo pa je prevedena v mnogih državah sveta, tudi pri nas. Na splošno je poliomino preprosto povezana figura, sestavljena iz kvadratov. Z vidika šahista preprosto povezovanje pomeni, da lahko vsa polja poliomina obidemo s potezo topa. Odvisno od števila kvadratov 07 so poliomini v različnih stopnjah. Monomino vsebuje en kvadrat, domino dva, tromino tri, tetramino štiri, pentomino pet, heptomino šest kvadratkov itd. Poudarili bomo še nekaj vprašanj, povezanih z navadno šahovnico. Očitno je, da je nemogoče pokriti dssk samo z ravnimi trominami, tj. domino 3 × 1, saj 64 ni deljivo s 3. Pojavi se naslednja težava.
Ali je mogoče pokriti šahovnico z 21 ravnimi trominami in enim monominom? Če da, katera polja lahko zaseda monomino?
Eden od potrebnih dapo premazov na sl. 4a. Da določimo možne razporeditve monominov, na tablo narišemo dva sistema vzporednih črt, kot je prikazano na sl. 4b.
Zlahka je videti, da za katero koli prevleko vsak tromino pokriva točno eno polje, skozi katerega poteka polna črta, in točno tisto, skozi katero poteka črtkana črta. Ker je število polj, ki jih sekajo polne črte, 22, prav tako število polj, ki jih sekajo črtkane črte, in je trominov 21, lahko monomini pokrivajo samo polja, ki jih sekata obe družini črt. In takšna polja so samo štiri: c3, c6, f3 in f6! Z obračanjem plošče za 90, 180 in 270° lahko dobite ustrezno pokritost za vsako od teh štirih polj.
Naslednja naloga je nekoliko drugačna od zgoraj obravnavanih.
Ali je mogoče šahovnico prekriti z dominami tako, da ni mogoče potegniti ene meje med vertikalami in horizontalami, ne da bi prečkali domine?
Če si predstavljamo, da je plošča stena, domine pa so opeke, potem obstoj določene meje (šiva) kaže na krhko zidanje. Z drugimi besedami, problem se sprašuje, ali je mogoče "opeke" razporediti tako, da se "zid" ne poruši. Pravokotnik, ki ga je mogoče prekriti na zahtevan način, se imenuje "močan". "Moč" šahovnice je razvidna iz sl. 5. V splošnem primeru Gardner pokaže, da je mogoče domine zložiti v "močan" pravokotnik, če je njegova površina enakomerna, njegova dolžina in širina pa večji od štiri, z edino izjemo kvadrata 6 × 6.
V nadaljevanju bomo pogosto obravnavali pravokotne šahovnice takšne ali drugačne velikosti. V tem primeru se vedno predpostavlja, da ima plošča m×n m vertikal in n horizontal (šah). Za tablo pravimo, da je soda, če je število njenih polj sodo, sicer pa je liha. Kjer dimenzije table niso določene, mislimo na standardno šahovnico, za katero velja m = n = 8.
Tabla 100x4 je prekrita z dominami. Dokažite, da ga je mogoče razrezati vzdolž ene od mej med navpičnicami in vodoravnicami, ne da bi to vplivalo na katero koli od domin.
Katera koli od navedenih meja razdeli tablo na dva dela, sestavljena iz sodega števila polj. Polja vsakega dela delimo na dva razreda: pokrite domine, ki v celoti ležijo v tem delu, in pokrite domine, ki jih seka meja. Ker je število polj vsakega dela sodo (morda nič), prav tako število polj prvega razreda (vsaka domina pokriva dve polji), je število polj drugega razreda sodo. In to pomeni, da je število domin, ki jih prečka meja, sodo. Skupaj sta 102 ločilni meji (99 navpičnih in 3 vodoravne), in če vsaka od njih prečka domine, potem je v kritju udeleženih najmanj 102 × 2 = 204 domin. Samo 200 jih imamo! Pravzaprav smo pokazali, da je pravokotnik 100x4 "šibak".
Vprašanje možnosti prekrivanja poljubne pravokotne plošče z linearnimi k-mini (domine k × 1) je rešeno z naslednjim izrekom.
Plošča m × n je lahko prekrita z linearnimi k-mino, če in samo če je vsaj eno od števil m ali n deljivo s k brez ostanka.
Izrek ponazorimo z naslednjim primerom.
Ali je mogoče ploščo 10x10 (na taki plošči se igra sto kvadratov) prekriti z ravnimi tetramini?
Ravni tetramino ima dimenzije 4x1, kar pomeni, da bi lahko načeloma 25 ploščic prekrilo vsa polja naše plošče. Vendar iz izreka sledi, da je to nemogoče - 10 ni deljivo s 4.
Razmislimo še o nekaj problemih o šahovnici. Pri rešitvi naslednjega problema viovb se uporablja njegovo barvanje.
Naj bo tabla sestavljena iz lihega števila polj. Na vsako od njegovih polj bomo postavili nekaj šahovska figura. Ali je mogoče vse te figure premakniti na sosednja polja (navpično ali vodoravno), tako da nobena dva ne končata na istem polju?
Naloga je nemogoča. Dejansko, če bi navedeni premik figur obstajal, bi vsaka "bela" figura (ki stoji na belem polju) postala "črna" (padla bi na črno polje), vsaka "črna" pa "bela".
Tako bi bila tabla sestavljena iz enakega števila belih in črnih polj, kar je v nasprotju z njeno "nenavadnostjo".
Priljubljeni so problemi rezanja šahovnice. Najbolj znan med njimi je naslednji, v lasti S. Loyda.
Na poljih a1, b2, c3, d4 so štirje konji. Ploščo razrežite na štiri skladne dele (ki sovpadajo, ko so postavljeni drug na drugega), tako da ima vsak od njih konja.
Pri težavah z rezanjem se vedno predpostavlja, da se rezi izvajajo le vzdolž meja med vertikalami in horizontalami plošče. Rešitev tega problema je prikazana na sl. 6. Od časa Loyda se je na to temo pojavilo veliko novih in težjih problemov. Predvsem so bili rešeni problemi razreza plošče na štiri skladne dele za različne položaje vitezov (vitezi imajo tu seveda le simbolično vlogo). Glede tega vprašanja je še veliko nerešenih vprašanj. Na primer, število načinov, na katere je mogoče navadno ploščo (brez kosov) razrezati na dva skladna kosa, še vedno ni znano.
riž. 6. Loydov problem štirih konj |
Naj se po več rezih plošče nastali deli premaknejo, tako da lahko naslednji rez izreže ne enega, ampak več delov hkrati. Koliko rezov bo potrebnih, da dobimo 64 posameznih prostorov na plošči (polja 1×1)?
Najprej desko prerežemo na pol, nato obe polovici postavimo eno poleg druge in desko razrežemo na štiri enake dele itd. Skupaj bo potrebnih 6 rezov (2 e \u003d 64), manjšega števila pa ni mogoče opustiti .
Zdaj je dovoljeno rezati dele plošče samo ločeno. Koliko rezov bo potrebnih, da dobimo 64 polj v tem primeru?
Praviloma ta naloga (še posebej, če je predlagana po prejšnji) povzroča določene težave. Očitno je to posledica neke inercije našega razmišljanja. Konec koncev je takoj jasno, da bo potrebnih 63 kosov! Dejansko vsak rez poveča število delov za enega; hkrati imamo v začetnem trenutku en del (sama plošča), v končnem trenutku pa 64 (vsa polja plošče).
riž. 7. Tri težave na nenavadni plošči |
V nalogi na sl. 7a, morate opraviti tri naloge, eno matematično in dve čisto šahovski:
a) desko razrežemo na štiri skladne dele;
b) mati črnega kralja po najkrajši poti, ko beli preide;
c) matirati črnega kralja po najkrajši poti; med potezo črnega zvesti igrajo kooperativno).
Rešitve: a) kako razrezati desko, prikazano na sl. 7b; b) ko beli premakne, je mat dan na 12. potezi: 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 (vse poteze črnega kralja so izsiljene in niso podane); c) pri pravilni igri po 1. ... Ke6-e7 mat ni mogoč, saj se črni kralj skrije na e8 - 2. Be1-b4+ Ke7-e8, škof temnega polja pa je prisiljen zapustiti diagonalo a3 - e7. zaradi grožnje zastoja. Vendar, če črni igra kooperativno (pomaga belemu pri matiranju), je cilj dosežen v samo treh potezah:
1. … Ke6-d6
2. Ke3-d4 Ke6-e7
3. Be1-b4+ Ke7-e6
4. Be4-d5 mate.Številna polja naše plošče se med parjenjem ne uporabljajo, a če bi jih izključili, ne bi bilo težav pri rezanju plošče.
riž. 8. Paradoks z razrezom šahovnice: a) 8×8 = 64; b) 13×5 = 65 |
Razmislite zdaj o enem dobro znanem paradoksu, povezanem z rezanjem šahovnice. Desko razrežemo na štiri dele, kot je prikazano na sl. 8, a (v tem primeru nam ni donosno barvati njegova polja), iz nastalih delov pa bomo dodali pravokotnik (slika 8, b). Površina plošče je 64, površina nastalega pravokotnika pa 65. Tako je pri rezanju plošče od nekje prišlo eno dodatno polje!
Rešitev paradoksa je, da naše risbe niso povsem točne (namenoma smo risali debele črte, da bi skrili netočnosti). S skrbno izdelavo risbe na sl. 8b se bo namesto diagonale pravokotnika pojavila rahlo podolgovata figura v obliki diamanta s stranicami, ki se zdijo skoraj zlite. Površina te številke bo enaka "dodatni" enoti.
Znani popularizator matematike na začetku stoletja, E. Ignatiev, je prišel do "metode šahovnice", ki omogoča izpeljavo različnih formul. Na to temo podajamo dva preprosta primera.
Poiščimo vsoto prvih n naravnih števil z uporabo "metode šahovnice". Da bi to naredili, na plošči (n + 1) × n (na sliki 9, a n = 8) pobarvamo vsa polja prve vertikale, vsa polja druge vertikale (razen zgornjega), tretja navpična (razen dveh zgornjih) itd. d., končno - spodnja polje nth navpično. Posledično bosta beli in črni polji na naši tabli enaki, in sicer 1 + 2 + ... + n. Ker je celotna plošča sestavljena iz n (n + 1) polj, dobimo
2 (1 + 2 + … + n) = n (n + 1),
od koder sledi znana formula za vsoto aritmetične progresije:
1 + 2 + … + n = n(n + 1)/2.
Zdaj dokažimo naslednjo formulo:
8(1 + 2 + ... + n) + 1 = (2n + 1)².
Če želite to narediti, vzemite ploščo (2n + 1) × (2n + 1) in pobarvajte več njenih polj s črno, kot je prikazano na sl. 9, 6 (za primer n = 5). Očitno vsak črni del vsebuje (1 + 2 + ... + n) polj. Brez upoštevanja osrednjega polja imamo tu štiri enake bele in črne dele. Zahtevana formula izhaja iz dejstva, da naša tabla vsebuje (2n + 1)² polj in je sestavljena iz sredinskega polja in osmih enakih delov (štirje beli in štirje črni - slika 9b).
Pri razkrivanju paradoksa, pa tudi pri seznanjanju z "metodo šahovnice", lahko samo tablo varno zamenjate s kockastim listom ali mizo. Težav s takimi objekti je ogromno, vendar bi nas njihova podrobna obravnava preveč oddaljila od šaha.
V zaključku poglavja predstavljamo en star dokaz na šahovnici ... Pitagorovega izreka. Na tablo narišite kvadrat, kot je prikazano na sl. 10, a. Tabla je razdeljena na ta kvadrat in štiri skladne pravokotne trikotnike. Na sl. 10, 6 vidimo iste štiri trikotnike, pa tudi dva kvadrata. Torej trikotnika v obeh primerih zavzemata isto površino. Posledično preostali deli plošče brez trikotnikov zavzemajo isto površino, na sl. 10,a - en kvadrat, na sl. 10b - dva. Ker je veliki kvadrat zgrajen na hipotenuzi pravokotnega trikotnika, mali kvadrati pa na njegovih krakih, potem so "Pitagorejske hlače enake v vseh smereh"!
Seveda, strogo gledano, naše razmišljanje ne dokazuje Pitagorejskega izreka (preučevali smo le posamezen primer), ampak ga le ilustriramo. Toda takšen dokaz je brez uporabe šahovnice - za vsak pravokotni trikotnik lahko izberete kvadrat, ki se lomi na podoben način.
Ta rešitev je podana v knjigi T. Saatija "Metode optimizacije celih števil in sorodni ekstremni problemi" (M., "Mir", 1973).
S. Golomb. Polyomino. M., Mir, 1974.
To je dokazal A. Soifer v članku "Šahirane plošče in polimipo" ("Kvant", 1972, št. 11); tam so podani tudi številni novi poliominski problemi.
E. Ignatiev. Na področju iznajdljivosti ali aritmetike za vsakogar. Knjiga. 1 - 3. M. - Str., Gosizdat, 1923.
V tej lekciji bomo govorili o pobarvankah in o tem, kako pomagajo pri reševanju problemov. Razmislite o nestandardnih težavah z rezanjem in polaganjem ploščic ter načinih za njihovo rešitev.
Povzetek lekcije "Rezanje. Teselacija. Barvanje."
Pobarvanke. Rezanje. Teselacije.
Številni znanstveniki že od antičnih časov radi rešujejo probleme. Rešitve številnih preprostih problemov rezanja so našli že stari Grki in Kitajci, vendar je prvo sistematično razpravo na to temo napisal Abul-Vef, slavni perzijski astronom iz 10. stoletja, ki je živel v Bagdadu. Geometri so se resno lotili reševanja problemov rezanja figur na najmanjše dele in nato iz njih sestavili eno ali drugo novo figuro šele v začetku 20. stoletja. Eden od ustanoviteljev te fascinantne veje geometrije je bil slavni sestavljalec ugank Henry E. Dudeney. Posebej veliko število že obstoječih številk, ki podirajo rekorde, je podrl strokovnjak na avstralskem patentnem uradu Harry Lindgren. Je vodilni rezalnik figur.
Danes ljubitelji ugank radi rešujejo rezalne probleme, predvsem zato, ker ni univerzalne metode za reševanje takšnih problemov in vsak, ki se loti njihove rešitve, lahko v celoti pokaže svojo iznajdljivost, intuicijo in sposobnost kreativnega razmišljanja. Ker tukaj ni potrebno poglobljeno poznavanje geometrije, lahko amaterji včasih celo prekašajo profesionalne matematike.
Da bi dokazali, da je mogoče rešiti problem razreza neke figure na dele, je dovolj, da zagotovite nekakšno metodo rezanja. Iskanje vseh rešitev, torej vseh načinov rezanja, je nekoliko težje. In dokazati, da je rezanje nemogoče, je že precej težko. V nekaterih primerih nam pri tem pomaga barvanje figure.
Naloga 1: Vzeli smo kvadrat karirastega papirja velikosti 8 × 8, iz njega izrezali dve celici (levo spodaj in desno zgoraj). Ali je mogoče dobljeno figuro popolnoma prekriti z "dominami" - 1 × 2 pravokotnika?
Naloga 2. Ali je mogoče postaviti šahovnico z dvaintridesetimi dominami tako, da jih je 17 vodoravno in 15 navpično?
Naloga 3: Ali je možno izrezati kvadrat karirastega papirja na želeno velikost
4×4 za en podstavek, en kvadrat, en stolpec in en cikcak?
Naloga 4: Ali je mogoče razporediti kvadrat 8×8 s 15 pravokotniki 1×4 in enim vidnim kotom?
Naloga 5: Ali je mogoče postaviti pravokotnik 6×10 s pravokotniki 1×4?
Naloga 6: Ali je mogoče prepogniti kvadrat 6×6 z 11 pravokotniki 1×3 in enim vidnim kotom?
Naloga 7: Na vsaki celici plošče 5 × 5 je hrošč. V določenem trenutku vsi hrošči vzletijo in pristanejo na sosednjih celicah ob strani. Dokaži, da bo vsaj eden prazna kletka.
Naloga 8: Iz plošče 8 × 8 izrežite kotno kletko. Ali lahko preostanek razrežete na pravokotnike 3×1?
Naloga 9: Kamela se giblje po šahovnici s potezo kot (1, 3). Ali je mogoče »kamelo« premakniti s poljubnega polja na sosednje?
Naloga 10: Ali je lahko plošča 10 × 10 prekrita s figurami oblike ?
Naloga 11: Podana je tabla 12 × 12. V spodnjem levem kotu je 9 dama, ki tvorijo kvadrat 3 × 3. V eni potezi lahko izberete dve dami in enega od njiju preuredite simetrično glede na drugega (ne da bi zapustili tablo) . Ali je mogoče ta dama premakniti v več potezah, tako da tvorijo kvadrat 3 × 3 v spodnjem desnem kotu?
Naloga 12: V vsaki celici kvadrata 9 × 9 je hrošč. Na ukaz vsak hrošč odleti v eno od diagonalno sosednjih celic. Dokaži, da bo potem vsaj 9 celic prostih.
Naloga 13: Grad ima obliko pravilnega trikotnika, razdeljenega na 25 majhnih dvoran enake oblike. V vsaki steni med vežama so narejena vrata. Popotnik se sprehodi po gradu, ne da bi katero od dvoran obiskal večkrat. Poiščite največje število dvoran, ki jih lahko obišče. 
Naloga 14:Kolikšno je največje število rombov, ki jih je mogoče razrezati v enakostranični trikotnik, razdeljen na 36 enakostraničnih trikotnikov?
Naloga 15. V kvadratu 7x7 je 16 ploščic 1x3 in ena ploščica 1x1. Dokažite, da ploščica 1 × 1 leži v središču ali pa meji na robove kvadrata.
Naloga 16. V spodnjem levem kotu šahovnice 8×8 je postavljenih devet žetonov v obliki polja 3×3. Žeton lahko skoči na prosto polje skozi bližnji žeton, to pomeni, da se lahko odbije simetrično glede na njegovo središče (lahko skočite navpično, vodoravno in diagonalno). Ali je možno z določenim številom takšnih potez vse žetone znova postaviti v obliko kvadrata 3 × 3, vendar v drugem kotu.
