Kezdőlap


Feladat:	N.35	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Braun Gábor , Csörnyei Marianna , Futó Gábor
Füzet:	1995/március, 160 - 163. oldal		PDF \| MathML
Témakör(ök):	Egyéb feladványok, Algoritmikus eljárások, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1994/május: N.35

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Induljunk ki a kapcsolók egy tetszőleges állásából. Feltehetjük, hogy most a lámpa színe piros. Ha az összes kapcsoló állását megváltoztatjuk, akkor a lámpa színe is megváltozik. Végezzük el ezt egyesével: változtassuk meg először az első, azután a második kapcsolót, és folytassuk ezt egészen addig, amíg a lámpa színe először meg nem változik. Legyen az a kapcsoló, amelynél a lámpa színe először megváltozott, a $k$ -adik. Feltehetjük, hogy a lámpa színe kék lett.
I. Vizsgáljuk most azt az állást, amikor a lámpa színe még piros volt, de a következő lépésben már kék. Nevezzük a kapcsolók itteni állását $O$ állásnak, (tehát lehet, hogy az első kapcsolónak a zöld a $O$ állása, a másodiknak a piros és így tovább). Ezek után a $k$ -adik kapcsoló állását megváltoztattuk, és a lámpa kék lett. Legyen a $k$ -adik kapcsoló új állása az 1-es. Tehát:

\begin{matrix} k-adik kapcsoló & többi kapcsoló & lámpa színe \\ 0 & 0, 0,..., 0 & piros \\ 1 & 0, 0,..., 0 & kék \end{matrix}

Állítsuk most a

k

-adik kapcsolót a harmadik lehetséges állásba (jelöljük ezt 2-vel), a többit pedig, a 0-tól különböző tetszőleges állásba (1 vagy 2). Ekkor a táblázat első és második sorához képest is megváltozott minden kapcsoló állása, így a lámpa színe sem piros, sem kék nem lehet, azaz zöld.

\begin{matrix} k-adik kapcsoló & többi kapcsoló & lámpa színe \\ 0 & 0, 0,..., 0 & piros \\ 1 & 0, 0,..., 0 & kék \\ 2 & \binom{1}{2},\binom{1}{2},...,\binom{1}{2} & zöld \end{matrix}

(Az egymás alá írt

\binom{1}{2}

azt jelenti, hogy bármelyiket választhatjuk az 1 és 2 közül, minden egyes kapcsolónál külön-külön.)
Állítsuk most a

k

-adik kapcsolót 1-es, a többit pedig tetszőlegesen vagy 1-es, vagy 2-es állásba. Ekkor a táblázat első sorához képest minden kapcsoló állása megváltozott, így a lámpa színe nem lehet piros. De zöld sem lehet, mert ha minden 1-et 2-re és minden 2-t 1-re változtatunk, akkor a táblázat harmadik sora alapján zöld lesz. Így biztos, hogy kék:

\begin{matrix} k-adik kapcsoló & többi kapcsoló & lámpa színe \\ 0 & 0, 0,..., 0 & piros \\ 1 & 0, 0,..., 0 & kék \\ 2 & \binom{1}{2},\binom{1}{2},...,\binom{1}{2} & zöld \\ 1 & \binom{1}{2},\binom{1}{2},...,\binom{1}{2} & kék \end{matrix}

Ha most a

k

-adik kapcsolót 0-ra, a többit tetszőlegesen 0-ra, 1-re vagy 2-re állítjuk, akkor a fentiekhez hasonló módon a lámpa színe nem lehet zöld a táblázat 3. sora miatt (mivel az összes kapcsolót megváltoztathatjuk úgy, hogy a 0-kat és 1-eket 2-re változtatjuk, a 2-ket pedig 1-re, így egy 3. sorbeli állást kapunk). De ugyanígy a 4. sor miatt a lámpa színe kék sem lehet, ezért biztos, hogy piros. Tehát:

\begin{matrix} k-adik kapcsoló & többi kapcsoló & lámpa színe \\ 2 & \binom{1}{2},\binom{1}{2},...,\binom{1}{2} & zöld \\ 1 & \binom{1}{2},\binom{1}{2},...,\binom{1}{2} & kék \\ 0 & bármi & piros \end{matrix}

II. Legyen most a

k

-adik kapcsoló állása 1, a többié tetszőlegesen 0, 1 vagy 2. Ha most az 1-eseket és 0-kat 2-re, a 2-eseket 1-re változtatjuk, akkor egy 1. sorbeli állást kapunk, így a lámpa színe nem lehet zöld. Ha pedig a

k

-adikat 0-ra, a többit pedig bárhogyan megváltoztatjuk, akkor egy 3. sorbeli állást kapunk, így a lámpa színe nem lehet piros. Tehát biztosan kék:

\begin{matrix} k-adik kapcsoló & többi kapcsoló & lámpa színe \\ 0 & bármi & piros \\ 1 & bármi & kék \end{matrix}

III. Legyen végül a

k

-adik kapcsoló állása 2, a többié tetszőleges. Ha a

k

-adikat 0-ra, a többit tetszőlegesen változtatjuk, akkor egy 1. sorbeli, ha pedig a

k

-adikat 1-re, a többit pedig tetszőlegesen változtatjuk, akkor egy 2. sorbeli állást kapunk. Így a lámpa színe se nem piros, se nem kék, tehát zöld, és a táblázat:

\begin{matrix} k-adik kapcsoló & többi kapcsoló & lámpa színe \\ 0 & bármi & piros \\ 1 & bármi & kék \\ 2 & bármi & zöld \end{matrix}

Tehát a lámpa állása csak egy kapcsolótól függ (a

k

-adiktól).

Csörnyei Marianna (Fazekas M. Főv. Gyak. Gimn., IV. o.t.)

Megjegyzések. 1. Tegyük fel, hogy most nem feltétlenül véges az asztalra szerelt kapcsolók száma. Nevezzük dominánsnak a kapcsolók egy részhalmazát, ha ők maguk már meghatározzák a körte színét abban az értelemben, hogy ha ebben a halmazban mindegyik kapcsolónak ugyanaz a szín az állása, akkor a körte is azzal a színnel ég. Megmutatható, hogy két domináns rész metszete is domináns, továbbá egy kapcsolórész vagy a komplementere mindig domináns. A kapcsolókra vonatkozó első feltétel azt jelenti, hogy van domináns rész, ti. az összes kapcsolók halmaza. Világos, hogy az üres halmaz nem domináns, míg egy domináns részhez néhány kapcsolót hozzávéve ismét domináns részt kapunk. Halmazelméleti kifejezéssel élve azt mondhatjuk, hogy a domináns részek ultraszűrőt alkotnak.
Fordítva, ha a kapcsolók halmazán adva van egy ultraszűrő, azaz részhalmazok egy olyan nem üres rendszere, amely az üres halmazt nem tartalmazza, amely metszetzárt, bármely halmazt vagy annak komplementerét tartalmazza, továbbá felszálló, azaz a benne levő részhalmazok minden bővítését is tartalmazza, akkor a körte színének a kapcsolóktól való függését beláthatjuk úgy, hogy a domináns részek a szóban forgó ultraszűrő elemei legyenek. Tetszőleges kapcsolóállásnál ui. ‐ amint az belátható ‐ a piros, a kék és a zöld kapcsolók ‐ mint részhalmazok ‐ közül pontosan az egyik eleme az ultraszűrőnek: világítson a körte ezzel a színnel. Könnyen ellenőrizhető, hogy így és csak így definiálható a körte színe a kívánalmaknak megfelelően. A feladat általánosabb változata tehát lényegében a kapcsolók ultraszűrőiről szól, és az eredeti változat úgy is megfogalmazható, hogy egy véges halmaz minden ultraszűrője főszűrő, azaz tartalmaz egyelemű részhalmazt.
2. A megoldásból kiderül, hogy a feladat feltételei közül elhagyható lett volna az első, amely szerint az összes kapcsoló domináns halmazként viselkedik, hiszen egy olyan, háromállású kapcsolókból és egy háromszínű körtéből álló rendszerben, amely a második feltételt kielégíti, az egyes kapcsolók állása megjelölhető a három színnel úgy, hogy az első feltétel is teljesüljön.