Logický úkol pro umístění kostek domina na šachovnici. Matematické olympiády a olympiádové úlohy
Daná šachovnice 8×8, ze které byly vyříznuty dva diagonálně protilehlé rohy, a 31 domino; každé domino může pokrýt dvě pole na desce. Je možné celé prkno vydláždit kostmi? Zdůvodněte svou odpověď.
Řešení
Na první pohled se zdá, že je to možné. Deska je 8×8, tedy 64 buněk, vyloučíme dvě, což znamená, že zbývá 62. Zdá se, že 31 kostí by se mělo vejít, ne?
Když se pokusíme naaranžovat domino v první řadě, máme k dispozici pouze 7 polí, jedna kost jde do druhé řady. Poté položíme domino do druhé řady a opět jedna dlaždice jde do třetí řady.
V každé řadě bude vždy jedna kost, kterou je třeba přesunout do další řady, bez ohledu na to, kolik rozložení zkusíme, nikdy se nám nepodaří vyskládat všechny kosti.
Šachovnice je rozdělena na 32 černých a 32 bílých buněk. Odstraněním protilehlých rohů (všimněte si, že tyto buňky jsou stejné barvy) nám zůstane 30 buněk jedné barvy a 32 buněk jiné barvy. Předpokládejme, že nyní máme 30 černých a 32 bílých čtverců.
Každá kostka, kterou položíme na plán, bude zabírat jednu černou a jednu bílou buňku. 31 kostek domina tedy obsadí 31 bílých a 31 černých buněk. Ale na naší desce je pouze 30 černých a 32 bílých buněk. Proto je nemožné rozložit kosti.
Analýza je převzata z překladu knihy G. Luckmana McDowella a je určena pouze pro informační účely.
Pokud se vám kniha líbila, doporučujeme vám ji zakoupit.
6. V krabičce je 235 zápalek. Postupně je vezmou dva hráči. V jednom tahu můžete vzít 1 až 6 zápasů. Hráč vyhrává
brát poslední zápas. Kdo vyhraje, když se hraje správně?
62
7. Z desky 8 × 8 se vyřízne rohový čtverec. Je možné desku položit do obdélníků 1×3?
8. Ze 30 zápasů berou dva hráči dle svého uvážení od 1
až 6 zápasů. Vyhrává ten, kdo vezme poslední zápas.
9. Jsou tam tři hromady kamení. Stát je trojice čísel
(X
1
, X
2
, X
3
), kde x i
- počet kamenů v i-té hromadě. Tah je operace převodu z hromady na hromadu počtu kamenů, který se rovná počtu kamenů v hromadě, kde se převod provádí. Z počátečního stavu (11, 7, 6) získáte stav (8, 8, 8).
10. Rozdělte kruh na maximální počet dílů pomocí čtyř rovných čar.
11. Řez řecký kříž dvěma rovnými čarami tak, že
aby se z výsledných částí vytvořil obdélník, jehož jedna strana je dvakrát ta druhá.
12. V 9 je 12litrová zásoba kapaliny a prázdné nádoby
a 5 l. Je potřeba naměřit přesně 6 litrů. Kolik litrů lze s takovými nádobami změřit ze zásoby 12 litrů?
13. Určete počet posloupností délky n z (0, 1, 2),
ve kterém neexistují dvě po sobě jdoucí jednotky.
14. Je možné pokrýt čtverec 10 × 10 figurami formuláře?
15. Je možné pokrýt čtverec 10 × 10 figurami formuláře?
63
16. Je možné obložit čtverec 8×8 s vyříznutou rohovou buňkou figurami formuláře?
17. Je možné pokrýt figurami ve tvaru šachovnice 8 × 8, ve které je vyříznut čtverec:
18. Je možné položit šachovnici s vyřezávanou rohovou klecí s dílky formy
19. Je možné provést křížení čtyř párů rytíř-panoš pomocí dvoučlenného člunu, když panoš nemůže být na jednom břehu s cizím rytířem (rytíři) v nepřítomnosti svého pána?
20. Vytvořte algoritmus pro nalezení dvou nejmenších čísel v neuspořádané posloupnosti n čísel.
21. Z 27 zápasů ležících na stole odehrají dva hráči střídavě alespoň jeden a ne více než čtyři zápasy. Vyhrává ten, kdo bude mít na konci hry sudý počet zápasů. Vytvořte algoritmus pro hru prvního hráče.
64
22. Dva účastníci hry se střídají ve volání čísla od 1 do 10.
Zavoláním čísla jej hráč přičte k již existujícímu součtu čísel (zavoláním prvního čísla jej hráč přičte k nule). Vyhrává hráč, který dosáhne 100 bodů.
Vytvořte algoritmus pro hru prvního hráče.
23. Najděte minimální počet otázek (možné odpovědi:
"ano", "ne") skryté 5místné číslo, pokud je součet prvních tří číslic 17.
24. Najděte minimální počet otázek (možné odpovědi:
"ano", "ne") skryté 4místné číslo, pokud je součet druhé a čtvrté číslice 7.
25. Kolika způsoby lze vyměnit 100 rublů? mince v
5, 10, 20 a 50 rublů?
26. Vypočítejte rekurzivně počet šesticiferných čísel, jejichž součet prvních čtyř číslic je 26 a součet posledních dvou 14.
27. Vypočítejte rekurzivně počet oddílů čísla 37 pěti členy, z nichž první nepřesahuje 7, druhý
- 5 a třetí a čtvrtý přebírají hodnoty ze sady
{5, 6, 7, 8}.
28. Vypočítejte rekurzivně počet sedmiciferných čísel, jejichž součet prvních čtyř čísel je 21 a součet posledních pěti čísel je 19.
29. Vypočítejte rekurzivně počet oddílů čísla 27 čtyřmi členy, z nichž první nepřesahuje 7,
druhá je 8 a třetí a čtvrtá přebírají hodnoty ze sady (3, 5, 7).
30. Vypočítejte rekurzivně počet pěticiferných čísel, jejichž první tři číslice tvoří 21 a poslední tři číslice tvoří 12.
65
31. Vypočítejte rekurzivně počet sedmiciferných čísel, ve kterých je součet první a třetí číslice 12 a součet zbývajících pěti je 19.
32. Počítejte rekurzivně
(2n − 2) (2n − 4) × . . . ×2
(n + 1) (n + 3) x. . . × (n + 2n − 1)
a n−5
b
−(n+3)
33. Vypočítejte rekurzivně počet sedmiciferných čísel, jejichž součet prvních čtyř číslic je 17 a součet posledních tří číslic je 16.
34. Vypočítejte rekurzivně počet oddílů čísla 17 čtyřmi členy, z nichž první nepřesahuje 4, druhý - 8 a třetí a čtvrtý mají hodnoty (3, 4, 8).
35. Vypočítejte rekurzivně počet sedmiciferných čísel, jejichž součet druhých mocnin prvních čtyř čísel je 17 a součet druhých mocnin posledních dvou je 16.
36. Vypočítejte rekurzivně počet oddílů čísla 25 čtyřmi členy, z nichž první nepřesahuje 8,
druhá je 3 a třetí a čtvrtá nabývají hodnot ze sady (2, 5, 9).
37. Vypočítejte rekurzivně počet umístění N věží na šachovnici
N × N tak, aby věže byly symetrické vzhledem k oběma úhlopříčkám a neútočily na sebe.
38. Vypočítejte rekurzivně počet binárních posloupností n prvků, ve kterých chybí dva sousední.
39. Je dána mřížka N × M:
66
M
N
A
B
Vypočítejte rekurzivně počet cest z A do B. Cesta je posloupnost tahů po mřížce vedoucí zleva doprava a zdola nahoru.
40. Jsou uvedena čísla a
1
, . . . , n
v určitém pořadí. Pro výpočet součinu a
1
·. . a n
při zachování pořadí faktorů existuje mnoho způsobů, jak umístit závorky mezi faktory. Vypočítejte rekurzivně počet způsobů umístění závorek.
41. Vypočítejte rekurzivně počet 8místných čísel, jejichž součet prvních pěti číslic je 29 a součet posledních tří číslic 21.
67
3
. metody analýzy algoritmů
3.1. Třídy algoritmů
V předchozích částech jsme zvažovali různé přístupy, které lze použít při konstrukci algoritmů. K nalezení řešení, k analýze účinnosti tohoto řešení lze předložit různé předpoklady, použít již známé jiné algoritmy, přeformulovat stav problému atd. Můžete vyhledat některé podobné problémy se známým řešením a použít toto řešení k nalezení algoritmu pro požadovaný problém.
Existuje však mnoho konkrétních problémů, pro které byla nalezena řešení. Úkolů nevyřešených nebo vyřešených s určitými omezeními a podmínkami je ještě více. Hledání podobných problémů mezi celým souborem problémů, hodnocení existujících řešení podle jejich míry „vhodnosti“ může být obtížný, časově náročný a ne vždy řešitelný problém. Bylo by užitečnější a produktivnější pokusit se definovat třídy problémů sjednocené společným problémem, společnými metodami a přístupy k řešení a pak hledat třídu, které lze přiřadit náš konkrétní problém, který je třeba vyřešit. Takových tříd by samozřejmě nemělo být příliš mnoho, ale na druhou stranu by jich nemělo být příliš málo, aby každá nová úloha definovat svou vlastní, novou třídu, která pak pravděpodobně nebude použita k řešení jiných problémů.
Jako příklad problému spadajícího do určité třídy uveďme dobře známý problém identifikace padělané mince.
Úloha 3.1 (problém o padělaná mince). Existuje n mincí,
mezi nimiž může být jeden padělek. Padělaná mince se od ostatních liší hmotností a k dispozici máme váhu se dvěma kelímky. Je nutné určit padělanou minci pro minimální počet vážení nebo stanovit,
že neexistují žádné padělané mince.
68
Řešení. Problém padělaných mincí byl vyřešen v Sec. 2,2,
ale pak se vědělo, že padělaná mince je nutně lehčí. Nyní se pokusme tento problém vyřešit pro obecnější případ. Jakékoli řešení tohoto problému (ne nutně optimální)
lze interpretovat jako sekvenci vážení. Je však zřejmé, že výběr mincí pro vážení v kterémkoli kroku závisí na tom, jaké mince byly použity a na výsledcích vážení v předchozích krocích. Sled vážení znázorníme následovně. Mince přečíslujeme a definujeme jako množinu S = (1, 2, . . . , n). Sady čísel vážených mincí na levé a pravé misce váhy lze označit S
L
a S
R
respektive. Je jasné, že vážení má smysl pouze v případě, že mohutnosti množin S
L
a S
R
zápas, tzn. Každá stupnice má stejný počet mincí. Vážení bude označeno znakem ":", pak každé vážení
(S
L
): (S
R
) jsou tři možné výsledky. Spousta mincí
S
L
může být lehčí, těžší nebo se stejnou hmotností jako sada S
R
. Potom tyto výsledky vážení označíme jako
"" nebo "=". Příklad vážení čtyř mincí je na Obr. 3.1. Ovály představují vážení, čtverce představují výsledky, které označují číslo padělané mince a zda je lehčí nebo těžší než ostatní.
Případ nepadělané mince je označen jako „0“, přeškrtnuté čtverečky odpovídají případům, které nemohou nastat.
Odhadneme maximální počet vážení potřebný k vyřešení problému, tzn. nejhorší případ. Jak je patrné z Obr. 3.1 je problém v nejhorším případě vyřešen ve 3 váženích. Všimněte si, že i v nejlepším případě potřebujeme alespoň 2
vážení. Lze dosáhnout lepšího výsledku?
Na Obr. 3.1 představuje další řešení problému vážení čtyř mincí. V prvním kroku nezvážíme pár mincí, ale všechny mince a rozdělíme je do dvou sad. V důsledku toho jsme dosáhli toho, že v nejlepším případě je potřeba pouze jedno vážení,
v nejhorším případě je však počet vážení opět 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
=
=
=
>
>
>
>
>
=
=
Rýže. 3.1. Řešení problému s padělanými mincemi
Pamatujte, že na rozdíl od první možnosti vážení,
znázorněno na Obr. 3.1 jsme ve druhé verzi definovali nejen schéma vážení, ale také představili nový koncept kandidátů na padělané mince. Skutečně zvažte výsledek prvního vážení, (1, 2) : (3, 4). Nechte (1, 2) L
= (1, 2) a S
R
= (3, 4). Pak
S
L
R
. Z tohoto výsledku nelze posoudit, zda je padělaná mince lehčí nebo těžší než všechny ostatní,
a v jaké je to sestavě. Lze však předpokládat
(a ještě přesněji - lze tvrdit), že pokud padělaná mince patří do sady S
L
, pak je padělaná mince světlejší než ostatní, takovou sadu označíme písmenem L. V našem případě, pokud jsou mince s čísly 1 nebo 2 padělané, pak jsou lehčí než pravé. Pokud jsou padělané mince s čísly 3 resp
4, pak jsou těžší než skutečné, označíme odpovídající sadu písmenem T. Na obr. 3.2 lehké a těžké padělky kandidátů jsou označeny značkami na okrajích stromu.
Je zřejmé, že na otázku o optimálním počtu vážení lze odpovědět pokračováním v třídění možných schémat výběru mincí. Vzhledem k tomu, že počet mincí je konečný, může být dříve nebo později takový výčet dokončen. Zastavme se zatím u obou získaných řešení a pokusme se analyzovat, co 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
Rýže. 3.2. Další řešení problému padělané mince nám z pohledu obecného přístupu k řešení problému.
Jak je známo, jakákoli strategie vážení mincí může být popsána pomocí ternárního nebo ternárního stromu. Jinými slovy, uvažovaný problém patří do třídy problémů,
popsaný ternárními stromy. Taková klasifikace problému umožňuje analyzovat ne každé konkrétní řešení, ale všechna řešení obecně na základě známých vlastností stromů.
Tím je iterace ukončena možné způsoby vážení je vlastně prohledávání různých ternárních stromů, kterých je samozřejmě exponenciálně mnoho. Na druhou stranu se pokusme určit, čeho je obecně možné dosáhnout při řešení daného problému pomocí jeho příslušnosti k této konkrétní třídě.
Z Obr. 3.1 a 3.2 je vidět, že při zobrazení sekvence vážení pomocí stromu připisujeme každé vážení vrcholu stromu, který není listem (znázorněno pomocí oválů), zatímco výsledky, včetně nemožných,
odpovídalo listům stromu (znázorněno čtverečky). Všechny uzly stromu lze seřadit podle úrovní,
71
V
A
=
=
>
V
A
A
A
A
=
>
V
A
A
A
A
=
>
V
A
A
A
A
=
>
V
A
A
A
A
=
>
V
A
=
>
V
A
=
>
V
A
>
Na
V
L
V
0
V
1
V
l
-
1
V
l
……
………………
………
…
…
……
…
…
…
…
…
……
……
…
…
G
a =
l
Rýže.
3.3.
T
jarní strom hmotnosti
72
těch. podle jejich vzdálenosti od kořene stromu. Číslo úrovně se rovná počtu hran, které musí projít od kořene, aby se dostaly do vrcholu. danou úroveň(obr. 3.3). Pokud je hloubka stromu úroveň listu nejdále od kořene, pak se tato hodnota rovná počtu vážení v nejhorším případě.
Kolik možných důsledků je v našem problému? Každá z n mincí se může ukázat jako falešná lehká nebo falešná těžká mince a nemusí tam být vůbec žádné falešné mince.
Máme tedy 2n + 1 výsledků. To znamená, že ve stromě
odpovídající schématu vážení, musí být min
2n + 1 list. Ternární strom hloubky l obsahuje nejvýše,
než 3
odcházím. Z toho můžeme odhadnout minimální možnou hloubku stromu
3
l
≥ 2n + 1,
a tudíž
l ≥ log
3
(2n + 1).
(3.1)
Pro n = 4 je tedy minimální možný počet vážení větší nebo roven 2. Zde máme na mysli nikoli minimální počet vážení pro toto schéma - jako na Obr. 3.2, a jsou případy, kdy je řešení problému nalezeno již po prvním vážení - vyhodnotíme nejhorší variantu, tzn. maximální počet vážení pro dané schéma, jinými slovy hledáme minimum mezi maximální hloubkou všech stromů s alespoň 2n + 1 listy.
Lze však ukázat, že neexistuje žádná metoda vážení, která by poskytla rovnost v odhadu (3.1).
VĚTA 3.1
Počet vážení v nejhorším případě pro problém s padělanými mincemi se odhaduje jako l > log
3
(2n + 1).
Důkaz. Jak již bylo zmíněno, pro n mincí existuje 2n + 1 možných výsledků. Každé vážení může mít tři možné výsledky a každý výsledek má svůj vlastní
73
schéma dalšího vážení. Současně má schéma svůj vlastní počet možných výsledků s přihlédnutím k výsledku posledního vážení. Necháme při prvním vážení |S
L
| = |S
R
| = k, tj.
na jedné pánvi se používá k mincí a na druhé k mincí,
kde k ≤ n/2. Pokud ve stejnou dobu S
L
R
, pak mince od S
L
vyhlašujeme kandidáty na lehké padělané mince a mince od S
R
- Kandidáti na těžké padělané mince. Takto,
s výsledkem prvního vážení jsou možné výsledky 2k.
Podobně pro S
L
>S
R
2k jiných výsledků jsou možné. Proto pro S
L
=S
R
zbývajících 2n + 1 − 4k výsledků je možných.
Pokud platí rovnost (3.1), znamená to, že ternární strom je kompletní a všechny jeho listy jsou na l-té úrovni.
K tomu je však nutné, aby po každém vážení byly možné výsledky rovnoměrně rozloženy do tří větví a rovnost
2k = 2n + 1 − 4k,
což je nemožné, protože 2k je vždy sudé číslo a
2n + 1 − 4k je vždy liché.
Při důkazu věty 3.1 byla použita důležitá myšlenka:
Aby byl váhový strom optimální, nebo alespoň co nejblíže optimální, je nutné, aby výsledky byly rovnoměrně rozloženy mezi všechny výsledky každého vážení.
Získali jsme tedy odhad nejhoršího počtu vážení v problému s padělanými mincemi tím, že jsme tento problém spojili s třídou problémů
popsaný ternárními stromy. Nyní zvažte mírně upravený problém.
Problém 3.2 (problém s padělanou mincí za přítomnosti standardu). Existuje n mincí, mezi nimiž může být jeden padělek, a ještě jedna mince, o které se s jistotou ví, že je pravá. Je nutné určit padělanou minci v minimálním počtu vážení nebo zjistit, že neexistují žádné padělané mince.
74
Řešení. Tento problém se od předchozího liší přítomností další referenční mince, ale ukazuje se, že tato další mince umožňuje sestrojit stromy optimální hmotnosti, pro které je splněna rovnost v (3.1). Označme nl
číslo, pro které platí rovnost
3
l
= 2nl
+ 1.
(3.2)
Při zvažování předchozího problému ve větě 3.1 jsme dostali: aby byla splněna rovnost (3.1), musí být váhový strom úplný. Pokud je tedy možné sestavit takový optimální strom l úrovní, pak určí schéma l vah pro n l
mince. Všimněte si, že platí následující vztah:
n l
= 3nl−1
+ 1.
(3.3)
Protože pro n
0
= 0 v (3.2) získáme rovnost, 3 0
= 2 0 + 1,
pak odtud pomocí (3.3) můžeme získat n
1
= 1,n
2
=
4, n
3
= 13 atd. Řešením (3.2) je posloupnost
0, 1, 4, 13, 40, . . ..
Když tedy platí rovnost (3.2), množina n
l mincí je rozděleno na tři stejné části n l−1
mincí a zbývá ještě jedna mince. Podívejme se na různé situace, které mohou nastat během procesu vážení.
Schéma 1. Nechť na začátku vážení máme n i
mince, kde n i
patří do sekvence (3.3) pro některé i. Položme n i−1
mince, kde n
i
= 3n i−1
+ 1,
pak přidáme referenční minci na levou misku vah a jednu ze zbývajících n i−1
+ 1 mince. Označte vážené množiny jako dříve S
L
a S
R
Nyní jako výsledek vážení S
L
=S
R
. Vzhledem k tomu, že se referenční mince účastnila vážení, je zřejmé, že padělaná mince, pokud existuje, patří mezi nepoužité n
i−1
mincí a problém se redukuje na problém s n i−1
mince. V čem
75
V důsledku vážení máme stále možné 2n i−1
+ 1 =
3
i−1
výsledky. Nyní nechme S
L
R
. To znamená, že padělaná mince je buď v sadě S
L
a zároveň je lehčí než ostatní, nebo v sadě S
R
a pak je těžší než ostatní.
Navíc je jich n i−1
podezřelé lehké mince a n i−1
+ 1 podezřele těžké a dohromady to dává opět 2n i−1
+ 1 = 3
i−1
možné výsledky.
Nakonec ať S
L
>S
R
. Pak máme n i−1
kandidáty na těžké mince a n i−1
+1 kandidátů na plíce a celkem 2n i−1
+1 =
3
i−1
výsledky. Takže s takovým schématem prvního vážení vlastně dostaneme 3
i počáteční výsledky byly rovnoměrně rozděleny podle výsledků vážení. Chcete-li zjistit, zda je možné nastavit schéma vážení tak, aby byly výsledky po každém vážení rozděleny na stejný počet částí, zvažte výsledky vážení. Pochopitelně pro S
L
=S
R
dostáváme se ke stejnému problému, jen s menším rozměrem a vážení můžeme vždy provést znovu podle schématu 1, ale s menší hodnotou i.
Schéma 2. Nechť nyní S
L
R
. V tomto případě definujeme strategii vážení následovně. Počáteční údaj je, že v některém kroku i v posloupnosti vážení máme 3
i
= 2n i
+ 1 mince, mezi nimi n i
lehké padělky kandidátů a n i
+ 1 kandidátů na těžké, zatímco počet n i
je číslo formuláře (3.3)
n i
= 3n i−1
+ 1.
Na každou misku váhy položte n i−1
snadní kandidáti a n
i−1
+1 těžký. Protože existují pouze 2n i
+1 = 2(3n i-1
+1)+1 = 6n i−1
+3
mincí a vážit
2n i−1
+ 2n i−1
+ 2 = 4n i−1
+ 2
mincí, pak jsou ještě 2n i−1
+ 1 mince, z toho n i−1
+ 1
plíce a n i−1
těžký. Vzhledem k tomu, že na obou vahách je stejný počet lehkých a těžkých mincí, pak pokud váhy nejsou vyvážené,
to dává n i−1
kandidáti na lehké mince (z misky, která se ukázala jako lehčí) a n i−1
+ 1 kandidát na těžké (z mísy, která se ukázala být
76
těžší). Tím se dostáváme k původním datům stejného schématu
(schéma 2), ale pro 3
i−1
= 2n i−1
+ 1 mince. Pokud jsou váhy vyvážené, pak to znamená, že musíme hledat falešnou minci mezi neváženými n i−1
+ 1 plíce a n i−1
těžké mince, což odpovídá schématu 3. Je zřejmé, že 2n i−1
+1 výsledky, tzn. opět je soubor všech možných výsledků rozdělen na tři stejné části.
Schéma 3. Nechť nyní S
L
>S
R
. V tomto případě máme 3
i
=
2n i
+ 1 mince, mezi nimi n i
+ 1 lehké padělky kandidátů a n i
kandidáty těžké váhy. Všechny argumenty jsou podobné schématu 2, s tím rozdílem, že při vážení je potřeba dát n i−1
+ 1 snadní kandidáti a n i−1
těžký. Pokud váhy nejsou vyvážené, opět nám to dává vzorec 3 za 3
i−1
mincí, jinak získáme podmínky pro vážení odpovídající schématu 2. Opět platí, že ve všech případech je množina možných výsledků rozdělena na tři stejné části 2n i−1
+ 1.
Máme tedy třikrát
1 2
3
=
>
=
=
Rýže. 3.4. Přechody mezi schématy vážení v problému padělaných mincí v osobním stavu popsaném výše a pravidlem vážení pro každý stát. Podle výsledku vážení přecházíme do jiného stavu (nebo zůstáváme ve stejném stavu), ale za menší počet mincí. Při každém vážení je počet možných výsledků rovnoměrně rozdělen podle výsledků vážení. Schéma přechodů mezi stavy je na Obr. 3.4. Příklad vážení pro 27 mincí je na Obr. 3.5.
77
Dokažte, že šachovnice je 10X10 nelze rozřezat podél čar mřížky na obdélníky 1X4. (Řešení podle D.Yu. Kuzněcova.)
Řešení 1 . Desku rozdělte na 2x2 čtverce a vybarvěte je do šachovnicového vzoru (obr. 1). Všimněte si, že libovolný obdélník 1x4 obsahuje stejně (2) černé a bílé buňky, ale s tímto vybarvením je na desce 52 černých a 48 bílých, tzn. ne stejně. To znamená, že nebude možné rozřezat desku 10x10 na obdélníky 1x4.
Řešení 2 . Desku vybarvíme diagonálním vybarvením ve 4 barvách (obr. 2). Všimněte si, že libovolný obdélník obsahuje jednu buňku každé ze čtyř barev, ale při daném vybarvení je na desce 25 buněk 1. a 3. barvy, 26 buněk 2. a 24 buněk 4., tzn. ne stejně. To znamená, že nebude možné rozřezat desku 10x10 na obdélníky 1x4.
1. Ze šachovnice vystřihněte buňky pravého a levého dolního rohu. Je možné výslednou figurku rozřezat na 1x2 domino? A když střihnete vpravo dole a vlevo nahoře?
2. Je možné rozřezat desku 6x6 na domino tak, aby mezi nimi bylo přesně 11 vodorovných? (Vodorovné zbarvení ve dvou barvách.)
3. Vybarvěte kresbu čtyřmi barvami tak, aby sousední části byly namalovány různými barvami. Dá se vystačit se třemi barvami? (Viz Aktivita 6: Vybarvování zeměpisná mapa- třída 5-6).
4. Ve čtverci 4x4 jsou buňky levé poloviny natřeny černě a zbytek bíle. V jedné operaci je povoleno přebarvit všechny buňky uvnitř libovolného obdélníku na opačnou barvu. Jak získat šachové zbarvení z původního zbarvení ve třech operacích?
5. Několik kobylek sedí na stejné přímce a vzdálenosti mezi sousedy jsou stejné. Každou minutu jeden z nich skočí do bodu, který je k němu symetrický vzhledem k jiné kobylce. Může se kobylka Sasha po nějaké době dostat na místo, kde na začátku seděl jeho soused Lyosha?
6. a) Je možné rozřezat šachovnici na figury sestávající ze 4 buněk ve tvaru písmene "T"?
b) Je možné rozřezat šachovnici 10x10 na takové figury?
7. Je možné rozdělit čtverec 8x8 s odříznutým rohem na obdélníky 1x3?
8. Lze desku 10x10 rozřezat na kusy po čtyřech buňkách ve tvaru písmene "L"? (Vodorovné zbarvení ve dvou barvách.)
9. Deska 8x8 se rozřeže na domino 2x1. Může být 15 vertikálních a 17 horizontálních domino?
10. Trojúhelník je rozdělen na trojúhelníky (25 kusů), jak je znázorněno na obrázku. Brouk může chodit v trojúhelníku a pohybovat se mezi sousedními (postranními) trojúhelníky. Jaký je maximální počet trojúhelníků, kterými může brouk projít, pokud nenavštívil každý trojúhelník více než jednou?
11. Jaký je největší počet kosočtverců, z nichž každý je tvořen dvěma rovnostrannými trojúhelníky se stranou 1, které lze vystřihnout z rovnostranného trojúhelníku se stranou 5 (viz obrázek předchozí úlohy).
12. Trojúhelníkový zámek je rozdělen na 100 stejných trojúhelníkových sálů. Uprostřed každé stěny jsou dveře. Kolik místností může navštívit osoba, která nechce nikam více než jednou?
Kapitola 2 šachovnice
Pro podrobný popis šachové matematiky, kterou právě začínáme, je nejpřirozenější začít matematické problémy o šachovnici samotné, aniž by na ni byly umístěny figurky. Právě tomuto tématu je věnována tato kapitola.
Podívejme se nejprve na několik problémů pokrytí desky 2 × 1 domino. Všude se předpokládá, že každé domino pokrývá dvě pole hrací desky a každé pole je pokryto jednou polovinou kostek domina. Začněme dalším starým problémem.
Je možné dominou obložit čtverec o velikosti 8×8, ze kterého jsou vyříznuty protilehlé rohové buňky (obr. 2a)?
Mohli bychom použít algebraické uvažování, ale „šachové“ řešení je jednodušší a elegantnější. Vybarvíme náš zkrácený čtverec černobíle a uděláme z něj šachovnici bez dvou rohových polí a8 a h1 (obr. 2b). Při jakémkoli pokrytí hrací desky pokrývá každé domino jeden bílý a jeden černý čtverec. Máme o dvě bílá pole méně než černá (ořezaná pole jsou bílá), a proto neexistuje potřebné pokrytí! Jak vidíme, zbarvení šachovnice nejen usnadňuje orientaci šachisty během hry, ale slouží také jako prostředek k řešení matematických problémů.
V uvažovaném problému nebylo důležité, aby rohová pole byla z desky vyříznuta, ale aby byla stejné barvy. Je jasné, že ať si vystřihnete dvojici jednobarevných políček, zbytek hrací plochy domino nepokryjete. Vyvstává tedy následující problém.
Předpokládejme nyní, že na šachovnici jsou vyříznuta dvě pole různých barev. Je vždy možné pokrýt zbytek hrací plochy 31 domino?
Ukazuje se, že vždy. Velkolepý důkaz našel slavný americký matematik R. Gomory. Nakreslete na šachovnici hranice mezi vertikálami a horizontálami, jak je znázorněno na obr. 3. V bludišti mezi těmito hranicemi na sebe navazují černá a bílá pole, která se střídají jako knoflíky dvou barev na uzavřené niti (cesta, po které lze toto bludiště obejít, je uzavřena). Ať vystřihneme z desky kterákoli dvě pole různých barev, nit se přetrhne: na jednom místě, pokud jsou vyříznutá pole vedle sebe, a na dvou místech jinak. V tomto případě bude každý kus vlákna sestávat ze sudého počtu polí. V důsledku toho mohou být tyto figurky, a tím i celá hrací deska, pokryty dominem!
Rýže. 3. Labyrint Gomory |
Zajímavé nápady týkající se tlačítek a vláken najdete v kapitole 11.
Předpokládejme, že některá pole jsou vyříznuta ze šachovnice, takže na její zbývající část nelze umístit domino. Je snadné zkontrolovat, že nejmenší počet vyříznutých polí s touto vlastností je 32 - všechna jsou to pole stejné barvy (bílá nebo černá).
Problémy šachovnice a domino jsou jen malou částí z obrovské řady problémů tohoto druhu. Americký matematik S. Golomb vytvořil celou vědu, kterou nazval polymipo, a jeho kniha na toto téma byla přeložena v mnoha zemích světa, včetně té naší. Obecně platí, že polyomino je jednoduše spojená postava sestávající ze čtverců. Z pohledu šachisty jednoduché spojení znamená, že všechna polyomino pole lze obejít tahem věže. V závislosti na počtu čtverců 07 se polyominoes dodávají v různých kvalitách. Monomino obsahuje jeden čtverec, domino dva, tromino tři, tetramino čtyři, pentomino pět, heptomino šest čtverců a tak dále. Zastavíme se ještě u několika otázek souvisejících s obyčejnou šachovnicí. Je zřejmé, že není možné pokrýt dssk pouze rovnými trominoe, tj. domino 3 × 1, protože 64 není dělitelné 3. Vzniká následující problém.
Je možné pokrýt šachovnici 21 rovnými tromino a jedním monominem? Pokud ano, jaká pole může monomino obsadit?
Jeden z nezbytných dapo povlaků na Obr. 4a. Abychom určili možná uspořádání monominos, nakreslíme na desku dva systémy rovnoběžných čar, jak je znázorněno na obr. 4b.
Je snadné vidět, že pro jakoukoli krytinu každé trino pokrývá přesně jedno pole, kterým prochází plná čára, a přesně jedno, kterým prochází přerušovaná čára. Protože počet polí protínaných plnými čarami je 22, stejně jako počet polí protínaných přerušovanými čarami a je jich 21 tromino, mohou monominos pokrýt pouze pole protnutá oběma skupinami čar. A taková pole jsou jen čtyři: c3, c6, f3 a f6! Otočením desky o 90, 180 a 270° můžete získat odpovídající pokrytí pro každé z těchto čtyř polí.
Další úkol je poněkud odlišný od výše uvedených.
Je možné pokrýt šachovnici domino tak, že není možné nakreslit jedinou hranici mezi svislicí a vodorovnou rovinou, aniž by se kostky domino překročily?
Pokud si představíme, že deska je zeď a domino jsou cihly, pak existence zadané hranice (švy) ukazuje na křehké zdivo. Jinými slovy, problém se ptá, zda je možné uspořádat "cihly" tak, aby se "zeď" nezhroutila. Obdélník, který lze zakrýt požadovaným způsobem, se nazývá "silný". "Síla" šachovnice je vidět na Obr. 5. V obecném případě Gardner ukazuje, že domino lze složit do „silného“ obdélníku, pokud je jeho plocha rovná a jeho délka a šířka jsou větší než čtyři, s jedinou výjimkou, kterou je čtverec 6 × 6.
Níže se budeme často zabývat obdélníkovými šachovnicemi té či oné velikosti. V tomto případě se vždy předpokládá, že deska m×n má m vertikál a n horizontál (šachy). Říkáme, že hrací plocha je „sudá“, pokud je počet jejích polí sudý, a jinak „lichá“. Všude tam, kde nejsou uvedeny rozměry šachovnice, máme na mysli standardní šachovnici, pro kterou m = n = 8.
Deska 100x4 je pokryta kostkami domina. Dokažte, že lze řezat podél jedné z hranic mezi vertikálami a horizontálami, aniž by to ovlivnilo kteroukoli z kostek domina.
Libovolná ze zadaných hranic rozděluje desku na dvě části sestávající ze sudého počtu polí. Pole každé části rozdělujeme do dvou tříd: kryté domino ležící zcela v této části a kryté domino protnuté hranicí. Protože počet polí každé části je sudý (možná nula), stejně jako počet polí první třídy (každé domino pokrývá dvě pole), je počet polí druhé třídy sudý. A to znamená, že počet kostek domina protnutých hranicí je sudý. Existuje celkem 102 dělicích hranic (99 vertikálních a 3 horizontální), a pokud každá z nich překračuje domino, pak se pokrytí účastní minimálně 102 × 2 = 204 kostek domina. Máme jich jen 200! Ve skutečnosti jsme ukázali, že obdélník 100x4 je „slabý“.
Otázku možnosti pokrytí libovolné obdélníkové desky lineárními k-mino (domina k × 1) řeší následující věta.
Deska m×n může být pokryta lineárními k-mino tehdy a jen tehdy, když je alespoň jedno z čísel m nebo n dělitelné k beze zbytku.
Větu ilustrujeme na následujícím příkladu.
Je možné pokrýt desku 10x10 (na takové desce se hraje sto čtverečních dám) rovnými tetraminy?
Rovné tetramino má rozměry 4x1, což znamená, že v zásadě by 25 dlaždic mohlo pokrýt všechna pole naší desky. Z věty však vyplývá, že to není možné - 10 není dělitelné 4.
Podívejme se na několik dalších problémů o šachovnici. Při řešení následujícího problému viovb je použito jeho zbarvení.
Nechť se deska skládá z lichého počtu polí. Na každé jeho pole nějaké položíme šachová figurka. Je možné všechny tyto figurky přesunout na sousední pole (svisle nebo vodorovně), aby žádné dvě neskončily na stejném poli?
Úkol je nemožný. Pokud by naznačené posunutí kusů existovalo, pak by se každý "bílý" kus (stojící na bílém poli) stal "černým" (padl na černé pole) a každý "černý" - "bílý".
Deska by se tedy skládala ze stejného počtu bílých a černých polí, což je v rozporu s její „podivností“.
Populární jsou problémy řezání šachovnice. Nejznámější z nich je následující, kterou vlastní S. Loyd.
Na polích a1, b2, c3, d4 jsou čtyři rytíři. Rozřízněte desku na čtyři shodné části (shodné při překrývání) tak, aby každá z nich měla koně.
Při problémech s řezáním se vždy předpokládá, že řezy se provádějí pouze podél hranic mezi svislicemi a vodorovnými rovinami desky. Řešení tohoto problému je znázorněno na Obr. 6. Od dob Loyda se na toto téma objevilo mnoho nových a složitějších problémů. Zejména byly řešeny problémy rozřezání desky na čtyři shodné díly pro různé pozice rytířů (rytíři zde samozřejmě hrají pouze symbolickou roli). V této otázce je stále mnoho nevyřešených problémů. Například stále není znám počet způsobů, jakými lze běžnou desku (bez kusů) rozřezat na dva shodné kusy.
Rýže. 6. Loydův problém čtyř koní |
Po několika řezech desky necháme výsledné díly posunout tak, aby další řez mohl řezat ne jeden, ale několik dílů najednou. Kolik škrtů bude potřeba k získání 64 jednotlivých políček na desce (1×1 pole)?
Nejprve desku rozřízneme napůl, poté obě poloviny položíme vedle sebe a desku rozřežeme na čtyři stejné díly atd. Celkem bude potřeba 6 řezů (2 e \u003d 64) a menší počet nelze obejít .
Nyní je dovoleno řezat části desky pouze samostatně. Kolik řezů bude potřeba k získání 64 polí v tomto případě?
Tento úkol (zejména pokud je navržen po předchozím) zpravidla způsobuje určité potíže. Zřejmě je to způsobeno určitou setrvačností našeho myšlení. Vždyť je hned jasné, že bude potřeba 63 řezů! Každý řez totiž zvyšuje počet dílů o jeden; současně máme v počátečním okamžiku jednu část (samotná deska) a v konečném okamžiku - 64 (všechna pole desky).
Rýže. 7. Tři problémy na neobvyklé desce |
V úloze na Obr. 7a, musíte splnit tři úkoly, jeden matematický a dva čistě šachové:
a) rozřízněte desku na čtyři shodné části;
b) při tahu bílého dám černému králi nejkratší cestou mat;
c) dát černému králi mat nejkratším způsobem, zatímco černý tahá, věřící hrají kooperativně).
Řešení: a) jak řezat desku, jak je znázorněno na obr. 7b; b) když bílý táhne, dává mat ve 12. tahu: 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 (všechny tahy černého krále jsou vynucené a nejsou dány); c) při správné hře po 1. ... Ke6-e7 mat je nemožný, protože černý král se schovává na e8 - 2. Be1-b4+ Ke7-e8 a střelec s tmavým čtvercem je nucen opustit úhlopříčku a3 - e7 kvůli hrozbě patové situace. Pokud však černý hraje kooperativně (pomáhá bílému mat), pak je cíle dosaženo za pouhé tři tahy:
1. … Ke6-d6
2. Ke3-d4 Ke6-e7
3. Be1-b4+ Ke7-e6
4. Pár Be4-d5.Řada polí našeho prkna se při páření nepoužívá, ale pokud by byly vyloučeny, nebyl by problém prkno nařezat.
Rýže. 8. Paradox s řezáním šachovnice: a) 8×8 = 64; b) 13×5 = 65 |
Podívejme se nyní na jeden známý paradox spojený s řezáním šachovnice. Desku rozřízneme na čtyři části, jak je znázorněno na obr. 8, a (v tomto případě je pro nás nerentabilní barvit jeho pole) a z výsledných částí přidáme obdélník (obr. 8, b). Plocha desky je 64 a plocha výsledného obdélníku je 65. Při řezání desky tedy odněkud přišlo jedno pole navíc!
Řešením paradoxu je, že naše kresby nejsou úplně přesné (schválně jsme nakreslili tlusté čáry, abychom skryli nepřesnosti). Při pečlivé konstrukci výkresu na Obr. 8b se místo úhlopříčky obdélníku objeví kosočtvercový, mírně protáhlý obrazec se stranami, které jako by téměř splynuly. Plocha tohoto obrázku se bude rovnat pouze „extra“ jednotce.
Známý popularizátor matematiky na počátku století E. Ignatiev přišel s „metodou šachovnice“, která umožňuje odvodit různé vzorce. Na toto téma uvádíme dva jednoduché příklady.
Najděte součet prvních n přirozených čísel pomocí „šachovnicové metody“. K tomu na hrací ploše (n + 1) × n (na obr. 9 a n = 8) vybarvíme všechna pole první svislice, všechna pole druhé svislice (kromě horní), třetí vertikální (kromě dvou horních) atd. d., konečně - spodní pole n-té vertikální. Výsledkem je, že bílá a černá pole na naší desce budou stejná, konkrétně 1 + 2 + ... + n. Protože se celá deska skládá z n (n + 1) polí, dostáváme
2 (1 + 2 + … + n) = n(n + 1),
odkud následuje známý vzorec pro součet aritmetické posloupnosti:
1 + 2 + … + n = n(n + 1)/2.
Nyní dokažme následující vzorec:
8(1 + 2 + ... + n) + 1 = (2n + 1)².
Chcete-li to provést, vezměte desku (2n + 1) × (2n + 1) a natřete řadu jejích polí černou barvou, jak je znázorněno na obr. 9, 6 (pro případ n = 5). Je zřejmé, že každá černá část obsahuje (1 + 2 + ... + n) polí. Aniž bychom vzali v úvahu centrální pole, máme zde čtyři stejné bílé a černé části. Požadovaný vzorec vyplývá ze skutečnosti, že naše deska obsahuje (2n + 1)² polí a skládá se z centrálního pole a osmi stejných částí (čtyři bílé a čtyři černé - obr. 9b).
Při rozluštění paradoxu, stejně jako při seznamování se s „šachovnicovou metodou“, lze samotnou desku bezpečně nahradit listem kostkovaného papíru nebo stolem. Problémů s takovými předměty je obrovské množství, ale jejich podrobné zvážení by nás od šachů příliš vzdálilo.
Na závěr kapitoly uvádíme jeden starý důkaz na šachovnici... Pythagorovy věty. Nakreslete na desku čtverec, jak je znázorněno na obr. 10, a. Deska je rozdělena na tento čtverec a čtyři shodné pravoúhlé trojúhelníky. Na Obr. 10, 6 vidíme stejné čtyři trojúhelníky a také dva čtverce. Trojúhelníky tedy v obou případech zabírají stejnou plochu. V důsledku toho zbývající části desky bez trojúhelníků zabírají stejnou plochu, na obr. 10,a - jeden čtverec a na Obr. 10b - dva. Vzhledem k tomu, že velký čtverec je postaven na přeponě pravoúhlého trojúhelníku a malé čtverce jsou na jeho nohách, pak "Pythagorejské kalhoty jsou stejné ve všech směrech"!
Samozřejmě, přísně vzato, naše úvaha Pythagorovu větu nedokazuje (byl studován pouze konkrétní případ), ale pouze ji ilustruje. Ale takový důkaz se obejde bez použití šachovnice – pro jakýkoli pravoúhlý trojúhelník si můžete vybrat pole, které se láme podobným způsobem.
Právě toto řešení je uvedeno v knize T. Saatiho "Integer Optimization Methods and Related Extremal Problems" (M., "Mir", 1973).
S. Golomb. Polyomino. M., Mir, 1974.
Prokázal to A. Soifer v článku „Dražkované desky a polymipo“ („Kvant“, 1972, č. 11); je zde také uvedena řada nových polyominových problémů.
E. Ignatiev. V oblasti vynalézavosti nebo aritmetiky pro každého. Rezervovat. 1 - 3. M. - Str., Gosizdat, 1923.
V této lekci si povíme o omalovánkách a o tom, jak pomáhají řešit problémy. Zvažte nestandardní problémy s řezáním a obklady a způsoby jejich řešení.
Shrnutí lekce "Řezání. Teselace. Barvení."
Omalovánky. Řezání. Teselace.
Mnoho vědců se již od starověku zabývalo řezáním problémů. Řešení mnoha jednoduchých problémů s řezáním našli staří Řekové a Číňané, ale první systematické pojednání na toto téma napsal Abul-Vef, slavný perský astronom z 10. století, který žil v Bagdádu. Geometrové se vážně zabývali řešením problémů rozřezávání obrazců na nejmenší počet dílů a poté z nich skládání té či oné nové postavy až na počátku 20. století. Jedním ze zakladatelů tohoto fascinujícího odvětví geometrie byl slavný kompilátor hádanek Henry E. Dudeney. Obzvláště velký počet již existujících čísel lámajících rekordy překonal odborník z australského patentového úřadu Harry Lindgren. Je předním řezačem postav.
Dnes milovníci hlavolamů rádi řeší střihové problémy, především proto, že neexistuje žádná univerzální metoda na řešení takových problémů a každý, kdo se ujme jejich řešení, může plně prokázat svou vynalézavost, intuici a schopnost kreativně myslet. Vzhledem k tomu, že zde nejsou vyžadovány žádné hluboké znalosti geometrie, mohou amatéři někdy dokonce překonat profesionální matematiky.
Abychom dokázali, že je možné vyřešit problém řezání nějaké postavy na části, stačí poskytnout nějaký způsob řezání. Najít všechna řešení, tedy všechny způsoby řezání, je trochu složitější. A dokázat, že řezání je nemožné, je už docela obtížné. V některých případech nám k tomu pomáhá vybarvování postavy.
Úkol 1: Vzali jsme čtverec kostkovaného papíru o rozměrech 8 × 8, odřízli jsme z něj dvě buňky (vlevo dole a vpravo nahoře). Je možné výsledný obrazec zcela pokrýt "domino" - 1 × 2 obdélníky?
Úkol 2. Je možné rozložit šachovnici s dvaatřiceti domino tak, že 17 z nich je umístěno vodorovně a 15 svisle?
Úkol 3: Je možné uříznout čtverec kostkovaného papíru na velikost
4×4 na jeden podstavec, jeden čtverec, jeden sloup a jeden klikatý?
Úkol 4: Je možné rozložit čtverec 8×8 pomocí 15 obdélníků 1×4 a jednoho pohledu?
Úkol 5: Je možné rozložit obdélník 6×10 obdélníky 1×4?
Úkol 6: Je možné složit čtverec 6×6 pomocí 11 obdélníků 1×3 a jednoho pohledu?
Úkol 7: Na každé buňce desky 5 × 5 je brouk. V určitém okamžiku všichni brouci vzlétnou a přistanou na sousedních buňkách na straně. Dokažte, že bude alespoň jeden prázdnou klec.
Úkol 8: Z desky 8×8 vyřízněte rohovou klec. Lze zbytek rozřezat na obdélníky 3×1?
Úkol 9: Figurka velblouda se pohybuje po šachovnici tahem jako (1, 3). Je možné přesunout „velblouda“ z libovolného pole na sousední?
Úkol 10: Může být deska 10 × 10 pokryta figurkami ve formě?
Úkol 11: Dáno pole o rozměrech 12 × 12. V levém dolním rohu je 9 dám, které tvoří pole 3 × 3. V jednom tahu si můžete vybrat dvě dámy a jednu z nich přeskupit symetricky vzhledem k druhé (aniž byste opustili hrací plochu) . Je možné posunout tuto dámu několika tahy tak, aby tvořily pole 3 × 3 v pravém dolním rohu?
Úkol 12: V každé buňce čtverce 9 × 9 je brouk. Na povel letí každý brouk do jedné z diagonálně sousedících buněk. Dokažte, že alespoň 9 buněk pak bude volných.
Úkol 13: Zámek má tvar pravidelného trojúhelníku, rozděleného na 25 malých sálů stejného tvaru. V každé stěně mezi chodbami byly vyrobeny dveře. Cestovatel se prochází po zámku, aniž by některý ze sálů navštívil vícekrát. Najděte největší počet sálů, které může navštívit. 
Úkol 14:Jaký je maximální počet kosočtverců, které lze rozřezat na rovnostranný trojúhelník rozdělený na 36 rovnostranných trojúhelníků?
Úkol 15. Ve čtverci 7x7 je 16 dlaždic 1x3 a jedna dlaždice 1x1. Dokažte, že dlaždice 1×1 leží buď uprostřed, nebo sousedí s hranicemi čtverce.
Úkol 16. V levém dolním rohu šachovnice 8×8 je umístěno devět žetonů ve tvaru pole 3×3. Čip může skočit do volného pole přes blízký čip, to znamená, že se může odrážet symetricky kolem svého středu (můžete skákat vertikálně, horizontálně a diagonálně). Je možné při určitém počtu takových tahů umístit všechny žetony znovu ve formě pole 3 × 3, ale do jiného rohu?
