Zadanie
Milý denníček,
ako som sa tak ponevieral po lese, naďabil som na malú chalúpku, v ktorej bývajú šťavnaté kozliatka. Mama koza nebola doma, tak som sa rozhodol využiť situáciu. Zaklopal som na dvere a hovorím: „Kozliatka, kozliatka, otvorte mi vrátka. To som ja, vaša mamička.“ V duchu som bol na seba mimoriadne pyšný, že som s takým úskokom prišiel. Kozliatka však spoznali, že môj hlas neznie ako ich mamička, takže som nepochodil. Cestou lesom som však našiel katalóg miestnej kliniky, ktorá okrem iného ponúka úpravu hlasu.
Klinika ponúka štyri druhy operácie na zmenu hlasu. Každá operácia má \(n\)-miestny identifikačný kód zložený z \(0\) a \(1\).1 Aby sa predišlo chybám, sú kódy urobené tak, že ak pacient pri diktovaní spraví nanajvýš jednu chybu (teda namiesto jednej \(0\) povie \(1\) alebo naopak), tak doktor vie jednoznačne určiť, ktorú operáciu mal pacient na mysli. Určte najmenšie \(n\), pre ktoré môžu takéto identifikačné kódy existovať, a vysvetlite, prečo menšie \(n\) nevyhovuje.
Kód môže začínať aj číslicou \(0\).↩
Pre \(n=5\) existuje napríklad štvorica kódov \(00000\), \(00111\), \(11011\) a \(11100\). Overiť, že vyhovujú, môžeme vypísaním všetkých možností, ako sa možno pomýliť v jednej číslici. Zistíme, že takou chybou nemôžeme dostať z dvoch rôznych kódov (z našej štvorice) jedno päťčíslie. Menej pracne to možno overiť pozorovaním, že každé dva kódy sa líšia na aspoň troch pozíciách. To znamená, že päťčíslie, ktoré získame jednou chybou, sa bude od každého z ostatných kódov stále líšiť na aspoň dvoch pozíciách.
Keby boli kódy štvormiestne, v kóde by bolo možné spraviť chybu štyrmi rôznymi spôsobmi. To znamená, že pre každý druh operácie by sme museli uznávať päť rôznych štvorčíslí, ktoré by mohol pacient povedať – správny kód a štyri chybné. To je spolu \(5\cdot4=20\) štvorčíslí s jednoznačnými významami, ale celkovo existuje iba \(2^4=16\) štvorčíslí, takže sa medzi ne naše kódy nezmestia.
Ľahko si rozmyslíme, že kódy nemôžu byť ani kratšie. Keby existovali, mohli by sme ich predĺžiť na štvormiestne napríklad doplnením núl na koniec. Najmenšie použiteľné \(n\) je teda \(5\).
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.