A B. 5284. feladat (2022. december)

B. 5284. Legyen \(\displaystyle n>2\). Aladár kiválasztotta a \(\displaystyle 2n\) csúcsú teljes gráf egy élét. Paula egy forintért rákérdezhet, hogy egy általa megadott teljes párosításban benne van-e a kiválasztott él. Legalább hány forint lapul Paula zsebében, ha ügyes kérdésekkel biztosan ki tudja találni, hogy melyik él lett kiválasztva?

Javasolta: Pach Péter Pál (Budapest)

(6 pont)

A beküldési határidő 2023. január 10-én LEJÁRT.

Megoldás. A válasz: \(\displaystyle 2n-2+k\), ahol \(\displaystyle k\) az a pozitív egész, amelyre \(\displaystyle 2^{k-1} < n \leq 2^k\) (másképp mondva: \(\displaystyle k = \lceil \log_2(n) \rceil\), ahol \(\displaystyle \lceil x \rceil\) az \(\displaystyle x\) felső egészrészét jelenti).

(A) Egy jó kérdezési stratégia bemutatása. Először megadunk egy módszert, amellyel Paula ennyi kérdéssel biztosan kitalálja az Aladár által kiválaszott élt.

(A1) A gráf színezése \(\displaystyle 2n-1\) színnel. Ismert, hogy a \(\displaystyle 2n\) csúcsú teljes gráf élei kiszínezhetők \(\displaystyle 2n-1\) színnel úgy, hogy minden színosztály egy-egy teljes párosítást adjon meg. Azaz az élek felbonthatók \(\displaystyle 2n-1\) diszjunkt teljes párosításra. Egy másik ekvivalens megfogalmazás: \(\displaystyle 2n\) csapat számára szervezhető \(\displaystyle (2n-1)\)-fordulós körmérkőzéses focibajnokság. (Az állítás ez utóbbi változatára egy bizonyítás olvasható például Kiss György: Hogyan szervezzünk körmérkőzéses focibajnokságot? című, a 2006. decemberi KöMaL-ban megjelent cikkében). Paula színezze ki így a gráfot.

(A2) A szín meghatározása. Paula sorban kérdezzen egy-egy színre (pontosabban az adott színű élek alkotta párosításra). Legfeljebb \(\displaystyle 2n-2\) ilyen kérdéssel kiderül, milyen színű az Aladár által választott él, hiszen ha már \(\displaystyle 2n-2\) különböző színre vonatkozó kérdés ,,nem'' választ kapott, akkor már csak az egyetlen, eddig kimaradt szín jöhet szóba. (Ha Paula korábban kapott egy ,,igen'' választ, akkor nem is kell már többet kérdeznie.) Nevezzük sárgának az Aladár által választott él színét, a sárga élek halmazát jelölje \(\displaystyle S\).

(A3) Keresés a sárga élek között. Paula már csak az \(\displaystyle n\)-elemű \(\displaystyle S\) élhalmazban kell keresgéljen. Ezen belül bináris keresést fog alkalmazni: egy-egy kérdéssel mindig felezi a szóba jöhető élek halmazát. Azaz mindig egy olyan párosítást kérdez, amely a szóba jöhető élek felét tartalmazza. Így a kapott válasz alapján feleakkorára tudja szűkíteni a lehetséges élek halmazát. Ha éppen páratlan a szóba jöhető élek halmaza, akkor persze Paula nem tud pontosan felezni. Az alábbiakban pontosabban is kifejtjük a módszert.

(A3') A bináris keresés precíz leírása. A bináris keresés során Paula minden \(\displaystyle 1 \leq i \leq k\) esetén rekurzívan határozza meg az \(\displaystyle S_0 = S\) halmaz \(\displaystyle H_i\) és \(\displaystyle S_i\) részhalmazait. Minden \(\displaystyle 1 \leq i \leq k\) esetén \(\displaystyle H_i\) az \(\displaystyle S_{i-1}\) egy tetszőleges \(\displaystyle 2^{k-i}\)-elemű részhalmaza. Paula \(\displaystyle i\)-edik kérdése egy olyan teljes párosítás, amely \(\displaystyle S\)-ből éppen \(\displaystyle H_i\) éleit tartalamazza (hogy miért van ilyen párosítás, arról majd a következő pontban értekezünk). A kérdésre kapott válasz után a szóba jöhető élek az \(\displaystyle S_i \subsetneq S\) élhamazra szűkülnek: ha ,,igen'' volt a válasz, akkor \(\displaystyle S_i=H_i\), ha ,,nem'', akkor \(\displaystyle S_i = S_{i-1} \setminus H_i\). Mindkét esetben teljesül, hogy \(\displaystyle |S_i| \leq |S_{i-1}| / 2 \leq 2^{k-i}\).

A bináris keresés utolsó, \(\displaystyle k\)-adik kérdése után az \(\displaystyle S_k\) halmaz mérete így csak \(\displaystyle 2^0 = 1\) lehet, azaz Paula egyértelműen meghatározta az Aladár által válaszott élt.

(A4) Párosítás készítése a sárga élek adott részhalmazához. Adósak vagyunk annak belátásával, hogy Paula mindig tud az általa választott \(\displaystyle H_i\) halmazra illeszkedő párosítást választani. Ehhez bebizonyítjuk, hogy \(\displaystyle S\) (a sárga élek) tetszőleges olyan \(\displaystyle H\) részhalmazára, amelyre \(\displaystyle |H| \leq n-2\), készíthető olyan teljes párosítás a gráfban, amelyik pontosan \(\displaystyle H\) éleit tartalmazza a sárga élek közül. (A \(\displaystyle |H| \leq n-2\) feltétel nyilvánvalóan szükséges, hiszen \(\displaystyle n-1\) él már a párosítás \(\displaystyle n\). élét is meghatározná.)

Nevezzük el a sárga éleket \(\displaystyle a_ib_i\)-nek úgy, hogy az \(\displaystyle i \in \{ 1,2,\ldots,|H|\}\) indexekhez tartozzanak \(\displaystyle H\) élei, míg az \(\displaystyle i \in \{ |H|+1,|H|+2,\ldots,n\}\) indexekhez \(\displaystyle S \setminus H\) élei. Itt \(\displaystyle a_i\) és \(\displaystyle b_i\) az egyes élek végpontjaiban levő csúcsokat jelentik. Módosítsuk az \(\displaystyle S\) párosítást a következő módon:

• Az \(\displaystyle a_ib_i\) élt cseréljük le \(\displaystyle a_ib_{i+1}\)-re minden \(\displaystyle |H| < i < n\) esetén;
• Az \(\displaystyle a_nb_n\) élt pedig cseréljük le \(\displaystyle a_nb_{|H|+1}\)-re (mivel \(\displaystyle |H| \leq n-2\), vagyis \(\displaystyle |H|+1 < n\), tehát az \(\displaystyle a_nb_n\) él valóban le lesz cserélve másra így).

Így egy olyan teljes párosítást kapunk, amelyben \(\displaystyle H\) élei megmaradtak, \(\displaystyle S\setminus H\) élei viszont kikerültek a párosításból.

(A5) A \(\displaystyle |H| \leq 2\) feltétel ellenőrzése, pontosítás \(\displaystyle n=2^{k-1}+1\) esetén. Ha \(\displaystyle 2^{k-1}+1 < n \leq 2^k\), akkor Paula választásai során a \(\displaystyle |H_i| \leq n-2\) egyenlőtlenség mindig teljesül, hiszen a feladat \(\displaystyle n > 2\) feltétele miatt \(\displaystyle k \geq 2\), így \(\displaystyle |H_i| \leq |H_1| = 2^{k-1} \leq n-2\).

Ha \(\displaystyle n=2^{k-1}+1\), akkor viszont \(\displaystyle |H_1| = n-1\), így a bináris keresés első kérdésében nem tudunk olyan párosítást kérdezni, amely éppen \(\displaystyle H_1\) éleit tartalmazza. Tudunk viszont olyan párosítást kérdezni, amely éppen \(\displaystyle S_0 \setminus H_1\) éleit tartalmazza \(\displaystyle S_0\)-ból (hiszen \(\displaystyle |S_0 \setminus H_1| = 1 \leq n-2\), mivel \(\displaystyle n \geq 2\)). Így a bináris keresés első körében a ,,nem'' válasz esetén lesz \(\displaystyle S_1 = H_1\), míg ,,igen'' válasz esetén \(\displaystyle S_1 = S_0 \setminus H_1\). A második körtől pedig minden haladhat az eredeti terv szerint, mivel \(\displaystyle i\geq 2\) esetén már \(\displaystyle |H_i| \leq |H_2| = 2^{k-2} \leq n-2\).

Ezzel tehát megadtunk egy olyan módszert Paula számára, amely \(\displaystyle 2n-2+\lceil \log_2(n) \rceil\) kérdéssel garantáltan megtalálja az Aladár által kiválasztott élt.

(B) A minimalitás bizonyítása. Be kell még látnunk, hogy olyan stratégia nem létezhet, amelynek alkalmazásával Paula ennél kevesebb kérdéssel is garantáltan megtalálná a kívánt élt.

(B1) A lehetséges élek száma. A kérdezz-felelek játék egy tetszőleges lefolyása során jelölje \(\displaystyle E_i\) az élek azon részhalmazát, amely Aladárnak az \(\displaystyle i\)-edik kérdésre adott válasza után még szóba jöhet. (Ezek azok az élek, amelyek az összes addigi ,,igen'' válasznál a Paula által kérdezett párosításban voltak, míg az összes addigi ,,nem'' válasznál kimaradtak a párosításból.)

Paula mindig kaphat ,,igen'' és ,,nem'' választ is, kivéve, ha az \(\displaystyle i\)-ediknek megkérdezett párosítás része \(\displaystyle E_{i-1}\)-nek, vagy diszjunkt tőle. De ezzel Paula semmi újat nem fog megtudni, az \(\displaystyle E_{i-1}\) halmaz nem változik – tekinthetjük úgy, mintha ezt a kérdést fel se tette volna.

(B2) A lehetőségek száma legfeljebb \(\displaystyle n\)-nel csökken. Egy ,,nem'' válasz lefeljebb \(\displaystyle n\) új élt zárhat ki, így ilyenkor \(\displaystyle |E_{i+1}| \geq |E_i| - n\).

(B3) A lehetőségek legalább fele megmarad. Bármilyen \(\displaystyle i\)-re előfordulhat az is, hogy \(\displaystyle |E_i| \geq |E_{i-1}|/2\). Hiszen ha Paula az \(\displaystyle i\)-edik kérdésével egy \(\displaystyle P_i\) élhamazra kérdez rá, akkor ,,igen'' válasz esetén \(\displaystyle E_i^+ = E_{i-1} \cap P_i\), míg ,,nem'' válasz esetén \(\displaystyle E_i^- = E_{i-1} \setminus P_i\) lesz az új \(\displaystyle E_i\), de mivel \(\displaystyle E_i^+\) és \(\displaystyle E_i^-\) diszjunktak és uniójuk \(\displaystyle E_i\), legalább az egyikük legalább feleakkora, mint \(\displaystyle E_i\).

(B3) A végső leszámlálás. A teljes gráfnak \(\displaystyle \binom{2n}{2} = n(2n-1)\) éle van, így ha az első \(\displaystyle 2n-3\) kérdésre csupa ,,nem'' válasz érkezik, akkor \(\displaystyle |E_{2n-2}| \geq n(2n-1) - (2n-2)n = n\). Előfordulhat az is, hogy minden \(\displaystyle i > 2n-2\) esetén teljesül, hogy \(\displaystyle |E_i| \geq |E_{i-1}|/2\) (ez valójában a kisebb \(\displaystyle i\)-kre is teljesült, ha addig mindig ,,nem'' választ kapott Paula).

Ha \(\displaystyle |E_{2n-2}| \geq n > 2^{k-1}\), akkor így \(\displaystyle |E_{2n-2+k-1}| \geq |E_{2n-2}| / 2^{k-1} > 1\). Tehát a \(\displaystyle (2n-2+k-1)\)-edik kérdés után még több él is szóba jöhet. Így Paulának szüksége lehet a \(\displaystyle (2n-2+k)\)-adik kérdésre, ha nincs szerencséje – akármilyen ügyes stratégia szerint is kérdezgetett.

Statisztika:

43 dolgozat érkezett.
6 pontot kapott:	Aravin Peter, Chrobák Gergő, Csonka Illés, Czanik Pál, Czirják Márton Pál, Fülöp Csilla, Guthy Gábor, Holló Martin, Kovács Benedek Noel, Melján Dávid Gergő, Nguyen Kim Dorka, Simon László Bence, Szakács Ábel, Szanyi Attila, Tarján Bernát, Teveli Jakab, Varga Boldizsár, Wiener Anna, Zömbik Barnabás.
5 pontot kapott:	Diaconescu Tashi, Fazokán Marcell, Markovics Áron.
4 pontot kapott:	10 versenyző.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	4 versenyző.

A KöMaL 2022. decemberi matematika feladatai