Paukšteliai

Taškai: 9

Trys paukšteliai tupi ant medžio šakų. Kas tris sekundes du iš jų nuskrenda ant šalia esančių šakų, bet negali skristi nuo 9-os šakos ant 1-os arba nuo 1-os ant 9-os.

Gali būti, kad po kurio laiko visi paukšteliai sutūps ant pirmosios šakos viename iš duotų medžių.
Kuris tai medis?

A. B.
C. D.
Paaiškinimas

Informatikoje vienas iš svarbiausių uždavinių sprendimo metodų reikalauja surasti uždavinio dalį, kuri nesikeičia, teisingai atliekant veiksmus. Tai vadinama invariantiškumu ir dažnai vartojama, pavyzdžiai, cikluose. Šiuo atveju invariantas yra šakų numerių sumos lyginumas (tam tereikia sudėti šakų numerių reikšmes).

Lyginumo metodas yra naudojamas ir kitose srityse, pavyzdžiui, tikrinant ar nebuvo pažeisti perduoti duomenys arba norint įsitikinti, jog saugomi duomenys yra nepažeisti.

Atsakymas

Teisingas atsakymas – A.

Pastebėkite, kad šakų, ant kurių tupi paukščiai, numerių sumos nesikeičia, nors kiekvieną kartą bet kurie du paukščiai keičia vietas.
Visų variantų, išskyrus A, šakų, ant kurių tupi paukščiai, numerių sumos yra lyginės (B atveju 20, C – 16, D – 14). Tačiau jeigu visi paukščiai sutūptų ant pirmos šakos, suma pasidarytų nelyginė, ko negali nutikti.

Vienas iš galimų sprendimų atsakymui A yra: 9 ir 4  paukščiai → ant 8 ir 3 šakos; 8 ir 3 → ant 7 ir 2; 7 ir 2 → ant 6 ir 1; 6 ir 2 → ant 5 ir 1; 5 ir 1 → ant 4 ir 2; 4 ir 2 → ant 3 ir 1; 3 ir 1 → ant 2 ir 2; 2 ir 2 → ant 1 ir 1. Visi trys paukščiai atsidūrė ant pirmos šakos.

Šį uždavinį galima išspręsti ir greičiau, jeigu turėtume omeny, jog paukštis gali skristi per du žingsnius (įsivaizduokite kitą paukštį, skrendantį paskui vieno žingsnio skirtumu). Šis uždavinys taip pat gali būti apibendrintas klausimu: ar gali visi paukščiai atsidurti ant šakos su lyginiu numeriu?

 

 
Informacija atnaujinta 2015-12-03 07:50:57
Informuojame, kad nuo 2019 m. rugsėjo 2 d. Ugdymo plėtotės centro veiklas vykdo Nacionalinė švietimo agentūra. Ši interneto svetainė toliau nebus atnaujinama, tačiau visa informacija išliks aktyvi ir prieinama tol, kol bus perkelta į Nacionalinės švietimo agentūros interneto svetainę www.nsa.smm.lt.