Feladat: Pontversenyen kívüli P.230 Korcsoport: 16-17 Nehézségi fok: -
Megoldó(k):  Baranyi József ,  Nagy 578 Imre ,  Surján Péter 
Füzet: 1979/december, 214 - 215. oldal  PDF  |  MathML 
Témakör(ök): Informatikához kapcsolódó feladatok, Pontversenyen kívüli probléma
Hivatkozás(ok):Feladatok: 1974/december: Pontversenyen kívüli P.230

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Két jelből 27 különböző hét elemű sorozat készíthető. Ha ezek valamelyikében egy jel torzul, attól függően, hogy hányadik jel torzult, hét újabb sorozatot kapunk. Egy olyan rendszerben, amelynek az elemei hét elemű sorozatok, és ezeket a torzulás után is fel akarjuk ismerni, a torzítással kapott sorozatoknak is különbözőeknek kell lenni. Mivel egy sorozatból a torzítottjaival együtt 1+7=23 sorozat származik, egy rekonstruálható rendszerben legfeljebb 27:23=24 különböző sorozat lehet.
Az a körülmény, hogy a lehetőségek száma épp 2-hatvány, adja az ötletet, hogy a keresett sorozatokban az első néhány (esetünkben 4) jelet szabadon válasszuk, és a fennmaradó jelek ügyes megválasztásával készüljünk fel az esetleges torzítás felderítésére. Ha ezek a további jelek a kezdeti jelekből egyértelműen kiszámolhatóak, akkor e szabályszerűségek esetleges sérülése fog a hiba helyére vezetni minket.
Jelöljük jeleinket 0-val és 1-gyel, közülük az i-ediket egy megkonstruálandó sorozatban xi-vel, és végezzük a műveleteket modulo 2, akkor a következő összefüggések meghozzák a kívánt eredményt:

x5=x1+x2+x3x6=x1+x2+x3+x4x7=x1++x2x3+x4.
Ha a vett jelsorozatban ezek mindegyike teljesül, nincs hiba. Ha közülük pontosan 1 nem teljesül, x5,x6,x7 közül az torzult, amelyik karakterisztikus összefüggése nem teljesül. Ha 2 összefüggés érvénytelen, x2,x3,x4 közül pontosan az torzult, amelyik az érvénytelen összefüggésekben szerepel. Végül ha mindegyik összefüggés érvénytelen, x1 torzult. Mivel csak kétféle jelünk van, elég a torzulás helyét megtalálni.
Tehát a vizsgált ábécében 16 betű szerepelhet.