BEBRO konkurso užduotys 2017

 

Mėgstamiausi gėrimai

Taškai: 9

Keturi keliaujantys draugai sustojo nusipirkti atsigerti gėrimų parduotuvėje. Kiekvienas iš draugų yra apsisprendęs, kokio gėrimo nori labiausiai. Jų norai pavaizduoti lentelėje. Kokio gėrimo kiekvienas draugas nori labiausiai, matyti iš širdelių skaičiaus. Pavyzdžiui, Audra gėrimą įvertino  , o gėrimą   –  ir t. t.

 

Audra

Benas

Kristina

Domas

Gėrimų parduotuvė siūlo 4 rūšių gėrimus, tačiau jų turi mažai – tik po vieną kiekvienos rūšies gėrimą.

Kokį didžiausią širdelių skaičių gali surinkti draugai?

Įveskite natūralųjį skaičių.

Paaiškinimas

Optimizacija yra labai svarbi informatikoje, ekonomikoje, ūkinėje veikloje. Visais atvejais stengiamasi uždavinius suformuluoti matematiškai, o tada rasti jų universalius sprendimus, kad tikslo funkcija turėtų didžiausią reikšmę.

Šiame uždavinyje bandoma maksimizuoti grupės laimės lygį. Toks uždavinys matematikos teorijoje vadinamas „stabilių vestuvių uždaviniu“ – jame jaunikiams reikia parinkti tinkamiausias nuotakas. Panašiai formuluojamas ir medikų rezidentų paskirstymo į ligonines uždavinys. Kai dalyvių skaičius yra nedidelis (iki 10–20), jį galima spręsti loginio samprotavimo ar visiškojo perrinkimo būdu. Mūsų atveju iš viso galimos 4! = 24 kombinacijos. Už tokių uždavinių, kuriuose dalyvių skaičius siekia šimtus ar tūkstančius, sprendimą 2012 metais buvo paskirta Nobelio ekonomikos premija. Tai parodo, koks matematiškai sudėtingas yra šio uždavinio sprendimas.

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

Raktiniai žodžiai: optimizavimas.

Atsakymas

Teisingas atsakymas yra 14.

 

Audra

Benas

Kristina

Domas

Kadangi trys draugai labiausiai nori , didžiausias jų surinktas širdelių skaičius yra 4 + 4 + 3 + 3 = 14. Tokio širdelių rinkinio pavyzdys rodomas žemiau:

Audra

Benas

Kristina

Domas

Matome, kad  labiausiai nori tik Domas. Jis paima , kad grupės širdelių skaičius būtų didžiausias. Trys kiti draugai labiausiai nori tokio pat gėrimo, tačiau antrasis Audros pasirinkimas yra , o kitų dviejų draugų tai – trečiasis pasirinkimas. Taigi Audra turi paimti , o kiti du draugai gali paimti  ir  bet kuria tvarka.

Interaktyvi užduotis

 

 
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.