Logiška užduotis dėti domino ant šachmatų lentos. Matematikos olimpiados ir olimpiados uždaviniai
Duota 8×8 šachmatų lenta, iš kurios buvo išpjauti du įstrižai priešingi kampai, ir 31 domino kauliukas; kiekvienas domino gali uždengti du langelius ant lentos. Ar galima išasfaltuoti visą lentą kaulais? Pateikite savo atsakymo pagrindimą.
Sprendimas
Iš pirmo žvilgsnio atrodo, kad tai įmanoma. Lenta 8×8, vadinasi, yra 64 langeliai, išskiriame dvi, vadinasi, lieka 62. Atrodo, turėtų tilpti 31 kaulas, ar ne?
Kai bandome išdėstyti domino kauliukus pirmoje eilėje, turime tik 7 langelius, vienas kaulas eina į antrą eilę. Tada antroje eilėje dedame domino ir vėl viena plytelė eina į trečią eilę.
Kiekvienoje eilėje visada bus vienas kaulas, kurį reikės perkelti į kitą eilutę, kad ir kiek išdėstymų bandytume, visų kaulų niekada nepavyks išdėlioti.
Šachmatų lenta yra padalinta į 32 juodus ir 32 baltus langelius. Pašalinus priešingus kampus (atkreipkite dėmesį, kad šios ląstelės yra tos pačios spalvos), mums lieka 30 vienos spalvos langelių ir 32 kitos spalvos langeliai. Tarkime, kad dabar turime 30 juodų ir 32 baltų kvadratų.
Kiekvienas kauliukas, kurį messime ant lentos, užims vieną juodą ir vieną baltą langelį. Todėl 31 domino kauliukas užims 31 baltą ir 31 juodą langelį. Tačiau mūsų lentoje yra tik 30 juodų ir 32 baltų langelių. Todėl kaulų suskaidyti neįmanoma.
Analizė paimta iš G. Luckman McDowell knygos vertimo ir skirta tik informaciniams tikslams.
Jei patiko, rekomenduojame įsigyti knygą.
6. Dėžutėje yra 235 degtukai. Du žaidėjai juos pasiima paeiliui. Vienu judesiu galite paimti nuo 1 iki 6 degtukų. Žaidėjas laimi
imant paskutines rungtynes. Kas laimi, kai žaidžia teisingai?
62
7. Iš 8 × 8 lentos išpjaunamas kampinis kvadratas. Ar galima lentą iškloti 1×3 stačiakampiais?
8. Iš 30 rungtynių du žaidėjai savo nuožiūra paima iš 1
iki 6 rungtynių. Laimi tas, kuris laimi paskutines rungtynes.
9. Yra trys akmenų krūvos. Būsena yra skaičių trigubas
(x
1
, x
2
, x
3
), kur x i
- akmenų skaičius i-oje krūvoje. Perkėlimas – tai akmenų skaičiaus perkėlimas iš krūvos į krūvą, lygus akmenų skaičiui krūvoje, kurioje perkeliama. Iš pradinės būsenos (11, 7, 6) gaukite būseną (8, 8, 8).
10. Padalinkite apskritimą į maksimalų dalių skaičių, naudodami keturias tiesias linijas.
11. Iškirpkite graikišką kryžių dviem tiesiomis linijomis taip, kad
iš gautų dalių suformuoti stačiakampį, kurio viena kraštinė yra dvigubai didesnė už kitą.
12. 9 yra 12 litrų skysčių ir tuščių indų tiekimas
ir 5 l. Būtina išmatuoti tiksliai 6 litrus. Kiek litrų galima išmatuoti tokiais indais iš 12 litrų rezervo?
13. Nustatykite n ilgio sekų skaičių iš (0, 1, 2),
kurioje nėra dviejų iš eilės einančių vienetų.
14. Ar galima 10 × 10 kvadratą uždengti formos figūrėlėmis
15. Ar galima 10 × 10 kvadratą uždengti formos figūrėlėmis
63
16. Ar galima uždengti 8×8 kvadratą su iškirpta kampine ląstele su formos figūromis
17. Ar galima figūrėlėmis uždengti 8 × 8 šachmatų lentą, kurioje išpjautas kvadratas:
18. Ar galima pakloti šachmatų lentą su raižytu kampiniu narvu su formos gabalėliais
19. Ar galima dviejų žmonių valtimi perplaukti keturias riterių-kvailių poras, jei stribas negali būti viename krante su svetimu (-iais) riteriu (-iais), nesant šeimininko?
20. Sukurkite algoritmą, kaip rasti du mažiausius skaičius netvarkingoje n skaičių sekoje.
21. Iš 27 ant stalo gulinčių rungtynių du žaidėjai pakaitomis surenka bent vieną ir ne daugiau kaip keturias rungtynes. Laimi tas, kuris žaidimo pabaigoje turės lyginį rungtynių skaičių. Sukurkite pirmojo žaidėjo žaidimo algoritmą.
64
22. Du žaidimo dalyviai paeiliui skambina numeriu nuo 1 iki 10.
Skambindamas numeriu, žaidėjas jį prideda prie jau esančios skaičių sumos (skambinęs pirmuoju numeriu, žaidėjas prideda jį prie nulio). Žaidėjas, surinkęs 100 taškų, laimi.
Sukurkite pirmojo žaidėjo žaidimo algoritmą.
23. Raskite minimalų klausimų skaičių (galimi atsakymai:
„taip“, „ne“) paslėptas 5 skaitmenų skaičius, jei pirmųjų trijų skaitmenų suma yra 17.
24. Raskite minimalų klausimų skaičių (galimi atsakymai:
„taip“, „ne“) paslėptas 4 skaitmenų skaičius, jei antrojo ir ketvirtojo skaitmenų suma yra 7.
25. Keliais būdais galima pakeisti 100 rublių? monetos viduje
5, 10, 20 ir 50 rublių?
26. Rekursyviai apskaičiuokite šešiaženklių skaičių, kurių pirmųjų keturių skaitmenų suma yra 26, o paskutinių dviejų skaitmenų suma yra 14.
27. Rekursyviai apskaičiuokite skaičiaus 37 skaidinių skaičių penkiais nariais, iš kurių pirmasis neviršija 7, antrasis
- 5, o trečiasis ir ketvirtasis paima reikšmes iš rinkinio
{5, 6, 7, 8}.
28. Rekursyviai apskaičiuokite septynių skaitmenų skaičių, kurių pirmųjų keturių skaičių suma lygi 21, o paskutinių penkių – 19.
29. Skaičiaus 27 skyrių skaičių rekursyviai apskaičiuokite keturiais nariais, iš kurių pirmasis neviršija 7,
antrasis yra 8, o trečiasis ir ketvirtasis paima reikšmes iš rinkinio (3, 5, 7).
30. Rekursyviai apskaičiuokite penkių skaitmenų skaičių, kurių pirmieji trys skaitmenys sudaro 21, o paskutiniai trys skaitmenys sudaro 12.
65
31. Rekursyviai apskaičiuokite septynių skaitmenų skaičių, kurių pirmojo ir trečiojo skaitmenų suma lygi 12, o likusių penkių – 19.
32. Apskaičiuokite rekursyviai
(2n − 2)(2n − 4) × . . . ×2
(n + 1) (n + 3) × . . . × (n + 2n – 1)
a n-5
b
− (n+3)
33. Rekursyviai apskaičiuokite septynių skaitmenų skaičių, kurių pirmųjų keturių skaitmenų suma yra 17, o paskutinių trijų skaitmenų suma yra 16.
34. Rekursyviai apskaičiuokite skaičiaus 17 skaidinių skaičių keturiais nariais, iš kurių pirmasis neviršija 4, antrasis - 8, o trečiasis ir ketvirtasis ima reikšmes (3, 4, 8).
35. Rekursyviai apskaičiuokite septynženklių skaičių, kurių pirmųjų keturių skaičių kvadratų suma lygi 17, o paskutinių dviejų – 16.
36. Skaičiaus 25 skyrių skaičių rekursyviai apskaičiuokite keturiais nariais, iš kurių pirmasis neviršija 8,
antrasis yra 3, o trečiasis ir ketvirtasis paima reikšmes iš rinkinio (2, 5, 9).
37. Rekursyviai apskaičiuokite N bokšto vietų skaičių lentoje
N × N taip, kad bokštai būtų simetriški abiejų įstrižainių atžvilgiu ir nepultų vienas kito.
38. Rekursyviai apskaičiuokite n elementų dvejetainių sekų, kuriose trūksta dviejų gretimų, skaičių.
39. Duota gardelė N × M:
66
M
N
A
B
Rekursyviai apskaičiuokite takų skaičių nuo A iki B. Kelias yra judesių seka tinkleliu, einanti iš kairės į dešinę ir iš apačios į viršų.
40. Pateikti skaičiai a
1
, . . . , a n
tam tikra tvarka. Norėdami apskaičiuoti produktą a
1
·. . a n
išlaikant veiksnių tvarką, yra daug būdų, kaip pateikti skliaustus tarp veiksnių. Rekursyviai apskaičiuokite skliaustų išdėstymo būdų skaičių.
41. Rekursyviai apskaičiuokite 8 skaitmenų skaičių, kurių pirmųjų penkių skaitmenų suma yra 29, o paskutinių trijų skaitmenų suma yra 21.
67
3
. algoritminės analizės metodai
3.1. Algoritmų klasės
Ankstesniuose skyriuose aptarėme skirtingus metodus, kurie gali būti naudojami kuriant algoritmus. Norint rasti sprendimą, išanalizuoti šio sprendimo efektyvumą, galima kelti įvairias prielaidas, naudoti jau žinomus kitus algoritmus, performuluoti problemos būklę ir pan. Galite ieškoti panašių problemų su žinomu sprendimu ir naudoti šį sprendimą, kad surastumėte reikiamos problemos algoritmą.
Tačiau yra daug konkrečių problemų, kurioms buvo rasti sprendimai. Dar daugiau užduočių yra neišspręstų arba išspręstų su tam tikrais apribojimais ir sąlygomis. Panašių problemų paieška tarp visų problemų, esamų sprendimų įvertinimas pagal jų „tinkamumo“ laipsnį gali būti sudėtinga, daug laiko reikalaujanti ir ne visada išsprendžiama problema. Būtų naudingiau ir produktyviau pabandyti apibrėžti problemų klases, kurias vienija bendra problema, bendri metodai ir sprendimo būdai, o tada ieškoti klasės, kuriai galima priskirti mūsų konkrečią problemą, kurią reikia išspręsti. Žinoma, tokių užsiėmimų neturėtų būti per daug, bet, kita vertus, jų neturėtų būti per mažai, kad kiekviena nauja užduotis apibrėžkite savo naują klasę, kuri greičiausiai nebus naudojama kitoms problemoms spręsti.
Kaip tam tikrai klasei priklausančios problemos pavyzdį apsvarstykite gerai žinomą padirbtos monetos atpažinimo problemą.
3.1 užduotis (problema apie padirbta moneta). Yra n monetų,
tarp kurių gali būti vienas netikras. Padirbta moneta nuo likusios skiriasi svoriu, o mes turime svarstykles su dviem puodeliais. Būtina nustatyti padirbtą monetą minimaliam svėrimų skaičiui arba nustatyti,
kad nėra padirbtų monetų.
68
Sprendimas. Padirbtų monetų problema buvo išspręsta sek. 2.2,
bet tada buvo žinoma, kad padirbta moneta būtinai buvo lengvesnė. Dabar pabandykime išspręsti šią problemą bendresniu atveju. Bet koks šios problemos sprendimas (nebūtinai optimalus)
gali būti interpretuojama kaip svėrimų seka. Tačiau akivaizdu, kad monetų pasirinkimas sverti bet kuriame žingsnyje priklauso nuo to, kokios monetos buvo naudojamos, ir nuo svėrimo rezultatų ankstesniuose žingsniuose. Svėrimų seką pavaizduosime taip. Pernumeruojame monetas ir apibrėžiame jas kaip aibę S = (1, 2, . . . , n). Kairėje ir dešinėje svarstyklių lėkštėse sveriamų monetų skaičių rinkiniai gali būti pažymėti S
L
ir S
R
atitinkamai. Akivaizdu, kad svoriai yra prasmingi tik tuo atveju, jei aibių kardinalumas S
L
ir S
R
rungtynės, t.y. Kiekvienoje svarstyklėje yra tiek pat monetų. Svėrimas bus pažymėtas ženklu ":", tada kiekvienas svėrimas
(S
L
): (S
R
) yra trys galimi rezultatai. Daug monetų
S
L
gali būti lengvesnis, sunkesnis arba tokio pat svorio kaip rinkinys S
R
. Tada šiuos svorio rezultatus pažymėsime kaip
"" arba "=", atitinkamai. Keturių monetų svėrimo pavyzdys parodytas fig. 3.1. Ovalai žymi svėrimą, kvadratai – rezultatus, nurodant padirbtos monetos numerį ir tai, ar ji lengvesnė ar sunkesnė už kitas.
Atvejis, kai monetos nėra padirbtos, žymimas „0“, perbraukti kvadratai atitinka atvejus, kurių negali būti.
Įvertinsime maksimalų svėrimų skaičių, reikalingą problemai išspręsti, t.y. blogiausiu atveju. Kaip matyti iš fig. 3.1, problema išsprendžiama 3 svėrimais blogiausiu atveju. Atminkite, kad net geriausiu atveju mums reikia bent 2
svėrimas. Ar galima pasiekti geresnį rezultatą?
Ant pav. 3.1 pateikia dar vieną keturių monetų svėrimo problemos sprendimą. Pirmuoju žingsniu pasveriame ne porą monetų, o visas monetas, padalijame jas į du rinkinius. Dėl to mes pasiekėme, kad geriausiu atveju reikia tik vieno svėrimo,
tačiau blogiausiu atveju svėrimų skaičius vėl yra 3.
69
(1) : (2)
(1) : (3)
(1) : (4)
04 T
4 l
3 T
3 l
(1) : (4)
2 T
1 l
(1) : (4)
2 L
1 T
=
=
=
>
>
>
>
>
=
=
Ryžiai. 3.1. Padirbtų monetų problemos sprendimas
Atkreipkite dėmesį, kad, priešingai nei pirmoji svėrimo parinktis,
parodyta pav. 3.1, antroje versijoje ne tik apibrėžėme svėrimo schemą, bet ir pristatėme naują padirbtų monetų kandidatų koncepciją. Iš tiesų, apsvarstykite pirmojo svėrimo rezultatą (1, 2): (3, 4). Tegul (1, 2) L
= (1, 2) ir S
R
= (3, 4). Tada
S
L
R
. Iš šio rezultato negalima spręsti, ar padirbta moneta yra lengvesnė ar sunkesnė už visas kitas,
ir kokiame rinkinyje jis yra. Tačiau galima manyti
(o dar tiksliau – galima ginčytis), kad jei padirbta moneta priklauso rinkiniui S
L
, tada padirbta moneta yra lengvesnė už kitas, tokį rinkinį žymime raide L. Mūsų atveju, jei monetos su skaičiais 1 arba 2 yra padirbtos, tai jos yra lengvesnės už tikras. Jei padirbta moneta su skaičiais 3 arba
4, tada jie yra sunkesni už tikrus, atitinkamą aibę žymėsime raide T. Pav. 3.2 lengvi ir sunkūs padirbiniai kandidatai nurodomi žymomis ant medžio kraštų.
Akivaizdu, kad į klausimą apie optimalų svėrimų skaičių galima atsakyti ir toliau rūšiuojant galimas monetų pasirinkimo schemas. Kadangi monetų skaičius yra baigtinis, anksčiau ar vėliau toks surašymas gali būti baigtas. Kol kas apsistokime ties dviem gautais sprendimais ir pabandykime išanalizuoti, ką jie davė
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
=
=
>
>
>
=
02L
(3) : (4)
3 l
4 l
(1) : (2)
2 T
=
>
>
=
1 T
Ryžiai. 3.2. Kitas padirbtos monetos problemos sprendimas mums bendro požiūrio į problemos sprendimą požiūriu.
Kaip žinoma, bet kurią monetų svėrimo strategiją galima apibūdinti naudojant trijų ar trijų dalių medį. Kitaip tariant, nagrinėjama problema priklauso problemų klasei,
apibūdinti trišakiais medžiais. Tokia problemos klasifikacija leidžia analizuoti ne kiekvieną konkretų sprendimą, o visus sprendimus apskritai, remiantis žinomomis medžių savybėmis.
Taigi, iteracija baigta galimi būdai svėrimas iš tikrųjų yra paieška per įvairius trinarius medžius, kurių, žinoma, yra eksponentiškai daug. Kita vertus, pabandykime nustatyti, ką apskritai įmanoma pasiekti sprendžiant tam tikrą problemą, naudojant jos priklausymą tai konkrečiai klasei.
Iš pav. 3.1 ir 3.2 matyti, kad vaizduojant svėrimų seką naudojant medį, kiekvieną svėrimą priskiriame medžio viršūnei, kuri nėra lapas (pavaizduota naudojant ovalus), o rezultatus, įskaitant neįmanomus,
atitiko medžio lapus (parodyta kvadratais). Visus medžio mazgus galima rūšiuoti pagal lygius,
71
AT
a
=
=
>
AT
a
Ir
Ir
Ir
=
>
AT
a
Ir
Ir
Ir
=
>
AT
a
Ir
Ir
Ir
=
>
AT
a
Ir
Ir
Ir
=
>
AT
a
=
>
AT
a
=
>
AT
a
>
Į
AT
L
At
0
At
1
At
l
-
1
At
l
……
………………
………
…
…
……
…
…
…
…
…
……
……
…
…
G
a =
l
Ryžiai.
3.3.
T
pavasario svorio medis
72
tie. pagal atstumą nuo medžio šaknies. Lygio skaičius yra lygus briaunų skaičiui, kuris turi praeiti nuo šaknies, kad patektų į viršūnę. duoto lygio(3.3 pav.). Jei medžio gylis yra toliausiai nuo šaknies esančio lapo lygis, tada ši reikšmė yra lygi svorių skaičiui blogiausiu atveju.
Kiek galimų pasekmių yra mūsų problema? Kiekviena iš n monetų gali pasirodyti kaip netikra lengva arba netikra sunki moneta, o netikrų monetų gali nebūti.
Taigi, mes turime 2n + 1 rezultatus. Tai reiškia, kad medyje
atitinkanti svėrimo schemą, turi būti bent
2n + 1 lapai. Trečiame l gylio medyje yra daugiausia,
nei 3
l lapai. Iš to galime įvertinti mažiausią įmanomą medžio gylį
3
l
≥ 2n + 1,
taigi
l ≥ žurnalas
3
(2n + 1).
(3.1)
Taigi, esant n = 4, mažiausias galimas svėrimų skaičius yra didesnis arba lygus 2. Čia turime omenyje ne minimalų šios schemos svėrimų skaičių – kaip pav. 3.2, o pasitaiko atvejų, kai problemos sprendimas randamas jau po pirmo svėrimo – įvertiname patį blogiausią variantą, t.y. maksimalus svorių skaičius pagal pateiktą schemą, kitaip tariant, mes ieškome minimumo tarp didžiausių visų medžių, turinčių ne mažiau kaip 2n + 1 lapų, gylių.
Tačiau galima įrodyti, kad nėra svorių metodo, kuris suteiktų įverčio lygybę (3.1).
TEOREMA 3.1
Svėrimų skaičius blogiausiu atveju dėl padirbtų monetų problemos yra įvertintas kaip l > log
3
(2n + 1).
Įrodymas. Kaip jau minėta, n monetų galimi 2n + 1 rezultatai. Kiekvienas svėrimas gali turėti tris galimus rezultatus, ir kiekvienas rezultatas turi savo
73
tolesnio svėrimo schema. Tuo pačiu metu schema turi savo galimų rezultatų skaičių, atsižvelgiant į paskutinio svėrimo rezultatą. Tegul pirmojo svėrimo metu |S
L
| = |S
R
| = k, t.y.
vienoje lėkštėje naudojama k monetų, o kitoje - k monetų,
kur k ≤ n/2 . Jei tuo pat metu S
L
R
, tada monetos iš S
L
skelbiame kandidatus į lengvąsias padirbtas monetas, o monetas iš S
R
- Kandidatai į sunkias padirbtas monetas. Šiuo būdu,
su pirmo svėrimo rezultatu galimi 2k rezultatai.
Panašiai ir S
L
>S
R
Galimi 2k kiti rezultatai. Todėl dėl S
L
=S
R
galimi likę 2n + 1–4k rezultatai.
Jei (3.1) galioja lygybė, tai reiškia, kad trijų dalių medis yra baigtas ir visi jo lapai yra l lygyje.
Bet tam būtina, kad po kiekvieno svėrimo galimi rezultatai būtų paskirstyti tolygiai per tris šakas ir lygybę
2k = 2n + 1–4k,
o tai neįmanoma, nes 2k visada yra lyginis skaičius ir
2n + 1 − 4k visada yra nelyginis.
Įrodant 3.1 teoremą buvo panaudota svarbi mintis:
Kad svėrimo medis būtų optimalus arba bent kiek įmanoma arčiau optimalaus, būtina, kad rezultatai būtų tolygiai paskirstyti visiems kiekvieno svėrimo rezultatams.
Taigi, mes gavome blogiausio svėrimų skaičiaus padirbtų monetų problemos apskaičiavimą, susiedami šią problemą su problemų klase.
apibūdinti trišakiais medžiais. Dabar apsvarstykite šiek tiek pakeistą problemą.
3.2 uždavinys (problema dėl padirbtos monetos esant standartui). Yra n monetų, tarp kurių gali būti viena padirbta, ir dar viena moneta, apie kurią tikrai žinoma, kad ji tikra. Padirbtą monetą reikia nustatyti minimaliu svėrimų skaičiumi arba nustatyti, kad padirbtų monetų nėra.
74
Sprendimas. Ši problema nuo ankstesnės skiriasi tuo, kad yra papildoma etaloninė moneta, tačiau paaiškėja, kad ši papildoma moneta leidžia sukurti optimalaus svorio medžius, kuriems tenkinama (3.1) lygybė. Pažymėti n l
skaičius, kuriam galioja lygybė
3
l
= 2n l
+ 1.
(3.2)
Nagrinėdami ankstesnę 3.1 teoremos problemą, gavome: kad (3.1) lygybė būtų patenkinta, svorių medis turi būti baigtas. Todėl, jei įmanoma sukurti tokį optimalų l lygių medį, jis nurodys l svorių schemą n l
monetos. Atkreipkite dėmesį, kad šis ryšys yra teisingas:
n l
= 3nl−1
+ 1.
(3.3)
Kadangi už n
0
= 0 in (3.2), gauname lygybę, 3 0
= 2 0 + 1,
tada iš čia naudodami (3.3) galime gauti n
1
= 1,n
2
=
4,n
3
= 13 ir tt Sprendimas (3.2) yra seka
0, 1, 4, 13, 40, . . ..
Taigi, kai galioja lygybė (3.2), aibė n
l monetos dalijamos į tris lygias dalis n l−1
monetų ir dar liko viena moneta. Panagrinėkime įvairias situacijas, kurios gali kilti svėrimo metu.
Schema 1. Tegul svėrimo pradžioje turime n i
monetos, kur n i
priklauso sekai (3.3) kai kurioms i. Padėkime n i−1
monetos, kur n
i
= 3n i−1
+ 1,
tada pridedame pamatinę monetą į kairę svarstyklių dalį ir vieną iš likusių n i−1
+ 1 moneta. Pažymėkite svertines aibes, kaip ir anksčiau, S
L
ir S
R
Dabar tegul pasvėrus S
L
=S
R
. Kadangi etaloninė moneta dalyvavo sveriant, akivaizdu, kad padirbta moneta, jei tokia yra, yra tarp nepanaudotų n.
i-1
monetų, o problema redukuojama į problemą su n i−1
monetos. Kuriame
75
Dėl svorio vis dar turime 2n i−1 įmanomą
+ 1 =
3
i-1
rezultatus. Dabar tegul S
L
R
. Tai reiškia, kad padirbta moneta yra arba rinkinyje S
L
ir tuo pačiu yra lengvesnis nei kiti, arba rinkinyje S
R
ir tada jis yra sunkesnis už kitus.
Be to, yra n i−1
įtartinos šviesos monetos ir n i−1
+ 1 įtartinas sunkus ir kartu tai vėl duoda 2n i−1
+ 1 = 3
i-1
galimus rezultatus.
Galiausiai leiskite S
L
>S
R
. Tada turime n i−1
sunkiųjų monetų kandidatai ir n i−1
+1 kandidatai į plaučius ir iš viso 2n i−1
+1 =
3
i-1
rezultatus. Taigi, naudojant tokią pirmojo svėrimo schemą, iš tikrųjų gauname 3
i pradiniai rezultatai buvo tolygiai paskirstyti pagal svėrimo rezultatus. Norėdami nustatyti, ar galima nustatyti svėrimo schemą taip, kad po kiekvieno svėrimo rezultatai būtų padalinti į vienodą skaičių dalių, atsižvelkite į svėrimo rezultatus. Akivaizdu, kad S
L
=S
R
pasiekiame tą pačią problemą, tik su mažesniu matmeniu, ir visada galime pakartotinai atlikti svorius pagal 1 schemą, bet su mažesne i reikšme.
2 schema. Dabar S
L
R
. Šiuo atveju svorio strategiją apibrėžiame taip. Pradiniai duomenys yra tai, kad tam tikrame svorių sekos etape i turime 3
i
= 2n i
+ 1 monetos, tarp kurių n i
lengvi padirbti kandidatai ir n i
+ 1 kandidatai į sunkųjį, o skaičius n i
yra (3.3) formos skaičius
n i
= 3n i−1
+ 1.
Uždėkite ant kiekvienos svarstyklių lėkštės n i−1
lengvi kandidatai ir n
i-1
+1 sunkus. Kadangi yra tik 2n i
+1 = 2(3n i-1
+1)+1 = 6n i−1
+3
monetų ir pasverti
2n i-1
+ 2n i−1
+ 2 = 4n i−1
+ 2
monetų, tada dar yra 2n i−1
+ 1 monetos, tarp kurių n i−1
+ 1
plaučiai ir n i−1
sunkus. Kadangi ant abiejų svarstyklių yra tiek pat lengvų ir sunkių monetų, jei svarstyklės nėra subalansuotos,
tai duoda n i−1
kandidatai į šviesias monetas (iš dubenėlio, kuris pasirodė lengvesnis) ir n i−1
+ 1 kandidatas į sunkųjį (iš dubenėlio, kuris pasirodė esąs
76
sunkesnis). Taip pateksime į pradinius tos pačios schemos duomenis
(2 schema), bet 3
i-1
= 2n i−1
+ 1 moneta. Jei svarstyklės yra subalansuotos, tai reiškia, kad turime ieškoti padirbtos monetos tarp nesvertų n i−1
+ 1 plaučiai ir n i−1
sunkiųjų monetų, o tai atitinka 3 schemą. Akivaizdu, kad 2n i−1
+1 rezultatai, t.y. vėlgi visų galimų baigčių aibė padalinama į tris lygias dalis.
3 schema. Dabar S
L
>S
R
. Šiuo atveju turime 3
i
=
2n i
+ 1 monetos, tarp kurių n i
+ 1 lengvas padirbtas kandidatas, ir n i
sunkiasvorių kandidatų. Visi argumentai yra panašūs į 2 schemą, su skirtumu, kad sveriant reikia įdėti n i−1
+ 1 lengvas kandidatas, o n i−1
sunkus. Jei svarstyklės nėra subalansuotos, tai vėl suteikia mums modelį 3 už 3
i-1
monetų, kitu atveju gauname svėrimo sąlygas, atitinkančias 2 schemą. Vėlgi visais atvejais galimų baigčių aibė padalinama į tris lygias 2n i−1 dalis.
+ 1.
Taigi turime tris kartus
1 2
3
=
>
=
=
Ryžiai. 3.4. Aukščiau aprašytos asmeninės būklės padirbtų monetų problemos svorių schemų ir kiekvienos valstybės svorio taisyklės perėjimai. Priklausomai nuo svėrimo rezultato pereiname į kitą būseną (arba liekame toje pačioje būsenoje), bet už mažesnį monetų skaičių. Kiekvieno svėrimo metu galimų rezultatų skaičius tolygiai paskirstomas pagal svėrimo rezultatus. Perėjimų tarp būsenų schema parodyta fig. 3.4. 27 monetų svėrimo pavyzdys parodytas fig. 3.5.
77
Įrodykite, kad šaškių lenta yra 10X10 negalima iškirpti išilgai tinklelio linijų į stačiakampius 1X4. (Sprendimai pagal D.Ju. Kuznecovą.)
Sprendimas 1 . Padalinkite lentą į 2x2 kvadratus ir nuspalvinkite juos šaškių lentos raštu (1 pav.). Atkreipkite dėmesį, kad bet kuriame 1x4 stačiakampyje yra vienodai (2) juodos ir baltos spalvos langeliai, tačiau naudojant šį dažymą, lentoje yra 52 juodi ir 48 balti langeliai, t.y. ne vienodai. Tai reiškia, kad 10x10 lentos nebus galima iškirpti į 1x4 stačiakampius.
Sprendimas 2 . Nuspalvinkime lentą įstriža spalvomis 4 spalvomis (2 pav.). Atkreipkite dėmesį, kad bet kuriame stačiakampyje yra po vieną langelį iš kiekvienos iš keturių spalvų, tačiau su tam tikra spalva lentoje yra 25 1 ir 3 spalvų langeliai, 26 2 ir 24 4 langeliai, t.y. ne vienodai. Tai reiškia, kad 10x10 lentos nebus galima iškirpti į 1x4 stačiakampius.
1. Iš šachmatų lentos iškirpkite apatinį dešinįjį ir kairįjį kampinius langelius. Ar įmanoma gautą figūrą supjaustyti į 1x2 domino kauliukus? O jei nupjausite apačią dešinę ir viršutinę kairę?
2. Ar galima 6x6 lentą supjaustyti domino kauliukais, kad tarp jų būtų lygiai 11 horizontalių? (Dviejų spalvų horizontalus dažymas.)
3. Nuspalvinkite piešinį keturiomis spalvomis, kad gretimos dalys būtų nudažytos skirtingomis spalvomis. Ar įmanoma apsieiti su trimis spalvomis? (Žr. 6 užsiėmimą: dažymas geografinis žemėlapis- 5-6 klasė).
4. 4x4 kvadrate kairiosios pusės langeliai nudažyti juodai, o likusi dalis balta. Vienos operacijos metu leidžiama perspalvinti visas bet kurio stačiakampio viduje esančias ląsteles priešinga spalva. Kaip gauti šachmatų dažymą iš originalaus dažymo per tris operacijas?
5. Keli amūrai sėdi toje pačioje tiesėje, o atstumai tarp kaimynų yra vienodi. Kiekvieną minutę vienas iš jų peršoka į jam simetrišką tašką kito žiogo atžvilgiu. Ar po kurio laiko žiogas Saša gali atsidurti toje vietoje, kur pradžioje sėdėjo jo kaimynas Lioša?
6. a) Ar galima šachmatų lentą supjaustyti figūrėlėmis, sudarytomis iš 4 langelių „T“ raidės pavidalu?
b) Ar galima išpjauti 10x10 šachmatų lentą į tokias figūras?
7. Ar galima 8x8 kvadratą su nupjautu kampu padalinti į 1x3 stačiakampius?
8. Ar galima 10x10 lentą supjaustyti į keturias „G“ raidės formos ląsteles? (Dviejų spalvų horizontalus dažymas.)
9. 8x8 lenta supjaustoma į 2x1 domino kauliukus. Ar gali būti 15 vertikalių ir 17 horizontalių domino?
10. Trikampis padalintas į trikampius (25 vnt.), kaip parodyta paveikslėlyje. Vabalas gali vaikščioti trikampiu, judėdamas tarp gretimų (šoninių) trikampių. Kiek daugiausiai trikampių gali praeiti vabalas, jei kiekviename trikampyje apsilankė ne daugiau kaip vieną kartą?
11. Kiek daugiausia rombų, kurių kiekvienas sudarytas iš dviejų lygiašonių trikampių, kurių kraštinė yra 1, gali būti iškirpta iš lygiakraščio trikampio, kurio kraštinė yra 5 (žr. ankstesnio uždavinio paveikslą).
12. Trikampė pilis padalinta į 100 vienodų trikampių salių. Kiekvienos sienos viduryje yra durys. Kiek kambarių gali aplankyti nenorintis niekur daugiau nei vieną kartą?
2 skyrius šachmatų lenta
Išsamią šachmatų matematikos apžvalgą, kurią netrukus pradėsime, natūraliausia pradėti matematikos uždaviniai apie pačią lentą, dar nedėdami ant jos jokių gabalėlių. Būtent šiai temai ir skirtas šis skyrius.
Pirmiausia panagrinėkime keletą problemų, susijusių su lentos uždengimu 2 × 1 domino kauliukais. Visur daroma prielaida, kad kiekvienas domino kauliukas dengia du lentos langelius, o kiekvieną kvadratą dengia pusė domino. Pradėkime nuo kitos senos problemos.
Ar galima domino kauliukais uždengti 8×8 dydžio kvadratą, iš kurio išpjaunamos priešingos kampinės ląstelės (2a pav.)?
Galėtume naudoti algebrinius samprotavimus, tačiau „šachmatų“ sprendimas yra ir paprastesnis, ir elegantiškesnis. Nuspalvinkime savo nupjautą kvadratą juodai baltai, paversdami jį šachmatų lenta be dviejų kampinių laukelių a8 ir h1 (2b pav.). Bet kokiai lentos dangai kiekvienas domino kauliukas dengia vieną baltą ir vieną juodą kvadratą. Turime dviem mažiau baltų laukų nei juodų (iškirpti laukai balti), todėl nėra reikiamos aprėpties! Kaip matome, lentos spalvinimas ne tik palengvina šachmatininkui orientavimąsi žaidimo metu, bet ir pasitarnauja kaip priemonė sprendžiant matematinius uždavinius.
Nagrinėjamoje užduotyje buvo svarbu ne tai, kad iš lentos būtų išpjauti kampiniai laukai, o kad jie būtų vienodos spalvos. Aišku, kad ir kaip iškirptumėte porą vienspalvių laukelių, likusios lentos dalies domino kauliukais uždengti nepavyks. Taigi iškyla tokia problema.
Tarkime, kad šachmatų lentoje yra iškirpti du skirtingų spalvų laukai. Ar visada įmanoma likusią lentos dalį uždengti 31 domino kauliuku?
Pasirodo, kad visada. Įspūdingą įrodymą rado garsus amerikiečių matematikas R. Gomory. Nubrėžkime ant šachmatų lentos ribas tarp vertikalių ir horizontalių, kaip parodyta pav. 3. Labirinte tarp šių kraštų juodi ir balti laukai seka vienas kitą, kaitaliojasi tarsi dviejų spalvų mygtukai ant uždaro siūlo (takas, kuriuo galima apeiti šį labirintą, uždarytas). Kad ir kokius du skirtingų spalvų laukus iškirptume iš lentos, siūlas nutrūks: vienoje vietoje, jei nupjauti laukai greta, ir dviejose – kitaip. Tokiu atveju kiekvieną siūlą sudarys lyginis skaičius laukų. Vadinasi, šios detalės, taigi ir visa lenta, gali būti padengtos domino kauliukais!
Ryžiai. 3. Labirintas Gomoris |
Įdomių idėjų, susijusių su mygtukais ir siūlais, rasite 11 skyriuje.
Tarkime, kad kai kurie laukai yra iškirpti iš šachmatų lentos, kad ant likusios jos dalies nebūtų galima uždėti domino. Nesunku patikrinti, ar mažiausias iškirptų laukelių skaičius su šia savybe yra 32 – tai visi tos pačios spalvos (baltos arba juodos) laukai.
Šachmatų lentos ir domino problemos yra tik maža dalis daugybės tokio pobūdžio problemų. Amerikiečių matematikas S. Golombas sukūrė ištisą mokslą, kurį pavadino polimipu, o jo knyga šia tema buvo išversta daugelyje pasaulio šalių, tarp jų ir mūsų. Apskritai poliomino yra tiesiog sujungta figūra, susidedanti iš kvadratų. Žvelgiant iš šachmatų žaidėjo požiūrio, buvimas tiesiog sujungtu reiškia, kad visus poliomino langelius galima apeiti stačiakampio judesiu. Priklausomai nuo 07 kvadratų skaičiaus, poliominai būna skirtingų klasių. Monomino yra vienas kvadratas, domino du, tromino trys, tetramino keturi, pentomino penki, heptomino šeši kvadratai ir pan. Aptarsime dar keletą klausimų, susijusių su įprasta šachmatų lenta. Akivaizdu, kad dssk neįmanoma uždengti tik tiesiais tromino kauliukais, t. y. domino kauliukais 3 × 1, nes 64 nesidalija iš 3. Iškyla tokia problema.
Ar galima uždengti šachmatų lentą su 21 tiesiu tromino ir vienu monomino? Jei taip, kokius laukus gali užimti monominas?
Viena iš būtinų dapo dangų pav. 4a. Norėdami nustatyti galimus monominų išdėstymus, lentoje nubrėžiame dvi lygiagrečių linijų sistemas, kaip parodyta fig. 4b.
Nesunku pastebėti, kad bet kokioje dangoje kiekvienas trominas apima tiksliai vieną lauką, per kurį eina ištisinė linija, ir tiksliai vieną, per kurią eina punktyrinė linija. Kadangi laukų, kertamų ištisinėmis linijomis, skaičius yra 22, taip pat laukų, kertamų punktyrinėmis linijomis, skaičius ir yra 21 trominas, monominos gali apimti tik tuos laukus, kuriuos kerta abi linijų šeimos. Ir tokių kvadratų yra tik keturi: c3, c6, f3 ir f6! Pasukus plokštę 90, 180 ir 270°, galite gauti atitinkamą kiekvieno iš šių keturių laukų aprėptį.
Kita užduotis šiek tiek skiriasi nuo aukščiau aptartų.
Ar įmanoma šachmatų lentą uždengti domino kauliukais taip, kad nebūtų įmanoma nubrėžti vienos ribos tarp vertikalių ir horizontalių, nekertant domino?
Jeigu įsivaizduosime, kad lenta yra siena, o domino kauliukai – plytos, tai nurodytos kraštinės (siūlės) buvimas rodo trapų mūrą. Kitaip tariant, problema klausia, ar galima „plytas“ sutvarkyti taip, kad „siena“ nesugriūtų. Stačiakampis, kurį galima uždengti reikiamu būdu, vadinamas „stipriu“. Šachmatų lentos „jėgą“ galima pamatyti pav. 5. Bendru atveju Gardneris parodo, kad domino kauliukus galima sulankstyti į „stiprų“ stačiakampį, jei jo plotas lygus, o ilgis ir plotis yra didesni nei keturi, išskyrus 6 × 6 kvadratą.
Žemiau mes dažnai kalbėsime apie vienokio ar kitokio dydžio stačiakampes šachmatų lentas. Šiuo atveju visada daroma prielaida, kad m × n lentoje yra m vertikalių ir n horizontalių (šachmatai). Mes sakome, kad lenta yra „lyginė“, jei jos laukų skaičius yra lyginis, o kitaip „nelyginis“. Ten, kur lentos matmenys nenurodyti, turime omenyje standartinę šachmatų lentą, kuriai m = n = 8.
100x4 lenta padengta domino kauliukais. Įrodykite, kad jį galima iškirpti išilgai vienos iš vertikalių ir horizontalių ribų nepažeidžiant domino.
Bet kuri iš nurodytų kraštinių padalija lentą į dvi dalis, susidedančias iš lyginio skaičiaus laukų. Kiekvienos dalies laukus suskirstome į dvi klases: uždengtus domino kauliukus, kurie yra visiškai šioje dalyje, ir dengtus domino kauliukus, susikertančius su riba. Kadangi kiekvienos dalies laukelių skaičius yra lyginis (galbūt nulis), taip pat pirmosios klasės laukelių skaičius (kiekvienas domino kauliukas dengia du laukus), antrosios klasės laukelių skaičius yra lyginis. O tai reiškia, kad domino kauliukų, peržengtų ribą, skaičius yra lygus. Iš viso yra 102 skiriamosios ribos (99 vertikalios ir 3 horizontalios), o jei kiekviena iš jų kerta domino kauliukus, tai aprėptyje dalyvauja mažiausiai 102 × 2 = 204 domino kauliukai. Jų turime tik 200! Tiesą sakant, mes parodėme, kad 100x4 stačiakampis yra „silpnas“.
Klausimas dėl galimybės savavališką stačiakampę lentą padengti tiesiniais k-minos (domino kauliukai k × 1) sprendžiamas tokia teorema.
M×n lenta gali būti padengta tiesiniais k-minos tada ir tik tada, kai bent vienas iš skaičių m arba n dalijasi iš k be liekanos.
Teoremą iliustruojame tokiu pavyzdžiu.
Ar galima 10x10 lentą (ant tokios lentos žaidžiama šimtas kvadratinių šaškių) uždengti tiesia tetramino?
Tiesus tetramino matmenys yra 4x1, tai reiškia, kad iš esmės 25 plytelės galėtų padengti visus mūsų lentos laukus. Tačiau iš teoremos išplaukia, kad tai neįmanoma – 10 nesidalija iš 4.
Panagrinėkime dar keletą problemų, susijusių su šachmatų lenta. Sprendžiant šią problemą vivb naudojamas jo dažymas.
Tegul lenta susideda iš nelyginio laukų skaičiaus. Kiekviename jo lauke mes įdėsime keletą šachmatų figūrėlė. Ar galima visas šias figūras perkelti į gretimus langelius (vertikaliai arba horizontaliai), kad dvi iš jų neatsidurtų tame pačiame langelyje?
Užduotis neįmanoma. Iš tiesų, jei nurodytas gabalų poslinkis egzistuotų, tai kiekviena „balta“ gabalėlis (stovintis baltame lauke) taptų „juodas“ (kristų ant juodo lauko), o kiekvienas „juodas“ – „baltas“.
Taigi lentą sudarytų tiek pat baltų ir juodų laukų, o tai prieštarauja jos „keistumui“.
Populiarios yra šachmatų lentos pjovimo problemos. Garsiausias iš jų yra šis, priklausantis S. Loydui.
Laukuose a1, b2, c3, d4 yra keturi riteriai. Supjaustykite lentą į keturias lygias dalis (sutampa, kai dedama), kad kiekvienoje iš jų būtų arklys.
Pjovimo uždaviniuose visada daroma prielaida, kad pjūviai atliekami tik išilgai ribos tarp lentos vertikalių ir horizontalių. Šios problemos sprendimas parodytas fig. 6. Nuo Loydo laikų šia tema atsirado daug naujų ir sunkesnių problemų. Visų pirma, skirtingoms riterių pozicijoms buvo išspręstos lentos pjaustymo į keturias lygias dalis problemos (riteriai, žinoma, čia atlieka tik simbolinį vaidmenį). Šiuo klausimu vis dar yra daug neišspręstų problemų. Pavyzdžiui, vis dar nežinoma, kiek būdų įprastą lentą (be gabalų) galima supjaustyti į dvi lygias dalis.
Ryžiai. 6. Loydo keturių arklių problema |
Leiskite, po kelių lentos pjūvių gautas dalis paslinkti taip, kad kitą pjūvį būtų galima pjauti ne vieną, o kelias dalis iš karto. Kiek reikės pjūvių, kad gautumėte 64 atskirus lentos tarpus (1 × 1 kvadratas)?
Pirmiausia perpjauname lentą per pusę, tada sudedame abi puses ir supjaustome lentą į keturias identiškas dalis ir pan. Iš viso reikės 6 pjūvių (2 e \u003d 64), o mažesnio skaičiaus atsisakyti negalima .
Dabar lentos dalis leidžiama pjauti tik atskirai. Kiek reikės pjūvių, kad gautumėte 64 laukus šiuo atveju?
Paprastai ši užduotis (ypač jei ji siūloma po ankstesnės) sukelia tam tikrų sunkumų. Matyt, taip yra dėl tam tikros mūsų mąstymo inercijos. Juk iš karto aišku, kad reikės 63 pjūvių! Iš tiesų, kiekvienas pjūvis padidina dalių skaičių viena; tuo pačiu metu pradiniu momentu turime vieną dalį (pati lenta), o paskutiniu momentu - 64 (visi lentos laukai).
Ryžiai. 7. Trys problemos neįprastoje lentoje |
Užduotyje pav. 7a, turite atlikti tris užduotis, vieną matematinę ir dvi grynai šachmatų:
a) supjaustykite lentą į keturias lygias dalis;
b) šachmatas su juodu karaliumi trumpiausiu būdu, kai baltas juda;
c) šachmatas su juodu karaliumi trumpiausiu keliu; kol juodas juda, ištikimieji žaidžia bendradarbiaujant).
Sprendimai: a) kaip nupjauti lentą, parodyta pav. 7b; b) Kai baltas juda, šachmatas suteikiamas 12 ėjimu: 1-12. Be1-b4, Ke3-d3-c4, Be4-c2-b3, Kc4-c3, Bb4-d6, Bb3-d5, Kc3-c2, Bd6-c5, Bd5-c4, Bd6-b4šachmatas (visi juodojo karaliaus judesiai yra priverstiniai ir neduodami); c) su teisingu žaidimu po 1. ... Ke6-e7 šachmatas neįmanomas, nes juodasis karalius slepiasi ant e8 - 2. Be1-b4+ Ke7-e8, o tamsaus kvadrato vyskupas yra priverstas palikti a3 - e7 įstrižainę dėl aklavietės grėsmės. Tačiau jei juodu žaidžia bendradarbiaudami (padėdami baltiesiems šachtą), tikslas pasiekiamas vos trimis ėjimais:
1. … Ke6-d6
2. Ke3-d4 Ke6-e7
3. Be1-b4+ Ke7-e6
4. Be4-d5 mate. Nemažai mūsų lentos laukų poravimosi metu nenaudojami, bet juos atmetus, nebūtų problemų nupjauti lentą.
Ryžiai. 8. Paradoksas su šachmatų lentos pjovimu: a) 8×8 = 64; b) 13 × 5 = 65 |
Dabar apsvarstykite vieną gerai žinomą paradoksą, susijusį su šachmatų lentos pjaustymu. Lentą supjaustome į keturias dalis, kaip parodyta pav. 8, a (šiuo atveju mums neapsimoka spalvinti jo laukus), o iš gautų dalių pridėsime stačiakampį (8 pav., b). Lentos plotas yra 64, o gauto stačiakampio plotas yra 65. Taigi, pjaunant lentą, iš kažkur atsirado vienas papildomas laukas!
Paradokso sprendimas yra tas, kad mūsų piešiniai nėra visiškai tikslūs (norėdami paslėpti netikslumus, sąmoningai brėžėme storas linijas). Kruopščiai sukonstruojant brėžinį pav. 8b vietoje stačiakampio įstrižainės atsiras rombo formos, šiek tiek pailgos figūros, kurios šoninės lyg ir beveik susijungusios. Šios figūros plotas bus lygus „papildomam“ vienetui.
Amžiaus pradžioje žinomas matematikos populiarintojas E. Ignatjevas sugalvojo „šachmatų lentos metodą“, leidžiantį išvesti įvairias formules. Pateikiame du paprastus pavyzdžius šia tema.
Raskime pirmųjų n natūraliųjų skaičių sumą „šachmatų lentos metodu“. Norėdami tai padaryti, lentoje (n + 1) × n (9 pav. a n = 8) nuspalviname visus pirmosios vertikalės laukus, visus antrosios vertikalės laukus (išskyrus viršutinę), trečia vertikali (išskyrus dvi viršutines) ir tt d., galiausiai - apatinė laukas nth vertikaliai. Dėl to balti ir juodi laukai mūsų lentoje bus lygūs, būtent 1 + 2 + ... + n. Kadangi visa lenta susideda iš n (n + 1) laukų, gauname
2 (1 + 2 + … + n) = n (n + 1),
iš kur seka gerai žinoma aritmetinės progresijos sumos formulė:
1 + 2 + … + n = n(n + 1)/2.
Dabar įrodykime šią formulę:
8(1 + 2 + ... + n) + 1 = (2n + 1)².
Norėdami tai padaryti, paimkite lentą (2n + 1) × (2n + 1) ir nudažykite keletą jos laukų juodai, kaip parodyta Fig. 9, 6 (atvejui n = 5). Akivaizdu, kad kiekvienoje juodojoje dalyje yra (1 + 2 + ... + n) laukai. Neatsižvelgiant į centrinį lauką, čia yra keturios vienodos baltos ir juodos dalys. Reikalinga formulė išplaukia iš to, kad mūsų lentoje yra (2n + 1)² laukai ir susideda iš centrinio lauko ir aštuonių vienodų dalių (keturios baltos ir keturios juodos - 9b pav.).
Atskleidžiant paradoksą, taip pat susipažįstant su „šachmatų lentos metodu“, pačią lentą drąsiai galima pakeisti languoto popieriaus lapu ar lentele. Su tokiais objektais kyla daugybė problemų, tačiau detalus jų svarstymas nutoltų nuo šachmatų.
Skyriaus pabaigoje pateikiame vieną seną Pitagoro teoremos įrodymą šachmatų lentoje. Ant lentos nupieškite kvadratą, kaip parodyta pav. 10, a. Lenta padalinta į šį kvadratą ir keturis lygiaverčius stačiuosius trikampius. Ant pav. 10, 6 matome tuos pačius keturis trikampius, taip pat du kvadratus. Taigi, abiem atvejais trikampiai užima tą patį plotą. Vadinasi, likusios lentos dalys be trikampių užima tą patį plotą, pav. 10,a - vienas kvadratas, o pav. 10b - du. Kadangi didelis kvadratas pastatytas ant stačiojo trikampio hipotenuzos, o mažieji kvadratai yra ant jo kojų, tai „Pitagoro kelnės yra lygios visomis kryptimis“!
Žinoma, griežtai kalbant, mūsų samprotavimai neįrodo Pitagoro teoremos (buvo tiriamas tik konkretus atvejis), o tik iliustruoja. Tačiau toks įrodymas apsieina ir nenaudojant šachmatų lentos – bet kuriam stačiakampiui trikampiui galima pasirinkti kvadratą, kuris lūžta panašiai.
Būtent toks sprendimas pateiktas T. Saati knygoje „Integer Optimization Methods and Related Extremal Problems“ (M., „Mir“, 1973).
S. Golombas. Poliomino. M., Mir, 1974 m.
Tai įrodė A. Soiferis straipsnyje „Šachtinės lentos ir polimipo“ („Kvant“, 1972, Nr. 11); ten taip pat pateikiama nemažai naujų poliomino uždavinių.
E. Ignatjevas. Išradingumo srityje, arba aritmetikos kiekvienam. Knyga. 1 - 3. M. - Pg., Gosizdat, 1923 m.
Šioje pamokoje kalbėsime apie spalvinimo puslapius ir kaip jie padeda spręsti problemas. Apsvarstykite nestandartines pjovimo ir plytelių klijavimo problemas ir jų sprendimo būdus.
Pamokos "Pjovimas. Teseliacija. Dažymas" santrauka.
Dažymo puslapiai. Pjaustymas. Teseliacijos.
Daugelis mokslininkų nuo seniausių laikų mėgsta spręsti problemas. Daugelio paprastų pjovimo problemų sprendimus rado senovės graikai ir kinai, tačiau pirmąjį sistemingą traktatą šia tema parašė Bagdade gyvenęs garsus X amžiaus persų astronomas Abul-Vefas. Tik XX amžiaus pradžioje geometrai rimtai ėmėsi spręsti figūrų supjaustymo į kuo mažiau dalių skaičių ir iš jų vieną ar kitą naują figūrą. Vienas iš šios žavios geometrijos šakos įkūrėjų buvo garsus galvosūkių sudarytojas Henry E. Dudeney. Ypač daug jau egzistavusių figūrų, kertančių rekordus, sumušė Australijos patentų biuro ekspertas Harry Lindgrenas. Jis yra pirmaujantis figūrų kirpėjas.
Šiandien galvosūkių mėgėjai mėgsta spręsti sudėtingas problemas, visų pirma todėl, kad nėra universalaus metodo tokioms problemoms spręsti, o kiekvienas, kuris imasi jų sprendimo, gali visiškai pademonstruoti savo išradingumą, intuiciją ir gebėjimą kūrybiškai mąstyti. Kadangi čia nereikia gilių geometrijos žinių, mėgėjai kartais gali net pralenkti profesionalius matematikus.
Norint įrodyti, kad įmanoma išspręsti kokios nors figūros supjaustymo į dalis problemą, pakanka pateikti tam tikrą pjovimo būdą. Rasti visus sprendimus, tai yra, visus pjovimo būdus, yra šiek tiek sunkiau. O įrodyti, kad pjaustyti neįmanoma, jau gana sunku. Kai kuriais atvejais tai padaryti padeda figūros spalvinimas.
1 užduotis: Paėmėme languoto popieriaus kvadratą, kurio matmenys yra 8 × 8, iš jo nupjauname dvi langelius (apačioje kairėje ir viršutinėje dešinėje). Ar įmanoma gautą figūrą visiškai uždengti „domino kauliukais“ – 1 × 2 stačiakampiais?
2 užduotis. Ar galima išdėlioti šachmatų lentą su trisdešimt dviem domino kauliukais taip, kad 17 iš jų būtų išdėstyti horizontaliai, o 15 – vertikaliai?
3 užduotis: Ar galima languoto popieriaus kvadratą iškirpti pagal dydį
4×4 vienam postamentui, vienam kvadratui, vienai kolonai ir vienam zigzagui?
4 užduotis: Ar galima išdėlioti 8×8 kvadratą naudojant 15 1×4 stačiakampių ir vieną vaizdo kampą?
5 užduotis: Ar galima išdėlioti 6×10 stačiakampį su 1×4 stačiakampiais?
6 užduotis: Ar galima sulenkti 6×6 kvadratą naudojant 11 1×3 stačiakampių ir vieną vaizdo kampą?
7 užduotis: Kiekvienoje 5 × 5 lentos langelyje yra vabalas. Tam tikru metu visi vabalai pakyla ir nusileidžia ant gretimų ląstelių šone. Įrodykite, kad bus bent vienas tuščias narvas.
8 užduotis: Iš 8 × 8 lentos iškirpkite kampinį narvą. Ar likusią dalį galima supjaustyti į 3 × 1 stačiakampius?
9 užduotis: Kupranugario figūrėlė šachmatų lentoje juda tokiu judesiu kaip (1, 3). Ar galima perkelti „kupranugarį“ iš savavališko lauko į gretimą?
10 užduotis: Ar 10 × 10 lenta gali būti padengta figūromis?
11 užduotis: Duota 12 × 12 lenta. Apatiniame kairiajame kampe yra 9 šaškės, kurios sudaro 3 × 3 kvadratą. Vienu judesiu galite pasirinkti keletą dviejų šaškių ir perstatyti vieną iš jų simetriškai kitos atžvilgiu (neišlipant nuo lentos) . Ar galima šias šaškes perkelti keliais judesiais, kad jos apatiniame dešiniajame kampe sudarytų 3 × 3 kvadratą?
12 užduotis: Kiekvienoje 9 × 9 kvadrato ląstelėje yra vabalas. Įsakymu kiekvienas vabalas skrenda į vieną iš įstrižai gretimų ląstelių. Įrodykite, kad bent 9 langeliai bus laisvi.
13 užduotis: Pilis yra taisyklingo trikampio formos, padalinta į 25 mažas tos pačios formos sales. Kiekvienoje sienoje tarp salių padarytos durys. Keliautojas vaikšto po pilį nė vienoje salėje neapsilankęs daugiau nei vieną kartą. Raskite didžiausią skaičių salių, kurias jis gali aplankyti. 
14 užduotis:Kiek daugiausia rombų galima išpjauti į lygiakraštį trikampį, padalytą į 36 lygiakraščius trikampius?
15 užduotis. 7x7 kvadrate yra 16 1x3 plytelių ir viena 1x1 plytelė. Įrodykite, kad 1 × 1 plytelė yra centre arba greta kvadrato kraštų.
16 užduotis. Apatiniame kairiajame 8 × 8 šachmatų lentos kampe dedami devyni žetonai 3 × 3 kvadrato pavidalu. Lustas gali peršokti į laisvą lauką per šalia esantį lustą, tai yra, jis gali atsispindėti simetriškai apie savo centrą (galite šokinėti vertikaliai, horizontaliai ir įstrižai). Ar įmanoma atlikti tam tikrą skaičių tokių judesių, kad visi žetonai vėl būtų 3 × 3 kvadrato pavidalu, bet kitame kampe.
