2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Jungtys

Taškai: 12

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

Paaiškinimas

Šį 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.

Atsakymas

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.