BEBRO konkurso užduotys 2017

 

Teniso turnyras

Taškai: 9

Šeši bebrai Lukas, Kamilė, Gabija, Matas, Joris ir Paulina dalyvauja teniso turnyre. Turnyro organizatoriai sprendžia rimtą problemą: kiekvienas bebras kiekvieną savo žaidimą turi žaisti ta pačia rakete, bet organizatoriams trūksta lėšų, todėl jie turnyrui gali suteikti tik ribotą skaičių teniso rakečių. Šis skaičius, deja, yra mažesnis negu šeši, o tai reiškia, kad organizatoriai negali aprūpinti visų bebrų skirtingomis raketėmis.
Turnyro žaidimų sąrašas yra toks:

Lukas

Matas

Matas

Gabija

Gabija

Kamilė

Kamilė

Lukas

Joris

Kamilė

Joris

Gabija

Paulina

Matas

Lukas

Gabija

Jokios dvi žaidėjų poros nežaidžia tuo pačiu metu, t. y. visi turnyro žaidimai žaidžiami skirtingais laiko intervalais, todėl nė vieno žaidimo laikas nesusikirs su kito žaidimo laiku.
Kiek mažiausiai teniso rakečių turi parūpinti organizatorius, kad turnyras įvyktų?

  • 2
  • 3
  • 4
  • 5
Paaiškinimas

Daug realaus gyvenimo uždavinių gali būti modeliuojami duomenų struktūra, vadinama grafu. Grafas yra sudarytas iš viršūnių aibės (dažnai žymimų taškais) ir šias viršūnes jungiančių briaunų (dažnai vaizduojamų linijomis) aibės. Įvairūs gyvenime kylantys uždaviniai – įvykių tvarkaraščių sudarymas ir paskyrimų planavimas – gali būti sprendžiami priskiriant skirtingas spalvas kiekvienai grafo viršūnei arba briaunai. Informatikos sritis, nagrinėjanti tokio tipo uždavinius, vadinama grafų spalvinimu.

Raktiniai žodžiai: grafai, grafų spalvinimas.

Atsakymas

Teisingas atsakymas 3.

Turnyras gali būti vaizduojamas žemiau pateikta schema. Du bebrus jungianti linija rodo, kad šie bebrai žaidžia vienas su kitu. Aišku, kad nėra linija sujungtų dviejų bebrų, kurie galėtų sužaisti visus savo žaidimus (visą turnyrą) ta pačia rakete.

Problemą galima išspręsti kiekvieną bebrą spalvinant schemoje taip, kad jokie du linija sujungti bebrai nebūtų nuspalvinti ta pačia spalva. Viską pabaigus bebrai, kurie bus nuspalvinti ta pačia spalva, galės žaisti žaidimus ta pačia rakete. Be to, reikia numatyti mažiausią galimą spalvų skaičių, nes mums reikia rasti mažiausią teniso rakečių skaičių.

Bebrui Lukui galime priskirti pirmą spalvą, tarkim, raudoną. Kadangi Lukas linija sujungtas su Gabija, Kamile ir Matu, šiems bebrams turime priskirti kitas spalvas (t. y. ne raudoną). Priskirkime Gabijai antrą spalvą, pavyzdžiui, mėlyną. Matome, kad bebras Matas linija sujungtas ir su Luku (nuspalvintu raudonai), ir su Gabija (nuspalvinta mėlynai). Vadinasi, Matui reikia priskirti trečią spalvą – žalią. Nors Kamilė taip pat sujungta ir su Luku, ir su Gabija, bet nesujungta su Matu, todėl Kamilei galime priskirti tą pačią – žalią – spalvą kaip ir Matui. Bebras Joris linija sujungtas ir su Gabija (nuspalvinta mėlyna spalva), ir su Kamile (nuspalvinta žalia spalva), bet nėra sujungtas su Luku, kuriam priskirta raudona spalva. Vadinasi, Joriui galime priskirti tą pačią spalvą kaip Lukui – raudoną. Galų gale Paulina yra sujungta tik su Matu (nuspalvintas žalia spalva), todėl jai galime priskirti bet kurią spalvą iš esamų, išskyrus žalią. Vadinasi, tai gali būti mėlyna arba raudona.

Kadangi visiems bebrams nuspalvinti prireikė 3 spalvų, darome išvadą, kad turnyrui organizuoti užteks trijų rakečių: viena rakete dalysis Lukas ir Joris (raudona spalva), kita rakete – Matas ir Kamilė (žalia spalva), o trečią raketę naudos Gabija (mėlyna spalva). Paulina galės naudotis arba Luko ir Jorio rakete, arba Gabijos rakete.

Organizuoti turnyrą turint mažiau kaip tris raketes nepavyks, nes, pavyzdžiui, Lukas žaidžia su Matu, Matas žaidžia su Gabija, o Gabija – su Luku. Taigi, jei bus tik dvi raketės, vienas iš šių trijų žaidimų turės būti žaidžiamas ta pačia rakete, o tai neįmanoma.

 

 
Informacija atnaujinta 2017-11-13 16:52:39
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.