2014 2015 2016 2017 2018

Šokinėjanti beždžionė

Taškai: 12


Lapuotis medis   stovi tarp dviejų spygliuočių medžių   ir dviejų palmių .

Medžiuose padėti penkių skirtingų rūšių bananai, tarkim, P, Q, R, S, T – viename medyje viena rūšis. Beždžionė šokinėja tarp medžių, kas kartą suėsdama po vieną bananą. Ji sugaišta (šokdama ir ėsdama bananą) 3 sekundes, kol iš lapuočio medžio peršoka į bet kurį kitą, 2 sekundes – iš spygliuočio į palmę arba atvirkščiai, 7 sekundes – iš vieno spygliuočio į kitą spygliuotį arba iš vienos palmės į kitą palmę. Beždžionė šokinėja ir ėda bananus tokia tvarka P, Q, S, R, T, R, P.

Kokios rūšies bananai gali būti padėti lapuotyje medyje, siekiant, kad visas beždžionės sugaištas laikas būtų trumpiausias?

A. P arba Q, arba T C. Q arba S, arba T
B. P arba S, arba T D. Q arba R, arba S
Paaiškinimas

Spręsdami šį uždavinį iš pradžių turime pasitelkti dedukcinį metodą (arba dedukcinį samprotavimą), kad iš bendro atvejo išskirtume atskirus, logiškai pagrįstus atvejus. Taikome ir simetrijos principą. Taip pat siekiame optimalaus sprendimo, kad sunaudotume kuo mažiau resursų. Šiuo atveju optimizuojame laiko sąnaudas. Informatikai nuolat sprendžia optimizavimo uždavinius, tam sukurta nemažai standartinių algoritmų.

Reikšminiai žodžiai: dedukcinis samprotavimas, optimizavimas

Atsakymas

Sekoje P, Q, S, R, T, R, P ėdami visų rūšių bananai, atliekami šeši šuoliai P–Q, Q–S, S–R, R–T, T–R, R–P. Siekiant sugaišti mažiausiai laiko, reikia atlikti keturis 2 sekundžių ir du 3 sekundžių trukmės šuolius. Bendra visų šuolių trukmė – 14 sekundžių.
R yra keturiuose šuoliuose: S–R, R–T, T–R, R–P. R–T ir T–R trunka tiek pat laiko. Į R arba iš R yra mažiausiai trys skirtingi šuoliai. Todėl R negali būti lapuotis medis, nes trys šuoliai truktų 9 sekundes (3 X 3) ir sugaištas laikas nebūtų trumpiausias. Toks samprotavimas atmeta D atsakymą.
T gali būti lapuotis medis, nes T–R ir R–T šuoliai truktų po 3 sekundes, o kiti šuoliai – po 2 sekundes.
Jei Q yra lapuotis medis, tai šuoliai P–Q ir Q–S trunka po 2 sekundes. Tokiu atveju bendras visų šuolių laikas būtų minimalus, jei ir kiti šuoliai – S–R, R–T, T–R ir R–P – būtų 2 sekundžių trukmės. Tačiau tai yra neįmanoma ir tuo galima įsitikinti pažvelgus į paveikslėlį, kuriame medžiai pažymėti raidėmis S, R ir T. Taigi Q negali būti lapuotis medis, todėl telieka  galimybės P arba S, arba T.