 |
 |
|
 |
|
| |
Simonyi Gábor Információközlés és gráfelmélet című 2009. szeptember 29-ei előadását lejegyezte Lovas Lia Izabella Bevezető feladat:
Valaki kiválasztja egy sakktábla egy tetszőleges mezőjét. Legalább hány eldöntendő kérdésre van szükségünk ahhoz, hogy biztosan kitalálhassuk a gondolt mezőt?
A feladat megoldása igen egyszerű:
6 kérdés elég, ugyanis minden lépésben feloszthatjuk 2 egyenlő részre a még szóba jöhető mezőket, és rákérdezhetünk, hogy a keresett mező melyik csoportban található. Ilyen módon a 6. kérdés után egyetlen mező marad. Másrészt 6-nál kevesebb kérdés nem lehet elég: ha a még ki nem zárt mezőket következő kérdésünk két nem egyenlő csoportra bontja, akkor mindig lehetséges, hogy a kiválasztott mező a nagyobb elemszámú halmazba kerül.
Felvetődik:
vajon akkor is 6-e a fenti feladat megoldása, ha előre meg kell adnunk az összes kérdésünket, és csak ezután kapjuk meg a válaszokat?
Megoldás:
Igen. Képzeljük el, hogy minden mezőhöz hozzárendelünk egy 6 karakterből álló 0-1 sorozatot. Ezekből éppen különböző létezik, így a sakktábla minden mezejéhez különböző sorozatot rendelhetünk. Első kérdésünk az lehet, 1-es-e a mezőhöz tartozó sorozat első eleme, majd ugyanígy végigmehetünk a sorozat összes bitjén. A 6. kérdés után ismerni fogjuk a mezőhöz rendelt teljes sorozatot, tehát magát a mezőt is kitaláltuk.
Folytatás a PDF fájlban:
|
|
|||||||||||||||||
|
 |
|
 |
|
 |