Számelméleti feladat

Hmm, nem tudom, számelmélettel hogyan lehet megoldani, ez valójában kódolás-elmélet.

A végén az eredmény is lehet, hogy elég a feladat megoldásához, de leírom röviden a kódolást is. Nem lesz bonyolult.

Ha nem lenne hiba, akkor 2 kérdés, vagyis 2 hosszú kód elég lenne, hisz `2^2=4`, vagyis 2 igen-nem válasszal lehet "kódolni" a 4 lehetőséget. Abban az esetben az 5 hosszú kód (vagyis 5 kérdésre adott igen-nem válaszok sorozata) túlzás lenne.

Ha lehet egy hazugság is, akkor kell egy olyan kódot találni, ami 1 hibát képes javítani (ezt hibajavító kódnak hívják. Ilyen van pl. a telefonodban, amivel a QR kódot a program leolvassa, és kijavítja az esetleges kamera-hibákat. Ez persze sokkal egyszerűbb lesz annál.)
Ehhez legalább 3 Hamming távolságú kódot kell találni, vagyis olyat, ahol két kódszó között legalább 3 helyen van különbség. Pl. ez olyan:

A: 0 0 0 0 0
B: 0 1 1 1 0
C: 1 0 1 0 1
D: 1 1 0 1 1

Ha bármelyik kettőt kiválasztod, a kód bitjei között lesz 3 vagy 4 távolság, tehát a Haming távolsága 3 (pl. C és D között a második, harmadik és negyedik bitek különböznek).

Az 5 kérdést ebből a kódból függőlegesen lehet leolvasni:
1. kérdés: Edit a C-be vagy a D-be jár?
2. kérdés: Edit a B-be vagy a D-be jár?
3. kérdés: Edit a B-be vagy a C-be jár?
stb. ugye látod? Ne zavarjon meg, hogy lesz két-két egyforma kérdés! Ez nem törvényszerű, ha másik kódot választanál, ami szintén hármas Hamming távolságú, akkor lehet, hogy nem lennének egyforma kérdések.

Ezek után ha felteszed az 5 kérdést és mondjuk azokat a válaszokat kapod, hogy:
igen, nem, nem, nem, igen
vagyis 1 0 0 0 1, az a C-hez hasonlít a legjobban, attól egyetlen egy helyen tér csak el. Az az egy hely az, ahol hazudott a válaszoló. A többitől 1-nél több helyen tér el, vagyis azokhoz már legalább kétszer kellett volna hazudnia, azok nem lehetnek a megoldások, csak a C.

Mivel 3 a Hamming távolság a kódszavak (lehetséges válaszok) között, ezért 1 hazugság esetén a kapott válasz-sorozat az igazi megoldástól csak eggyel tér el, a többitől viszont legalább 2-vel.

Ha nem tanultatok ilyen Hamming távolság dolgot, akkor is ugyanígy kell megoldami, csak nem kell Hamming távolságnak nevezni a válaszok közötti eltérések számát.

Meg lehet csinálni kódolás-elmélet nélkül is. És mivel a feladat szerint tudjuk, hogy pontosan egyszer hamis a válasz, ezért 4 kérdés is elég!

Pontosabban ha az a feladat, hogy 4 barkochba kérdést lehet feltenni és abból pontosan egy válasz hamis lesz, akkor 4 kérdés elég:

Ha sose hazudna a válaszoló, akkor ugye 2 kérdés elég lenne, pl ezek:
- Az A vagy B osztályba jár-e?
Ha erre "igen" a válasz, akkor a második kérdés:
- Az A osztályba jár-e?
Ha viszont az első kérdésre "nem" a válasz, akkor az a második, hogy:
- A C osztályba jár-e?

Ugye ez tiszta?

De hazudik egyszer és nem tudjuk, mikor. Vagyis úgy kell feltenni a kérdéseket, hogy rájöjjünk, hogy hazudik-e. Pl. csinálhatjuk azt, hogy az első három kérdés ez:
- Az A vagy B osztályba jár-e?
- Az A vagy B osztályba jár-e?
- Az A vagy B osztályba jár-e?
Igen, ugyanazt kérdeztem háromszor!
Ha nem hazudik egyik válasznál sem, akkor kapunk 3 igent vagy 3 nemet, és tudjuk, hogy a negyedik kérdésre hazudni fog. Most ezt az előző mondatot olvasd el megint figyelmesen!
Negyedikre azt kérdezzük, amit fentebb a 2 kérdéses esetben is, csak tudjuk, hogy ha igent mond, az valójában nemet jelt és fordítva.

Ha viszont hazudott a három válasz valamelyikében, akkor kapunk 2 igent és 1 nemet, vagy 2 nemet és 1 igent. Amelyikből több van, az az igaz. A negyedik kérdés megint az, amit a fenti 2 kérdéses esetben tettünk fel, és most tudjuk, hogy erre rendesen felelt, nem hazudott.

Nem magyarázom tovább, ugye érthető?

------

Megjegyzés:
Ne felejtsd el, hogy nem az eredeti feladatot oldottuk meg! Ha 5 kérdés esetén hazudik pontosan egyszer, ahogy a feladat írja, akkor 4 kérdés nem elég, mert nem lehetünk benne biztosak, hogy mondjuk 3 igen után hazudni fog. Akkor 5 kérdést kell feltenni. Az ötödikre gondolhatná az ember egyszerűen, hogy semmi gond, ismételjük meg az utolsó kérdést, de az nem jó! Mondjuk az első 3 kérdésre kapott 3 igen után nem tudnánk, hogy az utolsó kettő közül melyiknél hazudott.
Olyant kell kérdezni ötödiknek, amire pontosan tudjuk, hogy mi a helyes válasz, akkor tudjuk megállapítani, hogy hazudott-e. Tehát tehetjük mondjuk ezt:
- Megkérdezzük 4-szer, hogy "Az A vagy B osztályba jár-e?"
- Aztán ötödiknek megkérdezzük azt, amit legfent is írtam (tehát az első 4 válasz alapján vagy az egyiket, vagy a másikat)

----
További megjegyzés:
Azért lehetett ilyen egyszerűen megoldani, mert kihasználtuk, hogy pontosan egyszer hazudik a válaszoló. Ha vagy igazat mondana, vagy egyszer hazudna, akkor kódolás-elmélettel kell csinálni, ahogy az első válaszomban írtam.