BEBRO konkurso užduotys 2017

 

Skiautinys

Taškai: 12

Bebrai iš įvairių spalvų skiaučių nori pasiūti antklodę. Ji turi būti spalvinga, todėl bendrą kraštą turinčios skiautės turi būti skirtingų spalvų. Be to, bebrai nori panaudoti kuo mažiau audinių spalvų. Jie nubraižė, kaip turėtų atrodyti antklodės ornamentai:

     

Padėk bebrams pasiūti antklodę iš kiek galima mažiau skirtingų spalvų audinių. Pasirink audinio spalvą ir nuspalvink antklodę.

Paaiškinimas

Spalvinimas priklauso grafo spalvinimo uždavinių grupei. Informatikoje grafas yra abstrakti objektų ryšių sistema. Informatikoje grafai vaizduojami apskritimais, arba taškais (vadinamais viršūnėmis), sujungtais briaunomis, arba lankais, kurie rodo tam tikrus vaizduojamų objektų ryšius. Grafe spalvinimo uždavinys formuluojamas taip: viršūnės turi būti sujungtos skirtingų spalvų linijomis. Grafo spalvinimo uždavinys – surasti mažiausią skaičių skirtingų spalvų tam tikram grafui nuspalvinti.

Šis uždavinys atitinka žemėlapio spalvinimo uždavinį. Tik pasitelkiant kompiuterį yra įrodyta, kad bet kokį žemėlapį, suskirstytą į regionus, galima nuspalvinti 4 spalvomis taip, kad gretimi regionai būtų nuspalvinti skirtingomis spalvomis.

https://en.wikipedia.org/wiki/Four_color_theorem

https://en.wikipedia.org/wiki/Graph_coloring

Raktiniai žodžiai: grafas, žemėlapio spalvinimas, keturių spalvų uždavinys.

Atsakymas

Teisingas atsakymas yra:

Antklodė gali būti pasiūta iš trijų skirtingų spalvų audinių. Sprendinį galima rasti derinant spalvas. Neįmanoma antklodės pasiūti iš 2 spalvų audinio, nes neužtenka 2 spalvų trims ornamentams, turintiems vieną bendrą viršūnę.

Interaktyvi užduotis

 

 
Informacija atnaujinta 2017-11-13 16:52:39