Jungtys
Taškai: 9
Reikia nuspalvinti kai kuriuos apskritimus paveikslėlyje. Atkarpomis sujungtų apskritimų poras vadinsime kaimynais. Skaičiai apskritimuose (sąlygos) rodo, kiek kaimynų turi būti nuspalvinta. Pavyzdžiui, reikia nuspalvinti lygiai 3 iš 4 apskritimo (kuriame įrašyta „=3“) kaimynus ir mažiau negu 4 apskritimo (kuriame įrašyta „<4“) kaimynus.
Kiek apskritimų iš viso reikia nuspalvinti, kad visos sąlygos apskritimuose būtų tenkinamos?
A) 4 B) 5 C) 6 D) 7
Šį uždavinį sprendžiame, pasitelkę logiką. Matome, kad visiško perrinkimo (arba jėgos) metodas (brute-force) nėra efektyvus. Jei naudotume visiško perrinkimo metodą, pastebime, kad kiekvienas apskritimas turi dvi galimybes. Tada bendras perrinkimų skaičius būtų lygus 29=512. Taigi vienas sprendimų būtų išbandyti visas 512 skirtingų apskritimų užpildymo kombinacijų. Tačiau pasitelkus logiką, ypač dedukcinę samprotavimų seką, gerokai sumažinamas galimų užpildymų skaičius, ir uždavinys nesunkiai išsprendžiamas.
Raktiniai žodžiai: dedukcinis samprotavimas, logika, sąlyga.
Teisingas atsakymas: 5.
Pažiūrėję į apatinį dešinįjį apskritimą, matome, kad abu jo kaimynai turi būti nuspalvinti:
Taip pat visi apskritimo ( „=4“) kaimynai turi būti nuspalvinti:
Taip nuspalvinus, visų apskritimų sąlygos yra tenkinamos ir daugiau nieko negalima spalvinti:
- jei nuspalvintume „=1“, tai „=3“ būtų netenkinama,
- jei nuspalvintume „=2“, tai „<4“ (virš) būtų netenkinama,
- jei nuspalvintume „=3“ arba „=4“, tai „<2“ būtų netenkinama.