Az A. 907. feladat (2025. április)

A. 907. Adott \(\displaystyle 2025\) lámpa és néhány kapcsoló. Minden kapcsolóhoz hozzá van rendelve a lámpák egy részhalmaza. Ha használunk egy kapcsolót, akkor az összes lámpa a hozzá tartozó részhalmazban állapotot vált, azaz ami eddig fel volt kapcsolva az lekapcsolódik, ami pedig le volt kapcsolva az felkapcsolódik. Kezdetben minden lámpa le volt kapcsolva. Tudjuk, hogy minden lámpához van olyan kapcsoló, amelyhez a lámpa hozzá van rendelve.

Határozzuk meg azt a legnagyobb \(\displaystyle k\) számot, amelyre akárhogyan is működnek a kapcsolók, mindenképpen fel lehet kapcsolni egyszerre legalább \(\displaystyle k\) darab lámpát.

OKTV feladat alapján

(7 pont)

A beküldési határidő 2025. május 12-én LEJÁRT.

A feladatot 2025 helyett általánosan oldjuk meg. Jelölje \(\displaystyle f(n)\), hogy \(\displaystyle n\) lámpa esetén mi az a legnagyobb \(\displaystyle k\) szám, amelyre teljesül, hogy \(\displaystyle k\) lámpa mindenképpen felkapcsolható. Definiáljuk továbbá a következő rekurzív sorozatot.

Legyen \(\displaystyle a(0)=0\), \(\displaystyle a(1)=1\). Legyen \(\displaystyle n \geq 2\), és jelölje \(\displaystyle k\) azt a pozitív egész számot, melyre \(\displaystyle 2^k-1 \leq n < 2^{k+1}-1\). Ekkor legyen \(\displaystyle a(n)=2^{k-1}+a(n-(2^k-1))\). Máshogy mondva, ha \(\displaystyle n=(2^k-1)+i\), ahol \(\displaystyle 0 \leq i \leq 2^k-1\), akkor \(\displaystyle a(n)=2^{k-1}+a(i)\). Világos, hogy ez a rekurzív definíció tényleg egyértelműen definiálja az \(\displaystyle a(n)\) sorozatot. Még egy átfogalmazását megemlítjük a definíciónak, amire később szükségünk lesz. Úgy kapjuk \(\displaystyle a(n)\)-t, hogy az \(\displaystyle n\) számot \(\displaystyle n=\sum_{i=1}^\ell 2^{k_i}-1\) alakba írjuk mohó módon, azaz ha már az első néhány \(\displaystyle k_i\) számot meghatároztuk, akkor a következőt mindig a lehető legnagyobbnak választjuk. Ekkor \(\displaystyle a(n)=\sum_{i=1}^\ell 2^{k_i-1}\).

Azt fogjuk bizonyítani, hogy \(\displaystyle f(n)=a(n)\) minden \(\displaystyle n\) pozitív egész számra teljesül. Ha ezt belátjuk, onnan a konkrét \(\displaystyle n=2025\) esetet is könnyen meghatározhatjuk:

Így \(\displaystyle a(2025)=512+256+126+64+32+16+8=1016\).

Térjünk rá az általános egyenlőség bizonyítására, ezt sok apró állításon keresztül csináljuk. Kezdjük egy egyszerű észrevétellel. Ha adott néhány lámpa, és hozzá kapcsolók a feladat feltétele szerint, akkor a kapcsolók használatának sorrendje nem számít, és ha egy kapcsolót kétszer használunk, annak nincs hatása. Ez azt jelenti, hogy nincs értelme egy kapcsolót többször megnyomni, és csak az számít, hogy a kapcsolók melyik részhalmazát használjuk.

1. Állítás: \(\displaystyle a(n) \geq \frac{n+1}{2}\) ha \(\displaystyle n \geq 1\).

Bizonyítás: Indukcióval bizonyítunk. Az \(\displaystyle n=1\) esetben igaz az állítás. Legyen \(\displaystyle n \geq 2\), és tegyük fel, hogy a kisebb értékekre már igazoltuk az állítást. Legyen \(\displaystyle n=2^k-1+i\), ahol \(\displaystyle 0 \leq i \leq 2^k-1\). Ha \(\displaystyle i=0\), akkor \(\displaystyle a(2^k-1)=2^{k-1}\), így teljesül az állítás. Különben indukcióból,

\(\displaystyle a(2^k-1+i)=2^{k-1}+a(i) \geq 2^{k-1}+\frac{i+1}{2} \geq \frac{(2^k-1+i)+1}{2}.\)

2. Állítás: Az \(\displaystyle f\) függvény monoton nő, és \(\displaystyle f(n+1) \leq f(n)+1\) minden \(\displaystyle n\) pozitív egész számra. Továbbá ez a két tulajdonság az \(\displaystyle a\) függvéynre is teljesül.

Bizonyítás: Világos, hogy ha egy \(\displaystyle n\) számra van olyan konstrukció, ahol legfeljebb \(\displaystyle f(n)\) lámpa oltható fel, akkor ha veszünk a lámpák egy \(\displaystyle m\) elemű részhalmazát tetszőleges \(\displaystyle m < n\) esetén, és erre a halmazra megszorítjuk a kapcsolókat, akkor továbbra is egy feltételeknek megfelelő konstrukciót kapunk, ahol legfeljebb \(\displaystyle f(n)\) lámpa kapcsolható fel, így \(\displaystyle f(m) \leq f(n)\). Továbbá ha ehhez az \(\displaystyle n\) lámpás konstrukcióhoz hozzáveszünk még egy lámpát, és ezt hozzákötjük minden kapcsolóhoz, akkor egy olyan konstrukciót kapunk \(\displaystyle n+1\) lámpával, amiben az eredeti \(\displaystyle n\) lámpából legfeljebb \(\displaystyle f(n)\) oltható fel, így összesen legfeljebb \(\displaystyle f(n)+1\), tehát \(\displaystyle f(n+1) \leq f(n)+1\).

Az \(\displaystyle a\) függvényre indukcióval egyszerű bizonyítani az állításokat. \(\displaystyle a(0), a(1), a(2)\) értékekre teljesül, hogy monoton nő, és minden lépésben legfeljebb eggyel nő. Azt kell igazolni, hogy \(\displaystyle a(n) \leq a(n+1) \leq a(n)+1\). Legyen \(\displaystyle n=2^k-1+i\), ahol \(\displaystyle 0 \leq i \leq 2^k-1\), és tegyük fel, hogy az \(\displaystyle m<n\) számok esetén már igazoltuk az állítást. Ha \(\displaystyle i<2^k-1\), akkor definíció szerint \(\displaystyle a(n+1)-a(n)=a(i+1)-a(i)\), így teljesül az állítás indukció miatt. Ha pedig \(\displaystyle i=2^{k}-1\), akkor \(\displaystyle a(n)=a(n+1)=2^k\), így ebben az esetben is igaz az állítás.

3. Állítás: Tetszőleges \(\displaystyle n,m\) pozitív egész számok esetén \(\displaystyle f(n+m) \leq f(n)+f(m)\).

Bizonyítás: Vegyünk \(\displaystyle n\) lámpához olyan kapcsolókat, amikkel legfeljebb \(\displaystyle f(n)\) lámpa kapcsolható fel, és \(\displaystyle m\) az előzőektől különböző lámpához olyan kapcsolókat, amikkel legfeljebb \(\displaystyle f(m)\) lámpa kapcsolható fel. Tekintsünk erre egy nagy konstrukcióként \(\displaystyle n+m\) lámpával. Ekkor legfeljebb \(\displaystyle f(n)+f(m)\) lámpa kapcsolható fel, így \(\displaystyle f(n+m) \leq f(n)+f(m)\) következik az \(\displaystyle f(n+m)\) definíciójából.

Figyeljük meg, hogy ebből indukcióval következik, hogy

\(\displaystyle f\left(\sum_{i=1}^\ell n_i\right) \leq \sum_{i=1}^\ell f(n_i)\)

tetszőleges \(\displaystyle n_1, n_2, \ldots , n_\ell\) pozitív egész számokra.

4. Állítás: \(\displaystyle f(2^k-1)=2^{k-1}\).

Bizonyítás: Valójában az alsó becslésre nem is lesz szükségünk a későbbiekben, de azért mutatunk rá egy egyszerű, tanulságos bizonyítást. Azt az általánosabb állítást látjuk be, amit az 1. Állításban igazoltunk az \(\displaystyle a(n)\) függvényre, azaz hogy \(\displaystyle f(n) \geq \frac{n+1}{2}\) minden \(\displaystyle n\) pozitív egész számra. Vegyünk egy tetszőleges konstrukciót \(\displaystyle n\) lámpával. Egymástól függetlenül, minden kapcsolót kapcsoljunk át \(\displaystyle \frac{1}{2}\) valószínűséggel. Tekintsünk egy tetszőleges \(\displaystyle \ell\) lámpát, és vegyünk hozzá egy \(\displaystyle c\) kapcsolót, amihez hozzá van rendelve. A kapcsolások sorrendje nem számít, tehát úgy is tekinthetünk a sorsolásra, hogy először \(\displaystyle c\)-n kívül az összes kapcsolót (egymástól függetlenül) \(\displaystyle \frac{1}{2}\) valószínűséggel használjuk, és ezek után dobunk fel egy pénzérmét, hogy \(\displaystyle c\)-t kapcsoljuk-e. Akármilyen állapotban is van \(\displaystyle \ell\) a \(\displaystyle c\) kapcsolása előtt, utána mindenképpen \(\displaystyle \frac{1}{2}\) valószínűséggel lesz feloltva. Legyen \(\displaystyle X\) az a valószínűségi változó, hogy végül hány lámpa ég, és minden \(\displaystyle \ell\) lámpa esetén legyen \(\displaystyle I_\ell\) az az indikátor valószínűségi változó, ami 1-et vesz fel, ha \(\displaystyle \ell\) felkapcsolódik, különben 0-t. Láttuk, hogy minden lámpa \(\displaystyle \frac{1}{2}\) vasószínűséggel kapcsolódik fel, így \(\displaystyle \mathbb{E}(I_\ell)=\frac{1}{2}\), ahol \(\displaystyle \mathbb{E}\) a várható értéket jelöli. Vegyük észre, hogy \(\displaystyle X=\sum I_\ell\), ahol az összegzés az összes lámpára történik. A várható érték additív, így

\(\displaystyle \mathbb{E}(X)=\sum \mathbb{E}(I_\ell)=\frac{n}{2}.\)

Továbbá pozitív valószínűséggel egyik kapcsolót sem kapcsoljuk, ekkor egy lámpa sem kapcsolódik fel. Emiatt kell lennie olyan esetnek, amikor több, mint \(\displaystyle \mathbb{E}(X)\) lámpa ég, azaz van olyan kapcsolás, hogy legalább \(\displaystyle \frac{n+1}{2}\) lámpa ég, és éppen ezt akartuk megmutatni.

A felső becsléshez mutatunk egy konstrukciót \(\displaystyle 2^k-1\) lámpával, ahol nem oltható fel \(\displaystyle 2^{k-1}\) lámpánál több. Rendeljünk hozzá minden lámpához egy különböző \(\displaystyle k\) hosszú \(\displaystyle 0-1\) sorozatot úgy, hogy a csupa 0-t egyik lámpához se rendeljük. Tehát a csupa 0-n kívül minden \(\displaystyle k\) hosszú \(\displaystyle 0-1\) sorozatot pontosan 1 lámpához rendeljük hozzá. Legyen \(\displaystyle k\) kapcsoló, ahol minden \(\displaystyle 1 \leq i \leq k\) esetén az \(\displaystyle i.\) (nevezzük \(\displaystyle c_i\)-nek) kapcsoló éppen azokat a lámpákat kapcsolja, amelyekhez rendelt sorozatban az \(\displaystyle i.\) jegy 1. Mivel minden lámpához rendelt sorozatban van 1-es, így minden lámpához van kapcsoló, ami hozzá van rendelve, tehát ez tényleg egy feltételeknek eleget tevő konstrukció. Tegyük fel, hogy \(\displaystyle m \geq 1\) kapcsolót használunk, a konstrukció szimmetriája miatt feltehetjük, hogy éppen a \(\displaystyle c_1, c_2, \ldots, c_m\) kapcsolókat. Ekkor éppen azok a lámpák fognak égni, melyekre a hozzájuk rendelt kódban az első \(\displaystyle m\) helyen páratlan sok 1-es jegy szerepel. Ismert, hogy éppen \(\displaystyle 2^{k-1}\) ilyen sorozat van, mert az utolsó \(\displaystyle k-1\) jegy tetszőleges megválasztása után az első jegyet pontosan egyféleképpen tudjuk megfelelően megválasztani, hogy páratlan sok 1-es legyen az első \(\displaystyle m\) jegy közül. Továbbá a csupa 0 kód ezt nem teljesíti, így tényleg pontosan \(\displaystyle 2^{k-1}\) olyan lámpa van, ami égni fog. Ezzel azt bizonyítottuk, hogy akárhogyan is használunk kapcsolókat (legalább 1-et), mindig pontosan \(\displaystyle 2^{k-1}\) lámpa fog égni. Tehát \(\displaystyle f(2^k-1) \leq 2^{k-1}\), ahogy akartuk.

5. Állítás: Minden \(\displaystyle n\) pozitív egész számra teljesül, hogy \(\displaystyle f(n) \leq a(n)\).

Bizonyítás: Az előző két állítás, valamint az \(\displaystyle a(n)\) alternatív definíciója alapján már nem nehéz olyan konstrukciót adni \(\displaystyle n\) lámpával, ahol legfeljebb \(\displaystyle a(n)\) lámpát lehet felkapcsolni. Legyen \(\displaystyle n=\sum_{i=1}^\ell 2^{k_i}-1\) mohó módon. Ekkor láttuk, hogy \(\displaystyle a(n)=\sum_{i=1}^\ell 2^{k_i-1}\), valamint az előző két állítás szerint

\(\displaystyle f(n) \leq \sum_{i=1}^\ell f(2^{k_i}-1)=\sum_{i=1}^\ell 2^{k_i-1}=a(n),\)

ahogy akartuk.

Mostantól arra hajtunk, hogy megmutassuk, hogy \(\displaystyle f(n) \geq a(n)\) is teljesül. A fő észrevétel a következő.

6. Állítás: Minden \(\displaystyle n\) pozitív egész számra teljesül, hogy \(\displaystyle 2f(n-f(n)) \leq f(n)\).

Bizonyítás: Vegyünk egy olyan konstrukciót \(\displaystyle n\) lámpával, ahol legfeljebb \(\displaystyle f(n)\) lámpa kapcsolható fel. Legyen a lámpák halmaza \(\displaystyle L\). Tekintsük a kapcsolók egy olyan \(\displaystyle C_1\) részhalmazát, amik együttes használata a lámpák egy \(\displaystyle S\) részhalmazát kapcsolja fel, ahol \(\displaystyle |S|=f(n)\). Most feledkezzünk meg ezekről a lámpákról, és figyeljük csak a maradék \(\displaystyle L \setminus S\) lámpákat, ezekre megszorítva a kapcsolókat továbbra is egy feltételeknek megfelelő konstrukciót kapunk \(\displaystyle n-f(n)\) lámpával. Emiatt van a kapcsolóknak egy olyan \(\displaystyle C_2\) részhalmaza, ami az \(\displaystyle L \setminus S\) halmazból legalább \(\displaystyle f(n-f(n))\) lámpát felkapcsol. Ha a \(\displaystyle C_1\) majd a \(\displaystyle C_2\) kapcsolóit használjuk, akkor \(\displaystyle L \setminus S\)-ből legalább \(\displaystyle f(n-f(n))\) lámpa égni fog, és tudjuk, hogy összesen legfeljebb \(\displaystyle f(n)\) lámpát tudunk felkapcsolni, tehát \(\displaystyle S\)-ből legfeljebb \(\displaystyle f(n)-f(n-f(n))\) lámpa éghet. Ez azt jelenti, hogy a \(\displaystyle C_2\) kapcsolók használatakor legalább \(\displaystyle f(n-f(n))\) lámpa lekapcsolódott \(\displaystyle S\)-ből. Tehát ha a csupa lekapcsolt állapotra alkalmazzuk \(\displaystyle C_2\)-t, akkor legalább \(\displaystyle 2f(n-f(n))\) lámpát felkapcsol. Ám tudjuk, hogy legfeljebb \(\displaystyle f(n)\) lámpát lehet felkapcsolni, ami bizonyítja az állítást.

Térjünk rá a feladat bizonyítására. Indirekten tegyük fel, hogy létezik olyan \(\displaystyle n\), amelyre \(\displaystyle f(n) \neq a(n)\), és vegyük a legkisebb ilyen \(\displaystyle n\) számot. Világos, hogy \(\displaystyle n>2\). A 2. és 5. Állítás szerint ekkor \(\displaystyle f(n)=a(n)-1\). A 6. Állítással szeretnénk ellentmondásra jutni. Ez azt mondja ebben az esetben, használva, hogy \(\displaystyle m<n\) esetén \(\displaystyle f(m)=f(n)\), hogy

\(\displaystyle 2a(n-(a(n)-1))=2a(n-f(n))=2f(n-f(n)) \leq f(n)=a(n)-1.\)

Tehát elég a következő állítást bizonyítani, hogy ellentmondásra jussunk.

7. Állítás: Minden \(\displaystyle n\) pozitív egész számra teljesül, hogy \(\displaystyle 2a(n+1-a(n)) > a(n)-1\).

Bizonyítás: Indukcióval bizonyítunk, \(\displaystyle n=1,2\) esetén teljesül az állítás. Tegyük fel, hogy minden \(\displaystyle m<n\) esetén teljesül az állítás, legyen \(\displaystyle n=2^k-1+i\), ahol \(\displaystyle 0 \leq i \leq 2^k-1\).

Először vizsgáljuk meg azt az esetet, amikor \(\displaystyle i=2^k-1\). Ekkor \(\displaystyle a(n)=2^k\), így

\(\displaystyle 2a(n+1-a(n)) = 2a(2^{k+1}-1-2^k) = 2 \cdot 2^{k-1} > 2^k-1 = a(n)-1,\)

így ekkor teljesül az állítás.

Mostantól feltesszük, hogy \(\displaystyle i<2^k-1\). Ekkor

\(\displaystyle a(n+1-a(n))=a((2^k-1+i)+1-(2^{k-1}+a(i)))=a((2^{k-1}-1)+(i+1-a(i))).\)

Az 1. Állítás miatt \(\displaystyle i+1-a(i) \leq \frac{i+1}{2} <2^{k-1}\), így \(\displaystyle i+1-a(i) \leq 2^{k-1}-1\), tehát definíció szerint

\(\displaystyle a((2^{k-1}-1)+(i+1-a(i)))=2^{k-2}+a(i+1-a(i)).\)

Használva az indukciós feltevést,

\(\displaystyle 2a(n+1-a(n))=2^{k-1}+2a(i+1-a(i))>2^{k-1}+a(i)-1=a(n)-1,\)

és pont ezt akartuk. Ezzel befejeztük a feladat bizonyítását.

Statisztika:

Az A. 907. feladat értékelése még nem fejeződött be.

A KöMaL 2025. áprilisi matematika feladatai