IX.B. Számrendszerek Megoldások

IX.B. Számrendszerek Megoldások 1. Szilviának a végén 8 kagylója maradt. Nézzük, hányat dobott HO" (OV]|U HJ\HW PDMG D PiVRGLN OpSpVEHQ PpJ NHWWW WHKiW összesen hármat. A feladat megoldása: 8 + 3 = 11 kagylóval játszott. Az alábbi ábrán ez jól látható (téglalapok jelzik a csoportosítást, az áthúzott kagylók pedig visszakerültek a tengerbe). $]HOVFVRSRUWRVtWiVXWiQ

A második csoportosítás után:

És a végállapot:

0HJMHJ\]pV(OVUiQp]pVUHQHPOiWV]LNPLDNDSFVRODWHIHODGDW és a számrendszerek között. A számlálás mindig csoportok létrehozásával jár. Ha kettes csoportokat (azaz párokat) képe]QNDNNRUNHWWHVV]iPUHQGV]HUKH]YH]HWPRGHOOWNDSXQN 149

$ IHQWL iEUiNRQ MyO OiWV]LN KRJ\ D NO|QE|] FVRSRUWRVtWiVRN PLQGLJD]HO]Oépésben keletkezett csoportok párosítását jelenWLN D]D] HOV]|U PDJXNDW D NDJ\OyNDW UHQGH]L SiUED PDMG D keletkezett párokat párosítja (így kap négyeseket), majd ezeket a négyeseket párosítja (nyolcasok), és így tovább. Az eldobott kagylók pedig mindig az új párosításban páratlanul maradt, az HO] SiURVtWiV VRUiQ NHOHWNH]HWW FVRSRUW /iWMXN D]W LV KRJ\ KD Szilvia nem hagyja abba a megkezdett algoritmust, akkor a követNH]OpSpVEHQ16-os csoportokat kellene képeznie (ilyen nem lett volna), és a „páratlanul” maradt 8-as csoportot pedig vissza kellene dobnia a vízbe. Írjuk fel, hogy lépésenként hány csoportot dobott el: 1,1,0,1. Ez a IHODGDW PHJROGiViW MHOHQW 11-es szám kettes számrendszerbeli DODNMD YLVV]DIHOp OHtUYD 1LQFV HEEHQ VHPPL PHJOHS KLV]HQ Szilvia éppen az általunk jól ismert átalakítási eljárást végezte el számunkra egy kissé szokatlan módon: 11 1 5 1 2 0 1 1 0  $ IHOJ\HOQHN QDJ\RQ HJ\V]HU& GROJD YDQ KD FVDN DUUD kíváncsi, hány zsák hamis tallért talált, ugyanis mindegyik zsákból kivéve egy-egy tallért és azt mérlegre téve, a mérleg amennyivel többet mutat 50 dkg-nál, amennyi hamis tallért tartalmazó zsák van. Így azonban nem tudja megállapítani, hogy melyik zsákban vannak a hamisak, mert például 52 dkg esetén hamis tallér lehet bármelyik két zsákban. Nyilvánvaló, hogy ha mindegyik zsákból ugyanannyi tallért veszünk ki, akkor nem tudjuk megtalálni a hamis zsákokat. Ezért FpOV]HU&D]HOV]ViNEyO1-et, a másodikból 2-t, a harmadikból 4HWDQHJ\HGLNEO8-DWpVD]|W|GLNEO16-ot kivenni. Ha mindegyik zsák valódi tallérokat tartalmazna, akkor 310 dkg-ot mérnénk. ,QQHQWO HOpJ FVDN D PpUW W|EEOHWW|PHJUH ILJ\HOQL +D D PpUpV eredménye például 321 dkg, akkor 11 dkg-mal kaptunk többet a QRUPiOLVQDN WHNLQWKHW 310 dkg-nál. A 11 pedig csak egyféleképpen jöhet ki a felsorolt számok összegeként: 1+2+8, vagyis a hamis talOpURND]HOVDPiVRGLNpVDQHJ\HGLN]ViNEDQYDQQDN 150

Vegyük észre, hogy éppen a kettes számrendszer helyi értékeivel próbálkoztunk (1, 2, 4, 8, 16). Ez nem véletlen, ugyanis ha a zsákokat sorba rakjuk, és 1-gyel jelöljük a hamis, 0-val az igazi tallérokaWWDUWDOPD]y]ViNRNDWDNNRUHJ\|WMHJ\&0-t és 1-et tartalmazó számot kapunk. Mivel éppen a kettes számrendszer helyi értékeit használtuk, ezt a csak 0-t és 1-HW WDUWDOPD]y |WMHJ\& V]iPRW HJ\pUWHOP&HQ iWDODNtWKDWMXN HJ\ Wt]HV V]iPUHQGV]HUEHOL számmá. Ez a szám a hamis tallérok számát adja, ami a mérleg iOWDO PpUW W|EEOHWEO LV PHJiOODStWKDWy 9DJ\LV PpUpV XWiQ QLQFV más dolgunk, mint a mért többletet, azaz a hamis érmék számát fölírni kettes számrendszerben, és az így kapott szám 5 számjegye (1 vagy 0) megmutatja, mely zsákokban vannak a hamis tallérok. Megjegyzés: Érdemes elgondolkodni azon, hogy miért éppen a kettes számrendszert hívtuk segítségül.  $] HO] IHODGDWKR] KDVRQOyDQ LWW LV GRER]RQNpQW NO|QE|] V]iP~PLQWDYpWHOOHOHOpUKHWKRJ\HJ\PpUpssel megállapítsuk az HJ\HV GRER]RNEDQ WDOiOKDWy FVRNROiGpN IDMWiLW $] HOV GRER]EyO 1-et, a másodikból 3-at, a harmadikból 9 csokoládét kell kivenni. A OHJNLVHEE W|PHJ DPHO\ tJ\ PpUKHW 1300 g (mind mogyorós), a legnagyobb 1326 g (mind kekszes). De nem csak ezekben az HVHWHNEHQ HJ\pUWHOP& D GRER]RNEDQ OpY FVRNROiGpN IDMWiMD Például 1317 g esetén a mért tömeg minimálistól való eltérése csak egyféleképpen adódhat: 2 ⋅1 + 2 ⋅ 3 + 1 ⋅ 9 = 17 . Ezek szerint az HOVGRER]EDQ102 g-os, a második dobozban szintén 102 g-os, a harmadik dobozban pedig 101 g-os táblák vannak, vagyis a dobo]RN iOWDO WDUWDOPD]RWW FVRNROiGpN IDMWiMD VRUUHQGEHQ D N|YHWNH] kekszes, kekszes, tejes. Mogyorós csokoládé nincs. /iWKDWy D KDVRQOyViJ D] HO]IHODGDWWDO$KiURPIpOHFVRNROiGé szükségessé teszi a legalább hármas alapú számrendszer használatát. Ha a mogyorósat 0-val, a tejeset 1-gyel a kekszeset 2-vel jelöljük, akkor a 000, 001, 002, 010, 011, 012, 020, 021, 022, 100,…, 221, 222OHKHWVpJN|]ONHOODPpUpVDODSMiQHJ\HWNLYiOasztani. A hármas számrendszerrel való kapcsolat miatt ez a mérési eredPpQ\LVPHUHWpEHQHJ\pUWHOP&HQPHJWHKHW  $ N|YHWNH] PyGV]HUUHO FVDN KiURP PpUpV V]NVpJHV H] D minimális): A 8 HPEHUEO 4-et megvizsgálnak a géppel. Így megtudják, hogy a kiválasztott négy ember között van-e a 151

terrorista. Akármi is a vizsgálat eredménye, most már csak 4 J\DQ~VtWRWW YDQ (EEO D 4-EO NHWWW PHJYL]VJiOQDN D JpSSHO 9DJ\DNHWWN|]OD]HJ\LNDWHUURULVWDYDJ\DPiVLNNHWWN|]O az egyik. A géppel ezt el tudják dönteni. Most már csak két gyanúsított van, akik közül elég az egyiket megvizsgálni. Összesen 3YL]VJiODWYROWKiURPHOKtYiVVDOYDJ\LVH]|VV]HVHQ3 óra 3 percig tart körülbelül. (Tegyük fel, hogy Szimatnak az eredményeket telefonon jelentik a kapitányságról, tehát nem igényel külön LGWD]HUHGPpQ\HNHOMXWWDWiVDDUHSOWpUUH $]iEUDDYL]VJiODtok egy lehetséges menetét mutatja. 1 2 3 4 5 6 7 8 ¨ ¨ ¨ x ¨ ¨ ¨ ¨ gyanúsítottak: 1,2,3,4,5,6,7,8 1. vizsgálat, a vizsgált ¨ ¨ ¨ x személyek: 1,2,3,4 1 óra a vizsgálat eredménye: 10 perc köztük van a terrorista gyanúsítottak: 1,2,3,4 ¨ ¨ ¨ x 2. vizsgálat, a vizsgált ¨ ¨ személyek: 1,2 1 óra a vizsgálat eredménye: 10 perc nincs köztük a terrorista gyanúsítottak: 3,4 ¨ x 3. vizsgálat, a vizsgált ¨ személy: 3 1 óra a vizsgálat eredménye: 10 perc QHPDWHUURULVWD gyanúsított: 4 x Összesen 3,5 óra Már csak az a kérdés, le lehet-e rövidíteni a nyomozás idejét. Lehet-H NHYHVHEEV]HU PHJWHQQL D] XWDW D UHSOWpU pV D UHQGUkapitányság között? A fenti módszerrel az a probléma, hogy a PiVRGLN YL]VJiODWRW QHP HMWKHWMN PHJ DGGLJ DPtJ D] HOV vizsgálat eredményét nem ismerjük. Kell-e tudnunk menet közben az egyes vizsgálatok eredményét, vagy össze tudunk állítani egy olyan vizsgálati tervet, amely független a „részeredmények”-WO" Mivel a gép egyszerre több felvétel tárolására is alkalmas, érdePHVHEE My VRN IHOYpWHOW NpV]tWHQL XWiQD D]RNDW D UHQGUNDSLWiQ\ViJRQ HOKtYDWQL (]]HO PHJVSyUROKDWQiQN D] LGLJpQ\HV sziOOtWiVWDUHSOWpUpVDUHQGUNDSLWiQ\ViJN|]|WW(J\LNOHKHWség, hogy mindenkit egyesével megvizsgálunk (az utolsó gyanú152

sított utast nem kell). Így az 1 órás úton kívül 7 felvétel-HOKtYiV lesz, ami összesen 2 óra 10 percet vesz igénybe. Ez már lényHJHVHQMREED]HO]3 és fél órás eredménynél. (QQpO PpJ MREE HUHGPpQ\ LV HOpUKHW (]W PXWDWMD D] DOiEEL táblázat: 1 2 3 4 5 6 7 8 a gyanúsítottak: ¨ ¨ ¨ x ¨ ¨ ¨ ¨ 1,2,3,4,5,6,7,8 1. vizsgálat: 1,2,3,4 ¨ ¨ ¨ x 2. vizsgálat: 1,2,5,6 ¨ ¨ ¨ ¨ 3. vizsgálat: 1,3,5,7 ¨ ¨ ¨ ¨ 1 óra Eredmények: 1. pozitív 10 perc 2. negatív 10 perc 3. negatív 10 perc gyanúsított: 4 x Összesen 1,5 óra A feladat fenti megoldása és a kettes számrendszer közötti kapcsolat könnyen megmutatható. Számozzuk meg a 8 gyanúsítottat 0-tól 7-ig. Ekkor kettes számrendszerben felírva az a cél, hogy megtaláljunk egy 000 és 111 közötti számot. 000 001 010 011 100 101 110 111 1. vizsgálat ¨ ¨ ¨ x 2. vizsgálat ¨ ¨ ¨ ¨ 3. vizsgálat ¨ ¨ ¨ ¨ eV]UHYHKHWMNKRJ\D]HOVYL]VJiODWEDQpSSHQD]RNDWDJ\DQ~VtWRWWDNDW YL]VJiOMXN DNLN VRUV]iPiQDN HOV V]iPMHJ\H 0. Ha az HOV YL]VJiODW SR]LWtY DNNRU D] HOV V]iPMHJ\ 0, különben 1. Hasonlóan a második és a harmadik vizsgálat eldönti a második és a harmadik számjegyet. Megjegyzés: A teljes megoldás megkövetelné annak a bizonyítását is, hogy három mérésnél kevesebbel nem megoldható a IHODGDW(WWOPRVWHOWHNLQWQN

153