Kódok 1. szakkör

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?

Megoldás: a) Rakjunk föl a mérlegre mindegyik súlyból egyet-egyet, és nézzük meg mennyivel tér el a tömeg 1+2+3+4+5+6+7+8+9+10=55 kg-tól.

b) Rakjunk a mérlegre az elsõ szériából 1, a másodikból 2, ..., a tizedikbõl 10 súlyt és nézzük meg mennyivel tér el a tömeg 1·1 + 2·2 + 3·3 + 4·4 + 5·5 + 6·6 + 7·7 + 8·8 + 9·9 + 10·10 kg-tól. Az eltérés és az elõzõ mérésben kapott hiba hányadosa épp a hibás súlyok szériaszáma.
Nem ez az egyetlen jó megoldás. Az a lényeg, hogy mindegyik szériából különbözõ számú súlyt tegyünk föl a mérlegre.

c) Ha n széria van, és az egyes szériákban a súlyok tervezett tömege rendre x₁, x₂, x₃, .., x_n, de az egyik széria hibás, akkor x₁ + x₂ + x₂ + ... + x_n, illetve x₁ + 2x₂ + 3x₂ + ... + nx_n lekérdezése megoldja a két feladatot.

d) I. mego. A b)-ben adott mérés most is jó lesz. Ha pld a 4. és 5. szériát felcseréljük, akkor a várt és a tényleges tömeg különbsége:
4·4 + 5·5
4·5 + 5·4
4·(-1)+5·1 = 1.

d) II. mego. Tegyünk fel az elsõtõl kezdve minden második szériából egyet-egyet a mérlegre! Az 1+3+5+7+9 összeget várjuk eredménynek. Ha volt csere, akkor nem ennyit kapunk.

Tanári kérdés: a fenti két megoldás között van-e olyan, amely akkor is jó, ha nem szomszédos ládákat cseréltek föl? És olyan, ami akkor is kimutatja a tévedést, ha nem volt csere, de az egyik széria hibás? (Az I. megoldás mindkettõre jó.)

5.1 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? Dobos Sándor

Megoldás: négy megoldás is van: 1223, 1313, 1233, 1123.

Megoldás: a) 9-nél több bástya nem helyezhetõ el, mert a 9 oszlop mindegyikében legfeljebb egy lehet. 9 elhelyezhetõ, az alábbi ábrán a kocka 3 rétege külön-külön látható, a korongok a bástyákat jelzik. Egy táblán belül semelyik két bástya sincs ugyanabban a sorban vagy oszlopban, a különbözõ táblákon lévõ bástyák soha sincsenek a tábla ugyanazon mezõjén.

b) 64 a megoldás. A konstrukció az elõzõhöz hasonló, a fõátló nyolc bástyáját ciklikusan fölfelé toljuk.

Megoldás: a) Egy-egy kérdés a szóbajövõ számok halmazát két részhalmazra bontja: azokra, amelyekre igen a válasz (ha az a szám a gondolt szám) és azokra, amelyekre nem a válasz. "Rossz esetben" olyan választ kapunk, amely azt mutatja, hogy a nagyobb, pontosabban a nem kisebb részhalmazban van a gondolt szám. Ezért, ha biztosra megyünk nem tehetünk jobbat, minthogy kérdéseinkkel megfelezzük a lehetõségeket. 4 kérdés kell a kitaláláshoz, és ennyi elég is.

b) Házi feladatnak maradt

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

I. megoldás (Mindent háromszor)
15 mérés elég. Sorra vesszük a szériákat, mindig csak egy súlyt veszünk ki belõlük és azt a súlyt háromszor is megmérjük. Így a jó eredményt mindegyik szériánál legalább kétszer is megkapja a cégvezetõ, így tudni fogja a helyes eredményeket.

Megjegyzés: ez a módszer jó, de nem optimális.

II. megoldás(Az I. megoldás javítása)
Az elõzõ módszert alkalmazom, de csak kétszer mérek meg minden súlyt, majd kizárólag azt teszem fel harmadszorra is, amelynél két különbözõ eredményt kaptam. Így 11 méréssel oldom meg a feladatot.

Megjegyzés: ez a módszer nem szabályos, mert nincs lehetõség a cégvezetõnek menet közben beleszólni, hogy melyiket mérje meg még egyszer az alkalmazott.

III. megoldás (Újabb javítás)
Én is csak kétszer mérek meg minden súlyt, végül pedig mindegyik szériából egyet-egyet tetetek fel a mérlegre, így 11 méréssel oldom meg a feladatot. Ha az egyesével mért súlyok egyikénél a két mérés nem ugyanazt az eredményt adta, akkor tudhatjuk, hogy az utolsó mérés jó, így annak eredményébõl, és a másik négy súly tömegébõl meghatározható a bizonytalan eredmény is.

IV. megoldás 7 méréssel oldom meg a feladatot. Az elsõ öt mérésben csak egy-egy súlyt teszünk a mérlegre, az elsõben az elsõ, a másodikban a második, ... az ötödikben az ötödik szériából. A hatodik mérésben öt súlyt, mindegyik szériából egyet-egyet teszünk a mérlegre. A hetedik mérésben 15 súlyt, az elsõ szériából egyet, a másodikból kettõt, ... az ötödikbõl ötöt teszünk a mérlegre. Ha a hatodik vagy a hetedik mérés eredménye összhangban van az elsõ öt mérés eredményével, akkor az elsõ öt mérés mindegyikének jó az eredménye, tudjuk a tömegeket. Ha a hatodik és a hetedik mérés eredménye sincs összhangban az elsõ öt mérés eredményével, akkor az elsõ öt között van a hiba. Most az 1.1 feladat a) és b) része megoldásának alapján készen vagyunk.

Hat mérés nem elég. Ennek igazolására késõbb térünk vissza.

Házi feladat (5.8-hoz) Egy mérési tervhez meg kell adni az elõírt mérések számát - a továbbiakban ezt n jelöli - továbbá nemnegatív egész számokkal kell kitölteni az ûrlap 1., 2., 3., 4., 5. oszlopait. Jelölje az így kapott számtáblázat i-edik sorának (i = 1, 2, ..., n) j-edik oszlopába (j = 1, 2, 3, 4, 5) írt számot a_ij (a_ij természetes szám). Tehát a_ij -vel jelölöm az i-edik mérésnél a j-edik szériából vett súlyok számát. Határozzunk meg az a_ij számokkal kapcsolatos olyan algebrai feltételt, amely azzal ekvivalens, hogy a mérésekbõl meghatározhatók a súlyok (feltéve, hogy legfeljebb egy hibás az eredmények közül).

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!

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!