Megoldás (Alsó korlát)
Tegyük fel, hogy k elõre leírt kérdéssel ki lehet találni a gondolt számot. Tekintsük ezt a k kérdést, és válasszuk ki a 16 szám egyikét, mintha az lenne a gondolt szám. Válaszoljuk meg a k db kérdést hazugság nélkül. Írjunk 0-t az "igen", 1-est a "nem" válasz helyett. Így egy k hosszúságú 0-1 sorozatot kapunk, amit a kiválasztott szám kódjának fogok nevezni. Ha a válaszoló egyszer hazudik, akkor nem a szám kódját kapjuk, hanem egy olyan sorozatot, amely egy helyen különbözik a szám kódjától. Az ilyen sorozatokat a szám álkódjának fogom nevezni. Álkódból éppen k darab van, mert a k kérdésbõl egyre kaphatunk rossz választ, és mindegyik kérdésre egyféle rossz választ kaphatunk. A 16 számhoz 16 kód és 16k álkód tartozik. Ezeknek mind különbözõeknek kell lennie, mert ha volna közös elemük, akkor az annak a 0-1 sorozatnak megfelelõ válaszok esetén nem tudnánk kitalálni a gondolt számot. Összesen 2^k darab k hosszú 0-1 sorozat van, így biztosan teljesül a 16·(k+1) ≤  2^k egyenlõtlenség. A két oldal értékét k = 1, 2, ... esetén táblázatban írom fel.

Látható, hogy az egyenlõtlenség a k = 7 esetben teljesül elõször. Tehát legalább 7 elõre leírt kérdésre van szükség.

I. konstrukció ("Mohó algoritmus")
7 elõre leírt kérdéssel megoldható a feladat.
Ennek igazolásához 16 db olyan 7 hosszúságú 0-1 sorozatot kell megadni, amelyek közül bármelyik kettõ legalább három helyen eltér egymástól. Ebbõl ugyanis következik, hogy a 16 kód és 16·7 álkód mind különbözõ lesz: ha két különbözõ kódhoz tartozó álkód megegyezik, akkor a két kód csak két helyen tér el egymástól.
Mohó algoritmussal dolgozunk. A 0000000 sorozattól kezdve a lexikografikusan legkisebb olyan sorozatot keressük, amelyik mindegyik korábban már kiválasztott sorozattól legalább 3 helyen különbözik. Az eredményül kapott 16 db 0 - 1 sorozat az alábbi táblázat oszlopaiban található:

A 7 kérdés a 7 sorból olvasható ki. Egy oszlophoz tartozó kérdés, azokra az 1 és 16 közti számokra kérdez rá, amelyek sorában az adott oszlopban 0 áll. A hét kérdés mindegyike így kezdõdik: "A gondolt szám az itt megadott halmazban van?". A hét megadott halmaz az alábbi sorokban olvasható:

Érdekes, hogy a fenti 1., 2., 3., 5. kérdések rendre megegyeznek az 5.8 b) feladatra adott megoldások  kérdéseivel (lásd a 16. szakkört).

II. konstrukció (Algebra I.)
Az 5.8 b) feladatra adott II. konstrukcióra építve az 1.2 feladat IV. megoldásának mintájára dolgozunk.
Legyen (n-1) kettes számrendszerbeli alakja x₈x₄x₂x₁ (ahol n befutja az {1, 2, ..., 16} halmazt, míg x_i értéke 0 vagy 1). Ebben a megközelítésben az 5.8 b) feladatra adott II. konstrukció kérdései így írhatók:

"x₈ = 0?";              "x₄ = 0?";              "x₂ = 0?";              "x₁ = 0?".
Állítjuk, hogy a jelen feladat megoldását kapjuk, ha a fenti négy kérdést kiegészítjük az alábbi hárommal:
"x₄+x₂+x₁ = 0?";   "x₈+x₂+x₁ = 0?";  "x₈+x₄+x₁ = 0?",
ahol az összeadás és az egyenlõség mindenütt mod 2 értendõ.
A válaszokat elfogadva megállapíthatjuk x₈, x₄, x₂, x₁, x₄+x₂+x₁, x₈+x₂+x₁, x₈+x₄+x₁ értékeit és az elsõ négyre kapott értékkel leellenõrizhetjük az utolsó hármat. Ha egyik ellenõrzés sem teljesül, akkor biztosan x₁ volt a ludas, értékét kijavíthatjuk. Ha két ellenõrzésnél sem stimmelt az összeg, akkor x₂, x₄ vagy x₈ értéke volt hibás, attól függõen, hogy melyik két egyenlettel volt baj. Mindegyik változó legalább két összegben szerepel, így ha csak egy ellenõrzésnél jutottunk ellentmondáshoz, akkor biztosan annak az összegnek az értékét kaptuk rosszul, a változók értékei helyesek. Végül, ha minden ellenõrzés klappolt, akkor nem is kaptunk hamis választ, tudjuk a változók értékeit.

III. konstrukció (Algebra II., Hamming kód)
Az I. konstrukció gondolatmenete alapján, de a II. konstrukcióban szereplõ algebrai módszerhez hasonló megoldást keresünk.
16 db olyan hét hosszúságú 0 - 1 sorozatot kell megadni, amelyek közül bármelyik kettõ legalább három helyen eltér egymástól. Szeretnénk ezeket a sorozatokat egy

a₁· y₁+ a₂· y₂ + ... + a₇· y₇ = 0, b₁· y₁ + b₂· y₂ + ... + b₇· y₇ = 0, c₁· y₁ + c₂· y₂ + ... + c₇· y₇ = 0
homogén lineáris egyenletrendszer megoldásaként elõállítani. (Itt, és az alábbiakban a +, · mûveletek és az egyenlõség is mod 2 értendõ, az együtthatók, változók értékei 0 és 1 lehetnek.) Azaz olyan a₁,  a₂, ..., a₇, b₁,  b₂, ..., b₇, c₁,  c₂, ..., c₇ együtthatókat keresünk, amelyek esetén a fenti egyenlet­rend­szert kielégítõ y₁ y₂ ... y₇ sorozatok közül bármelyik kettõ legalább 3 helyen eltér egymástól. Az ilyen kódot lineáris kódnak nevezik.
A lineáris kódnak a következõ elõnye van. Az egyenletrendszer egyik megoldása, tehát az egyik kódszó a 00...0 sorozat. Tegyük fel, hogy sikerül olyan az egyenletrendszer együtthatóit úgy megválasztani, hogy bármelyik másik megoldás 00...0-tól legalább három helyen térjen el, azaz legalább három 1-es legyen benne. Állítjuk, hogy ebben az esetben bármelyik két megoldás legalább három helyen eltér egymástól. Valóban, ha az y₁₁ y₂₁ ... y₇₁ és az y₁₂ y₂₂ ... y₇₂ sorozat is teljesíti a fenti egyenletrendszert, azaz
a₁· y₁₁ + a₂· y₂₁ + ... + a₇· y₇₁ = 0,                         a₁· y₁₂ + a₂· y₂₂ + ... + a₇· y₇₂ = 0, b₁· y₁₁ + b₂· y₂₁ + ... + b₇· y₇₁ = 0,                         b₁· y₁₂ + b₂· y₂₂ + ... + b₇· y₇₂ = 0, c₁· y₁₁ + c₂· y₂₁ + ... + c₇· y₇₁ = 0,                          c₁· y₁₂ + c₂· y₂₂ + ... + c₇· y₇₂ = 0,
akkor a megfelelõ egyenletek kivonása révén kapjuk, hogy
a₁· (y₁₁ - y₁₂) + a₂· (y₂₁ - y₂₂) + ... + a₇· (y₇₁ - y₇₂) = 0, b₁· (y₁₁ - y₁₂) + b₂· (y₂₁ - y₂₂) + ... + b₇· (y₇₁ - y₇₂) = 0, c₁· (y₁₁ - y₁₂) + c₂· (y₂₁ - y₂₂) + ... + c₇· (y₇₁ - y₇₂) = 0,
azaz az (y₁₁ - y₁₂) (y₂₁ - y₂₂)... (y₇₁ - y₇₂) sorozat is teljesíti az eredeti egyenletrendszert. Ebben a sorozatban feltételünk szerint legalább három 1-es van, de pontosan ott van benne 0-tól különbözõ szám, ahol az  y₁₁ y₂₁ ... y₇₁,  y₁₂ y₂₂ ... y₇₂ sorozatok eltérnek egymástól. Tehát ha egy lineáris kódban nincs olyan kódszó, amelyikben egy vagy két 0-tól különbözõ jel van, akkor bármely két kódszó távolsága legalább három.
Feltételi egyenlet nélkül az y₁, y₂, ..., y₇ bináris változók értékei 2⁷-féleképpen választhatók meg, hiszen mind a hét változó szabadon és egymástól függetlenül fölveheti a 0, 1 értékek bármelyikét. Egy egyenlet lehetõséget ad, hogy az egyik változót kifejezzük a többibõl, így a szabad változók száma eggyel csökken. Azt szeretnénk elérni, hogy az egyenletrendszernek 16 = 2⁴ megoldása legyen, ehhez 3 (független) egyenletet kell megadni.
Az
a₁· y₁ + a₂· y₂ + ... + a₇· y₇ = 0, b₁· y₁ + b₂· y₂ + ... + b₇· y₇ = 0, c₁· y₁ + c₂· y₂ + ... + c₇· y₇ = 0
egyenletrendszer tehát pontosan akkor megfelelõ, ha (egyenletei függetlenek és) nincs olyan megoldása, amelyben az ismeretlenek közül egynek vagy kettõnek az értéke 1-es (és a többi 0).
y₁ = 1, y₂ = ... = y₇ = 0 pontosan akkor megoldása a fenti egyenletrendszernek, ha az

mátrix elsõ oszlopában mindenütt 0 áll. Általában, egyenletrendszerünknek pontosan akkor van olyan megoldása, amelyben az egyik változó értéke 1, a többié 0, ha A-nak van azonosan 0 oszlopa.
y₁ = y₂ = 1,  y₃ = ... = y₇ = 0 pontosan akkor megoldása az egyenletrendszernek, ha az A mátrix elsõ két oszlopa egyenlõ egymással. Általában, pontosan akkor van olyan megoldás, amelyben két változó értéke 1, a többié 0, ha A-nak van két egyforma oszlopa. Az A mátrix tehát pontosan akkor ad megfelelõ egyenletrendszert, ha egyik oszlopa sem egyezik meg az azonosan 0 oszloppal vagy egy másik oszloppal (és az egyenletek függetlenek).
A egy-egy oszlopa egy három elembõl álló bináris sorozat, amely 2³ = 8-féleképpen választható meg. A 8 közül az egyik azonosan 0, ez nem lehet A-ban, tehát A oszlopai - a sorrendtõl eltekintve - egyértelmûen meghatározottak:

Tehát a megfelelõ egyenletrendszer:
1·y₁ + 1·y₂ + 1·y₃ + 0·y₄ + 1·y₅ + 0·y₆ + 0·y₇ = 0, 1·y₁ + 1·y₂ + 0·y₃ + 1·y₄ + 0·y₅ + 1·y₆ + 0·y₇ = 0, 1·y₁ + 0·y₂ + 1·y₃ + 1·y₄ + 0·y₅ + 0·y₆ + 1·y₇ = 0,
Ennek valóban 16 megoldása van (azaz egyenletei függetlenek) hiszen y₁, y₂, y₃, y₄ értékei szabadon választhatók és
y₅ = 1·y₁  + 1·y₂ + 1·y₃ + 0·y₄, y₆ = 1·y₁  + 1·y₂ + 0·y₃ + 1·y₄, y₇ = 1·y₁  + 0·y₂ + 1·y₃ + 1·y₄.
A 16 megoldás itt látható:

Látható, hogy - két sor felcserélõdésétõl eltekintve - ugyanahhoz a táblázathoz jutottunk, mint az I. konstrukció esetén.

IV. konstrukció (Négyzetminta)
Térjünk vissza a "Négyzetminta" feladathoz, az elõzõ foglalkozás elsõ példájához! Egész számok helyett számoljunk binárisan (mod 2), azaz a "páros" és "páratlan" szavakat 0 és 1 helyettesítse! A négyzet csúcsaihoz írt 8 számot 16-féle­képpen adhatjuk meg, hiszen a csúcsokhoz elõször írt egy-egy szám összesen 2⁴-féle lehet és ezek már meghatározzák a további négy számot. Így tehát összesen 16 db 0-1 sorozatot kapunk, amelyek egy lineáris halmazt alkotnak, azaz a 16 közül bármelyik két sorozat összege (természetesen koordinátánként és mod 2 értve) is a 16 sorozat között van. A "Négyzetminta" feladatban azt láttuk, hogy e sorozatokban 0, 4 vagy 8 db 1-es lehet, tehát a 16 sorozat egy olyan line­á­ris kódot alkot, amelynek minimális távolsága 4. Ha a nyolcelemû sorozatok egyik, pld az utolsó elemét minde­gyik­ben elhagyjuk, akkor 16 olyan hételemû 0-1 sorozatot kapunk, amelyek közül bármelyik kettõ Hamming távolsága legalább 3. Az I. konstrukció elején leírtak szerint éppen ilyen sorozatokat kerestünk.

Megoldás Az 1. - 2. tulajdonságokból következik, hogy jó 30-as halmazban lehet maradékosan osztani, azaz, ha h₁ I₃₀-ban van és h₂ is I₃₀-ban van és h₁ = n·h₂ + m ahol n, m egész számok, akkor m is I₃₀-ban van. Legyen k egy jó 30-as halmaz (egyik) legkisebb abszolút-értékû, de 0-tól különbözõ eleme. (Ilyen elem biztos van, hiszen 30 benne van a halmazban, így csak az 1, 2, ... 30 eseteket kell végignézni.) Ekkor k minden többszöröse is a jó 30-as halmazban van, de más elem nem is lehet a hal­maz­ban, mert a maradékos osztás k-nál kisebb abszolút-értékû elemet eredményezne. Tehát minden jó 30-as halmaz egy elem összes többszörösébõl áll. 30 pontosan akkor lesz egy ilyen halmaznak eleme, ha a szóbanforgó elem 30 osztója. 8 megfelelõ halmaz van, ezek rendre 30, 15, 10, 6, 5, 3, 2, 1 összes többszöröseibõl állnak.