BEBRO konkurso užduotys 2018

 

Paslapčių paslaptis

Taškai: 12

Linas, Agnė ir Eglė žaidžia loterijoje, kurioje yra ne daugiau nei vienas laimėtojas. Tačiau žaidėjas niekam negali sakyti, ar jis laimėjo, ar pralaimėjo. Žaidėjai:

  1. Linas ir Agnė slapta meta monetą.
  2. Linas ir Eglė slapta meta monetą.
  3. Agnė ir Eglė slapta meta monetą.
  4. Kiekvienas žaidėjas pasako, ar jo mestos dvi monetos atvirto vienodai, ar skirtingai.
  • Pralaimėjusieji loterijoje sako tiesą.
  • Laimėjusieji loterijoje sako netiesą.

Pavyzdžiui, jei mestos monetos atvirto, kaip parodyta paveikslėlyje, Eglė laimi loterijoje, o kiekvienas žaidėjas pasako, kad atvirto „skirtingai“.

Jei Linas pasako, kad atvirto „vienodai“, Agnė pasako – „vienodai“, o Eglė pasako – „skirtingai“, tada kuris iš teiginių yra teisingas?

  1. Loterijoje nelaimėjo nei vienas žaidėjas.
  2. Kažkuris žaidėjas laimėjo loterijoje, bet nežinoma kas.
  3. Kažkuris žaidėjas laimėjo loterijoje ir tikrai žinoma kas
  4. Nežinoma, ar kas nors laimėjo, ar pralaimėjo loterijoje.
Paaiškinimas

Lino, Agnės ir Eglės situacija žinoma Pietaujančių kriptografų problemos pavadinimu. Kriptografijoje Pietaujančių kriptografų problema analizuoja, kaip atlikti saugų loginės funkcijos ARBA daugianarį skaičiavimą. Pirmasis šią problemą pasiūlė David Chaum 1980 m. Jis panaudojo ją kaip pavyzdį, rodantį, kad galima siųsti anoniminius pranešimus su besąlygišku siuntėjo ir gavėjo atsekamumu. Anoniminiai komunikacijos tinklai, pagrįsti šia problema, dažnai vadinami DC tinklais (DC reiškia „Dining Cryptographers“).

Šiuo metu  aktuali problema – internetas, kur asmens duomenys dažnai renkami be jo sutikimo.

Raktiniai žodžiai: kodas, kintamo ilgio kodas.

Atsakymas

Teisingas atsakymas: B.

Pateikiami keli sprendimai.

Ar laimėjimas verčia meluoti?

Jei žaidėjas meluoja, jis laimėjo loterijoje. Laimėjimas loterijoje priverčia kažkurį žaidėją pameluoti. Tai leidžia manyti, kad tas, kuris meluoja, yra laimėtojas. Paprastai gyvenime laimėtojai tikriausiai nemeluoja. Įsivaizduokime, kad esam tokiame pasaulyje, kuriame galioja šios užduoties taisyklės, ir laimėtojas pameluoja.

Mes turime melagį!

Galima įsitikinti, kad kažkuris žaidėjas pagal šios užduoties scenarijų (atvirto vienodai, vienodai, skirtingai) meluoja. Tai galima išsiaiškinti dviem būdais.

Pirmasis būdas: prieštaros metodas.

Žaidėjai pasakė, kad atvirto „vienodai, vienodai, skirtingai“. Tarkime, kad visi šie žaidėjai nemeluoja. Linas pasakė, kad atvirto „vienodai“, todėl LA ir LE metimų rezultatai turėtų būti vienodi. Kadangi Agnė pasakė, kad atvirto „vienodai“, tada LA ir AE metimų rezultatai turėtų būti vienodi. Todėl visų trijų metimų rezultatai turėtų būti vienodi. O tai prieštarauja teiginiui, kad „visi žaidėjai sakė tiesą“, nes užduotyje žaidėjai teigė, kad atvirto „vienodai, vienodai, skirtingai“.

Pastaba: tačiau tai nereiškia, kad Eglė laimėjo loterijoje, o tiesiog pasako, kad teiginys „visi sako tiesą“ neteisingas.

Antrasis būdas: sudaryti lentelę.

Galima sudaryti visų aštuonių galimybių lentelę. Pirmuose trijuose stulpeliuose surašomi visų metimų rezultatai. Kituose trijuose stulpeliuose surašomi visų žaidėjų pasisakymai, kai jie sako tiesą.

Metimai

Pasisakymai

LA

LE

EA

L

A

E

Herbas

Herbas

Herbas

Vienodai

Vienodai

Vienodai

Herbas

Herbas

Moneta

Vienodai

skirtingai

Skirtingai

Herbas

Moneta

Herbas

Skirtingai

Vienodai

Skirtingai

Herbas

Moneta

Moneta

Skirtingai

Skirtingai

Vienodai

Moneta

Herbas

Herbas

Skirtingai

Skirtingai

Vienodai

Moneta

Herbas

Moneta

Skirtingai

Vienoda

Skirtingai

Moneta

Moneta

Herbas

Vienodai

Skirtingai

Skirtingai

Moneta

Moneta

Moneta

Vienodai

Vienodai

Vienodai

Pastebėsime, kad lentelėje nėra eilutės, kurioje būtų sakoma, kad monetos atvirto „vienodai, vienodai, skirtingai“. Taigi kažkuris žaidėjas meluoja. Todėl galima atmesti atsakymus A ir D.

Ar galima teigti, kad laimėtojas žinomas?

Aišku, kad bent vienas žaidėjas melavo.

Jei žaidėjas L melavo, tada žaidėjų pranešimai turėjo būti toks: monetos atvirto „skirtingai, vienodai, skirtingai“.

Jei žaidėjas A melavo, žaidėjai turėjo pasakyti, kad monetos atvirto „vienodai, skirtingai, skirtingai“.

Jei žaidėjas E melavo, žaidėjai turėjo sakyti, kad monetos atvirto „vienodai, vienodai, vienodai“.

Daugiau informacijos, kuri padėtų nuspręsti, kuris iš šių teiginių teisingas, užduoties sąlygoje nėra. Todėl negalima pasakyti, kuris žaidėjas meluoja. Žinoma, kad kažkuris žaidėjas laimėjo loterijoje, bet nežinoma, kas.

 

 
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.