1.1 Egy cég 10 szériában gyártott egész kg-os súlyokat. Az elsõ szériában 1, a másodikban 2, a harmadikban 3, ... a tizedikben 10 kg-os súlyokat terveztek készíteni. Az azonos szériában készült egyforma súlyokat ugyanabban a ládában tartják, mind a 10 ládára rá van írva, hogy hanyadik szériában készült. Az egyik széria hibás lett, példányai egyforma súlyúak, de ez az érték nem egyezik meg az elõre adott értékkel.
a) Egy kijelzõs mérleg egyszeri használatával kell megtalálnunk, hogy mennyivel nehezebbek vagy könnyebbek a hibás súlyok az elõírtnál.
b)Ezután határozzuk meg, hogy melyik súly szériája lett hibás!
Most is csak a kijelzõs mérleget használhatjuk, és azt is csak még egyszer.
c) Próbáljuk meg általánosítani elõzõ eredményeinket. Fontos volt-e, hogy épp 10 széria volt?
Lényeges-e, hogy rendre épp 1, 2, 3, ... 10 kg-osak a súlyok az egyes szériákban? Fogalmazzuk meg általánosan a feladatot, és adjunk választ az a), b) kérdésekre az általános esetben is!
d) Módosítunk az eredeti feladaton. Tegyük fel, hogy mindegyik súly megfelelõ tömegû (az egyes szériákban rendre 1, 2, ... 10 kg), de elõfordulhat, hogy amikor a ládákat a bennük lévõ súlyok növekvõ sorrendjében betolták a raktárba egymás mellé, akkor két szomszédos ládát felcseréltek. Ezután rakták rájuk sorban a szériaszámokat, amelyek így most növekvõ sorrendben vannak, de lehet, hogy az egyik szomszédos párnál nem a ládában levõ súlyok tömegét jelzik.
Hány méréssel lehet megállapítani, hogy történt-e ilyen tévesztés?

1.2 Egy cég 5 szériában gyártott súlyokat. Az egyes szériákon belül mindegyik súly egyforma tömegû, de nem ismert, hogy mekkorák. Az éppen távol levõ cégvezetõ meg szeretné tudni, hogy milyen tömegû súlyokat gyártottak. Ezért egy mérési ûrlapot küld egyik alkalmazottjának, majd annak kell elvégeznie a méréseket, és visszaküldeni az eredményekkel kitöltött ûrlapot.
Legalább hány mérést kell elvégezni, és mik legyenek ezek a mérések (hogyan töltse ki a cégvezetõ az 1., 2., ..., 5. oszlopokat), ha várható, hogy (legfeljebb) egyszer az alkalmazott hibás értéket ír be a "Mért tömeg" rovatba?
Az ûrlap így néz ki:

	Hány súly legyen az egyes szériákból a mérlegen?					Mért tömeg
	1. széria	2. széria	3. széria	4. széria	5. széria	(kg)
1. mérés
2. mérés
3. mérés
4. mérés
5. mérés
6. mérés
7. mérés
8. mérés
9. mérés
10. mérés
11. mérés

2.1 Írj az üres helyre betût úgy, hogy értelmes magyar szót kapj! Hány megoldás van az egyes esetekben?

_AP,       B_R,       HA_

2.2 Oldd meg az elõzõ feladatot angol nyelven értelmes szavakkal is!

2.3 A következõ szavakban egy-egy betût megváltoztathatsz, de értelmes magyar szót kell kapnod. Hány megoldás van az egyes esetekben?

HÁZ,      KEREK

2.4 Keress olyan legfeljebb ötbetûs magyar szót, amelyben az egyik betût sem lehet úgy megváltoztatni, hogy egy másik értelmes magyar szót kapjunk!

2.5 Keress az elõzõ feladattípusok bármelyikében olyan példát, amelynek az adott szóhosszúság esetén a legtöbb megoldása van!

2.6 Egy négybetûs szóra gondoltam. Alább néhány tippet és a rájuk adott választ láthatod. Csak akkor jelöltem találatot, ha a betû a helyén is volt.

HÁGÓ    0,             TÉLI       2,            BÁNJ     1, FÓKA    1,             FALA    2. Melyik szóra gondolhattam?

3.1 (Dobos Sándor javaslata)
A gyerekek párokat alkotnak. A pároknak az a feladata, hogy kitaláljanak egy kódrendszert, amellyel 0-tól egy általuk megnevezett n számig bármely egész számot le tudnak kódolni egymásnak öt pénzérmével az üres tanári asztalon.
Gondolkodás után minden pár bemondja, hogy meddig tud kódolni (n). A legnagyobbat mondó pár egyik tagja kimegy, a másig bennmarad. A tanár mond a bennmaradónak egy számot a megadott tartományban, amit az lekódol az asztalon. Ezután a másik bejön és kitalálja a számot.

3.2 A feladat ugyanaz, mint a 3.1 feladatban azzal a különbséggel, hogy a tanár kilátásba helyezi, hogy esetleg egy pénzdarabot le fog venni az asztalról, mielõtt bejön az a nebuló, akinek ki kell találnia a számot. Most új kódrendszert, és új n korlátot kell megadnia a pároknak.

4.1 (Pálvölgyi Dömötör példája, Bergengóc példatár 2. 237. fel.)
A budapesti telefonszámok hétjegyûek. Sokszor elõfordul, hogy valaki két szomszédos számot felcserél, ezért téves a hívása. Keress minél egyszerûbb eljárást arra, hogy a hétjegyû számok végére még egy ellenõrzõ számot téve, a központ számcsere (két szomszédos felcserélése) esetén jelezni tudja, hogy a szám téves, és ne kapcsoljon!

4.2 Menjünk át a könyvtárba és nézzük meg sok különbözõ könyv azonosítóját, az úgynevezett ISBN (International Standard Book Number) számot! Próbáljuk meg kideríteni, milyen részekbõl áll, hogyan épül fel ez az azonosító! (Segítség: a legutolsó jegy egy ellenõrzõ jegy, segítségével kiszûrhetõ bármelyik két számjegy felcserélése, illetve bármelyik jegy elírása. A többi jegy három csoportba osztható és a könyv azonosítására szolgál.)

4.3 Gyûjts össze rokonaid, ismerõseid személyi számát (ez nem ugyanaz, mint a személyi igazolvány száma)!

Próbáld meg kitalálni hogyan épül fel ez az azonosító! (Segítség: az utolsó számjegy egy ellenõrzõ jegy, értéke meghatározható a többi jegybõl. Az elõtte álló három számjegy egy sorszám.)

4.4 Olyan adatátviteli nyelvet szeretnénk kidolgozni, amely
I.) csak háromféle betût használ;
II.) minden értelmes szó három betûbõl áll;
III.) Ha egy értelmes szóból csak egy betût nem ismerünk (de tudjuk, hogy hanyadikat), akkor azt már ki tudjuk találni a többi betûjébõl.
Legfeljebb hány értelmes szó lehet egy ilyen nyelvben?

4.5 Bizonyítsd be, hogy egy kód pontosan akkor 1-hiba javító, ha bármelyik két kódszó legalább három helyen különbözik egymástól!

4.6 Keress háromféle betû alkalmazásával minél több szóból álló négybetûs 1-hibajavító kódot!

4.7 Összehasonlítunk három kódot! Mindhárom kód kilenc szóból áll, mindegyik egy hárombetûs ABC-t használ.
k₁) A legegyszerûbb: A szavak kétbetûsek, a kilenc kódszó az összes kétbetûs szó.
k₂) Mindent háromszor: A szavak hatbetûsek és úgy készülnek, hogy a kétbetûs szót háromszor írjuk le egymás után.
k₃) A sûrû: A szavak négybetûsek, a 4.6 feladatban meghatározott 1-hiba javító tökéletes kódot alkotják.
Tegyük fel, hogy egy betû a kommunikáció során 10% eséllyel megváltozik és 90% eséllyel jól továbbítódik. k₂ és k₃ esetén a kiolvasott jelsorozatot mindig a tõle legkevesebb jelben eltérõ kódszóra változtatjuk. Ha ez nem egyértelmû, akkor nem javítunk. Határozzuk meg a három esetben külön-külön, hogy mi az esélye, hogy egy szót úgy olvasunk ki, ahogy elküldték!

4.8 Legyen most a betûhiba esélye q, a hibátlan betûé pedig p = 1-q. (A 4.7 feladatban p = 0,9, q = 0,1 volt.) Tekintsük át p minden lehetséges értékét és rakjuk sorrendbe a k₁, k₂ és k₃ kódokat aszerint, hogy melyiknél esélyesebb egy szó helyes kiolvasása!

4.9 Keress kétféle betû alkalmazásával minél több szóból álló k-betûs 1-hibajavító kódot, k = 1;2;... ;6 esetén! Töltsd ki az alábbi táblázatot!

4.10 Ha adott egy négyzet alakú H_i számtáblázat, akkor elkészíthetjük a kétszer akkora oldalhosszúságú

számtáblázatot. Induljunk ki az 1×1-es H₁ = (1) "számtáblázat"-ból, és képezzük a
majd a H₄, H₈, H₁₆, H₃₂  számtáblázatokat. H₃₂-nek már 32 sora van, mindegyikben egy 32 hosszú számsorozat, csupa 1-gyel és (-1)-gyel. Tekintsük ezt a 32 sorozatot és (-1)-szereseiket. Álljon kódunk ebbõl a 64 sorozatból, csak a (-1)-eket cseréljük ki 0-kra. Határozzuk meg az így kapott bináris kód minimális távolságát![1]

4.11 Bizonyítsd be, hogy egy kód pontosan akkor
a) k-hiba javító, ha minimális távolsága legalább 2k+1;
b) k-hiba jelzõ, ha minimális távolsága legalább k+1;
c) k-törlés javító, ha k-hiba jelzõ!

5.1 (Dobos Sándor példája)
Számrontó Rezsõnek két módszere van egy szám elrontására. Vagy egy számjegyet tetszõlegesen megváltoztat (pld. 5437→5487), vagy két számjegyet kicserél (pld. 5437→3457). Egyszer véletlenül az asztalon hagytam egy cetlit a másológép négyjegyû belépési számával. Rezsõ ezt meglátta és rögtön átjavította 1323-ra. Szerencsére észrevettem, és visszajavítottam az eredeti számra. De, amikor legközelebb lehetõsége adódott Rezsõ megint elrontotta a cetlin lévõ számot, így most 1213 van ráírva. Mi lehet a másológép belépési száma?

5.2 Egy hajó és utasai, összesen 100 fõ, Ungabunga szigetén az emberevõk fogságába esett. Tudják, hogy másnap reggel a kannibálok leültetik õket egymás mögé, és mindegyikük fejére egy-egy piros vagy kék sapkát húznak. Mindenki csak az összes elõtte ülõ ember fején lévõ sapkát fogja látni, a sajátját és a mögötte ülõkét nem. A leghátsó embertõl kezdve sorban mindenki hangosan mondhat majd egy színt: pirosat vagy kéket. A végén azt engedik szabadon, aki saját sapkája színét mondta, aki nem találta el, azt bizony megeszik. A kannibálok szigorúak, ha bárki mást tesz, minthogy a lehetõ legegyszerûbben kimondja a "piros" vagy a "kék" szót, akkor senkinek sem kegyelmeznek.
A foglyoknak még egy esélye van. Most este még összebeszélhetnek. Szeretnék, hogy minél többen megszabaduljanak. Hány fogoly tud biztosan megmenekülni?

Könnyítés: oldjuk meg elõbb a feladatot abban az esetben, ha tudjuk, hogy összesen pontosan
a2) két;
a10) tíz;
piros sapka van a 100 között!

5.3 Gondoljuk végig az 5.2 feladatot kettõ helyett három színnel! Minden rab fején háromféle sapka lehet, és mindenki háromféle színt is mondhat.

5.4 Lépjünk tovább az 5.2-5.2 feladatokkal! Mi a helyzet n szín esetén?

5.5 A térbeli sakktáblán a bástya a tábla oldaléleivel párhuzamosan tud lépni. Legfeljebb hány bástya helyezhetõ el a táblán úgy, hogy semelyik kettõ se üsse egymást, ha a tábla
a) 3×3-as?
b) 8×8-as?

5.6 Bergengóciában a totó, a bajnokságnak megfelelõen csak 4 mérkõzést tartalmaz. Minden mérkõzés eredményére háromféleképpen lehet tippelni: 1-gyel, 2-vel vagy X-szel. Egy szelvényen csak egy tipposzlop van.
a) Hány szelvényt kell venni ahhoz, hogy biztosan legyen telitalálatunk?
b) És ahhoz, hogy biztosan legyen olyan szelvényünk, amely legalább 3 találatos?

5.7 A szenvedélyes játékosok már régóta keresik az olyan nyerõesélyes tipprendszereket, úgynevezett totókulcsokat, mint amilyet az 5.6 feladatban is kerestünk. Mégis, már "kicsinek" tûnõ esetekben sem ismeretes, hogy legkevesebb hány szelvény kell bizonyos számú találat eléréséhez.

Az alábbi táblázat[2] mutatja, hogy mit tudott a világ 1995-ben. n a mérkõzések számát jelöli, r pedig azt mutatja, hogy legfeljebb hány találatot engedünk ki a kezünkbõl. Az 5.6 feladat az n = 4, r =1 esetnek felel meg.

Látható, hogy elég kevés konkrét eredmény ismert. Az alábbi kérdés az egyik pontos eredményre kérdez rá.
Mutassuk meg, hogy a 13 mérkõzésbõl álló totón legalább 59049 szelvényt kell kitölteni ahhoz, hogy biztosan elérjünk legalább 12 találatot!

5.8 a) Az 1, 2, 3, ... 16 számok közül kell kitalálni egyet barkochba kérdésekkel. Legalább hány kérdésre van szükség?
b) És ha a kérdéseket elõre le kell írni, azaz a következõ kérdés nem függhet az elõzõre kapott választól?

5.9 Most is az 1, 2, 3, ...16 számok közül kell kitalálni egyet barkochba kérdésekkel. Kérdéseinket elõre le kell írni és nincs befolyásunk arra, hogy a gondoló milyen sorrendben nézi és válaszolja meg azokat.[3]
Hány kérdéssel tudjuk biztosan kitalálni a gondolt számot, ha várhatóan egyszer (legfeljebb egyszer) téves választ kapunk?

5.10 (Dienes Péter javaslata)
Hanyag Hugó az 1, 2, 3, ..., 16 számok egyikére gondolt. Egy-egy cetlire kell fölírni kérdéseinket, s mind odaadni neki, majd amikor ráér egyszerre mindegyikre válaszol fog. De lehet rá számítani, hogy az egyik választ elveszti mielõtt az eljutna hozzánk. Legalább hány kérdésre van így szükség ahhoz, hogy kitaláljuk a gondolt számot?

5.11 (Juhász Istvántól és Szegedy Balázstól is hallottam)
Egy kém az ellenséges ország televíziójánál dolgozik. Esténként alkalma van az adásba kerülõ 8×8-as fekete fehér tábla egyetlen mezõjének színét megváltoztatni. Nem feltétlenül szükséges változtatnia. Sajnos sohasem tudja elõre, hogy milyen mintázatú lesz a 64 mezõ, amikor eléje kerül. Hányféle információt tud így küldeni a TV-n keresztül?

6.1 - Négyzetminta Egy négyzet csúcsaiba egy-egy egész számot írtunk, majd mindegyik csúcs mellé még odaírtuk az abba a csúcsba írt számnak a szomszédos csúcsokba írt számokkal vett összegét. Hány páratlan szám lehet az így kapott nyolc szám között? Adjuk meg az összes lehetõséget!

6.2 - "Jó-30-as" Az egész számok egy I₃₀ részhalmazát "jó 30-as"-nak nevezzük, ha teljesülnek rá az alábbi feltételek:
1. Ha h I₃₀-ban van és n tetszõleges egész szám, akkor n·h is I₃₀-ban van.
2. Ha h₁ és h₂ is I₃₀-ban van, akkor I₃₀-ban van h₁ + h₂ is.
3. A 30 benne van I₃₀-ban.
Az egész számok halmazának hány "jó 30-as" részhalmaza van?

6.3 - "Ideális 101-es" Ebben a feladatban a természetes számok bizonyos részhalmazait keressük. A számokat mindig kettes számrendszerben leírva képzeljük, illetve alább így is említjük õket. Két számot nem a szokásos módon adunk össze, hanem kettes számrendszerbeli alakjuk megfelelõ jegyeit modulo 2, és átvitel nélkül adjuk össze  (pld 1100110 + 10011 = 1110101).
A természetes számok (pontosabban azok kettes számrendszerbeli alakjainak) egy I₁₀₁ részhalmazát "ideális 101-es"-nek nevezzük, ha
1. Ha h I₁₀₁-ben van, akkor h0 is I₁₀₁-ben van; (h0 a h dupláját, tehát azt a számot jelöli, amelyet úgy kapunk, hogy h mögé írunk egy 0-t)
2. Ha h és j is I₁₀₁-ban van, akkor h + j is ott van.
3. 101 is I₁₀₁-ben van (itt 101 az egy-nulla-egy számot, azaz az 5-öt és nem a százegyet jelenti).
a) Hány véges, "ideális 101-es" részhalmaza van a természetes számok halmazának?
b) Oldjuk meg az "ideális 101-es" feladatot 101 helyett mindenütt 1001-gyel!

6.4 - Hétszögminták Ebben a feladatban egy szabályos hétszög csúcsaira írunk 0-t vagy 1-et. Összesen 2⁷=128 ilyen kitöltés van. A kitöltések egy I₇ részhalmaza "7-szögre ideális", ha
1. Ha h eleme I₇ -nek, akkor h bármely (n·360°/7-kal való) elforgatottja is I₇-ben van.
2. Bármely két I₇-beli kitöltés csúcsonként és mod 2 számított összege is I₇-ben van.
A kitöltéseknek hány "7-szögre ideális" részhalmaza van?