Ilgiausia žodžių grandinė
Taškai: 9
Du bebrai žaidžia žodžių grandinės žaidimą. Vienas bebras pradeda pasakydamas žodį. Tada kiekvienas paeiliui sako po dar nepanaudotą žodį, prasidedantį trečia ankstesnio žodžio raide. Deja, bebrai žino labai nedaug žodžių – visą jų žodyną galima pavaizduoti taip:
Kiek žodžių sudaro ilgiausia žodžių seka, pasakyta per vieną žaidimą?
Spręsdami šį uždavinį turime suprasti taisyklių rinkinį, aiškų ir patogų duomenų vaizdavimą (grafą) ir tada surasti optimalų sprendimą duotoje sistemoje (žodyne). Grafai dažnai naudojami informatikoje. Jais modeliuojamos įvairiausios struktūros iš objektų ir jų ryšių, pavyzdžiui, traukinių maršrutų arba vandentiekių išdėstymo schemos.
Turėdami daugiau informatikos žinių, galėtume pakeisti uždavinį, pavyzdžiui, ilgiausio maršruto paieška grafe. Tai glaudžiai susiję su žinomu Keliaujančio pirklio uždaviniu.(https://lt.wikipedia.org/wiki/Keliaujan%C4%8Dio_pirklio_u%C5%BEdavinys)
Informatikos mokslininkai teigia, kad surasti ilgiausią žaidimą didžiausiame žodyne (turint galvoje, kad žinome tūkstančius žodžių!) nėra įmanoma. Tai užimtų per daug laiko net su geriausiu algoritmu.
Raktiniai žodžiai: grafas, dedukcija, ilgiausias kelias, duomenų vaizdavimas.
Teisingas atsakymas: 8.
Bebrai gali panaudoti daugiausiai 8 žodžius. Galima žodžių seka:
medis→drevė→ežeras→erdvė→debesis→bebras→burtas→radinys
Yra ir kitų tokio pat ilgio sekų. Turime pavyzdį iš 8 žodžių, bet dar nežinome, ar įmanoma sudaryti 9 žodžių seką. Tokiu atveju mums reikėtų panaudoti visus žodyno žodžius. Kadangi žodyne nėra žodžio, kurio trečia raidė m, turėtume pradėti nuo žodžio „medis“, todėl prieš žodžius radinys ir riba turi būti du skirtingi žodžiai, kurių trečia raidė „r“, bet tokį žodį turime tik vieną – burtas. Todėl neįmanoma viename žaidime panaudoti visų 9 žodžių.