Invariantai (šachmatų lentos uždaviniai ir ne tik). A dalis
Įvadas
Pirmiausia panagrinėkime grupę uždavinių, kuriuos galime spręsti invariantų metodu ir kurių dauguma yra susiję su vadinamaisiais „šachmatų lentos“ uždaviniais.
Kaip spręsti?
1 pavyzdys
Turime 8×8 šachmatų lentą ir domino kauliukų rinkinį (1×2 stačiakampiukų). Tarkime, šachmatų lentoje iškirpome vieną jos kampinį langelį. Ar bus įmanoma padengti likusius šachmatų lentos langelius domino kauliukais?
Atsakymas/sprendimas
Be abejo, ne. Iškirpus vieną langelį (nesvarbu kurį), liks 63 langeliai, t. y. nelyginis langelių skaičius. Kaip bedėliotume domino kauliukus, jais galėsime padengti tik lyginį skaičių langelių.
Šis paprastutis uždavinys aiškiai pademonstruoja metodą, leidžiantį spręsti ir kur kas sudėtingesnius uždavinius. Yra daugybė uždavinių, kuriuose reikia kažką išsiaiškinti apie galutinę „sistemos“ būseną, kai ją („sistemą“) galima įvairiai keisti (šiuo atveju galėjome visaip kaitalioti domino kauliukų išdėstymą; turėjome išsiaiškinti, ar tokiu būdu pavyks padengti šachmatų lentą). Aiškėja, jog perrinkti visus įmanomus variantus yra labai sunku ar net neįmanoma (net ir šiame paprastame uždavinyje perrinkinėti visus variantus, „nepametant“ nė vieno, nelengva). Tačiau kartais egzistuoja tam tikras dydis, kuris nekinta viso „sistemos“ kitimo metu. Šis dydis ir vadinamas invariantu. Gali būti, jog išsiaiškinus tą nekintantį dydį bus įmanoma kai ką nuspręsti ir apie galutinę „sistemos“ būseną, t. y. atsakyti į uždavinio klausimą. Kartais tas invariantas yra labai lengvai pastebimas (tarkime, duotame pavyzdyje tai buvo langelių skaičiaus lyginumas), kartais jį kur kas sunkiau pastebėti arba reikia imtis papildomų veiksmų (pavyzdžiui, įvairių „spalvinimų“) tam, kad „sukurtume“ invariantą. Bet kokiu atveju, šis metodas gali būti labai veiksmingas. Jis ypač dažnai naudojamas įvairiems „šachmatų lentos“ uždaviniams spręsti ir ne tik. Svarbu išmokti pastebėti tai, kas galėtų būti invariantu.
Invariantų lengviausia mokytis nagrinėjant pavyzdžius. Todėl pateiksime dar keletą pavyzdžių, kurie padės suprasti metodo idėją.
Kaip spręsti?
2 pavyzdys
Iš šachmatų lentos priešingų kampų išpjauname po 1 langelį. Ar šiuo atveju galėsime domino kauliukais padengti šachmatų lentą?
Atsakymas/sprendimas
Ne, negalima. Bus išpjauti 2 juodi arba 2 balti langeliai. Tarkime, juodi. Tada liks 30 juodų ir 32 balti langeliai, kuriuos reikės padengti. Tam, kad padengtume šiuos 62 likusius langelius, turėsime panaudoti 31 domino kauliuką, bet jie negalės padengti 32 baltų ir 30 juodų langelių, nes kiekvienas domino kauliukas dengia lygiai 1 juodą ir 1 baltą langelį.
Kaip spręsti?
1 pav.
3 pavyzdys
Stačiakampės dėžutės dugnas buvo padengtas 1×4 ir 2×2 stačiakampėmis plytelėmis. Išpylus plyteles iš dėžutės, viena 2×2 plytelė pasimetė. Vietoj jos buvo pasiūlyta 1×4 plytelė. Įrodykite, kad dabar nepavyks plytelėmis padengti dėžutės dugno.
Atsakymas/sprendimas
Čia su paprasta šachmatų lenta neišsiversime. Reikia „nudažyti“ langelius, kaip pavaizduota 1 pav. Nagrinėkime, kiek juodų langelių tokiu atveju dengs 2×2 ir 1×4 plytelės: bet kuri 2×2 plytelė dengs lygiai 1 juodą langelį, o 1×4 plytelė dengs 0 arba 2 juodus langelius. Taigi ir vėl, kaip besistengtume, pakeitus 2×2 plytelę 1×4 plytele, nepavyktų padengti dėžutės dugno („kirsis“ lyginumas).
Čia nagrinėjome vadinamuosius „šachmatų lentos“ uždavinius. Šio tipo uždaviniai pateikti pirmiausiai. Tačiau invariantų uždaviniai tikrai neapsiriboja tokio tipo uždaviniais. Kaip minėjome, invariantu gali būti bet kokia nagrinėjamos „sistemos“ savybė, kuri išlieka nepakitusi įvairiai kaitaliojant pačią sistemą. Labai dažnai tai yra lyginumas arba apskritai dalumas. Pabandykite tuo remtis ir surasti invariantus vėlesniuose uždaviniuose (dažniausiai reikės remtis dalumo savybėmis).
Uždaviniai
Ar galima 10×10 šachmatų lentą padengti T formos figūrėlėmis, turinčiomis 4 langelius1?
1 T formos figūrėlė iš 4 langelių.
Turime šachmatų lentą. Leidžiama atlikti tokią operaciją – perdažyti vienos eilutės arba vieno stulpelio visus langelius priešingomis spalvomis. Ar įmanoma tokiu būdu pasiekti, kad liktų tik vienas juodas langelis?
Šachmatų lentoje galime priešingomis spalvomis perdažyti visus langelius, esančius 2×2 kvadratėlyje, dengiančiame 4 šachmatų lentos langelius. Ar po kelių tokių operacijų galėtume gauti lentą su vienu baltu langeliu?
Ant lentos užrašoma 10 pliusų ir 15 minusų. Leidžiama nutrinti bet kuriuos du ženklus ir vietoj jų parašyti pliusą, jei tie ženklai sutampa, arba minusą, jei jie skirtingi. Koks ženklas galiausiai liks lentoje (po 24 operacijų)?
Ant lentos užrašytas tam tikras pliusų bei minusų skaičius. Leidžiama nutrinti bet kuriuos du ženklus ir vietoj jų parašyti pliusą, jei tie ženklai skirtingi, ar minusą, jei jie sutampa. Įrodykite, kad paskutinis ženklas, likęs lentoje, nepriklausys nuo to, kokia tvarka trinsime.
Šachmatų lentos 5×5 kiekviename langelyje tupi po vabalą. Kažkuriuo momentu visi vabalai perropoja į kaimyninį (horizontaliai ar vertikaliai) langelį. Įrodykite, kad tokiu atveju liks bent vienas tuščias langelis (be ant jo tupinčio vabalo).
Įrodykite, kad pavyks padengti šachmatų lentą domino kauliukais, jei išpjausime po 1 skirtingos spalvos langelį. Kokį metodą taikysite, nepriklausomai nuo to, kurie langeliai bus išpjauti.
