Az A. 913. feladat (2025. szeptember)

A. 913. Legyen $\displaystyle n$ egy pozitív egész szám. Marci a füzetébe leírja az első $\displaystyle n$ pozitív egész számot valamilyen sorrendben úgy, hogy azt mi nem látjuk. Legyen ez $\displaystyle m(1),m(2),\ldots,m(n)$, ezt a sorrendet szeretnénk kitalálni. Egy lépésben mi is felsorolhatjuk az első $\displaystyle n$ pozitív egész számot Marcinak valamilyen sorrendben, legyen ez $\displaystyle a(1),\ldots,a(n)$. Ekkor Marci a füzetébe (amit mi nem látunk) rajzol egy $\displaystyle n$ csúcsú üres gráfot, melynek csúcsait megcímkézi rendre az $\displaystyle 1,2,\ldots, n$ számokkal. Ezután minden $\displaystyle 1\leq i\leq n$ egészre az $\displaystyle i$-vel címkézett csúcsból húz egy irányított élet az $\displaystyle m(a(i))$ címkéjű csúcsba. Végül a kapott $\displaystyle n$ élű gráf felbomlik diszjunkt irányított körök uniójára (amelyek akár állhatnak egyetlen hurokélből is), és Marci elárulja nekünk ezen körök számát.

a) Mutassuk meg, hogy mindig ki tudjuk találni a gondolt permutációt legfeljebb $\displaystyle n\log_2 (n)$ ilyen lépésből.

b) Létezik-e olyan $\displaystyle c<1$ konstans, amelyre minden $\displaystyle n$ esetén elég $\displaystyle cn\log_2 (n)$ ilyen lépés?

Javasolta: Németh Márton, Budapest

(7 pont)

A beküldési határidő 2025. október 10-én LEJÁRT.

A könnyebb jelölés érdekében a feladatot a következőképpen fogalmazzuk át: adott egy titkos $\displaystyle \sigma\in S_n$ permutáció. Egy lépésben rákérdezhetünk egy $\displaystyle \pi\in S_n$ permutációra, ekkor elárulják nekünk $\displaystyle \sigma\circ\pi$ ciklusainak számát.

A megoldás során megpróbálunk egy olyan $\displaystyle \pi$ permutációt találni, melyre $\displaystyle \sigma\circ\pi = \mathrm{id}$, vagyis a ciklusok száma $\displaystyle n$. Ekkor készen vagyunk, hiszen ez azt jelenti, hogy $\displaystyle \sigma = \pi^{-1}$. Ehhez szükségünk lesz a következő eszközökre:

1. lemma: Tegyük fel, hogy $\displaystyle x_1$, $\displaystyle x_2$, $\displaystyle \ldots$, $\displaystyle x_k$ páronként különböző ciklusokban vannak $\displaystyle \sigma$-ban, és hogy tudjuk $\displaystyle \sigma$ ciklusainak számát. Ekkor egyetlen kérdéssel el tudjuk dönteni, hogy $\displaystyle y\neq x_i$ egy ciklusban van-e valamelyik $\displaystyle x_i$-vel, vagy nem.

Bizonyítás: Legyen $\displaystyle \pi = (y\, x_1\, x_2\, \ldots\, x_k)$. Két eset lehetséges:

Ha $\displaystyle y$ nincs egy ciklusban egyik $\displaystyle x_i$-vel sem, akkor egy $\displaystyle k+1$-edik ciklusban van, tehát

$\displaystyle \sigma = (x_1\, x_{1,2}\, x_{1,3}, \ldots)(x_2\, x_{2,2}\, x_{2,3}\, \ldots)\ldots (y\, y_2\, y_3\, \ldots)\tau, $

ahol $\displaystyle \tau$ a jelölt értékekkel diszjunkt ciklusokat jelöl. Ekkor

$\displaystyle \sigma\circ \pi = (x_{1,2}\, \ldots, x_1\, x_{2,2}\,\ldots\,x_2\,x_{3,2}\,\ldots\, y)\tau $

tehát a ciklusok száma $\displaystyle k$-val csökkent. A másik eset, hogy $\displaystyle y$ benne van az egyik ciklusban a $\displaystyle k$ közül, az általánosság elvesztése nélkül feltesszük, hogy $\displaystyle x_1$-gyel, ekkor

$\displaystyle \sigma = (x_1\, x_{1,2}\, \ldots\, x_{1,l-1}\, y\, x_{1,l+1}\,\ldots)(x_2\, x_{2,2}\, x_{2,3}\, \ldots)\ldots(x_k\, x_{k,2}\, x_{k,3}\, \ldots)\tau. $

Szóval mivel

$\displaystyle \sigma\circ\pi = (x_{1,l+1}\, \ldots\, x_1\, x_{2,2}\,\ldots x_k)(y\, x_{1,2}\, x_{1,3}\, \ldots\, x_{1,l-1})\tau, $

$\displaystyle \tau$-n kívül $\displaystyle k$ ciklusból $\displaystyle 2$ lett. A két eset egymástól mindig megkülönböztethető.

2. lemma: Tegyük fel, hogy $\displaystyle x_1$, $\displaystyle x_2$, $\displaystyle \ldots$, $\displaystyle x_k$ páronként különböző ciklusokban vannak $\displaystyle \sigma$-ban, és hogy tudjuk $\displaystyle \sigma$ ciklusainak számát. Ekkor el tudjuk dönteni, hogy $\displaystyle y\neq x_i$ a $\displaystyle k$ ciklus közül melyikben van, vagy ki tudjuk mutatni, hogy egyikben sem, legfeljebb $\displaystyle \lceil \log_2(k+1)\rceil$ kérdéssel.

Bizonyítás: Ez egy egyszerű bináris keresés az 1. lemma használatával: összesen $\displaystyle k+1$ kimenetel közül kell döntenünk, és minden kérdéssel meg tudjuk felezni a lehetőségek számát.

Következzen a teljes algoritmus: először kérdezzünk rá a $\displaystyle \pi = \mathrm{id}$-re, hogy megtudjuk $\displaystyle \sigma$ ciklusainak számát. Az algoritmus összesen $\displaystyle n$ lépésből fog állni. Az $\displaystyle i$-edik lépés végére szeretnénk rendelkezni egy $\displaystyle \pi_i$ permutációval, melyre teljesül, hogy $\displaystyle \sigma\circ \pi_i$-ben az $\displaystyle 1$, $\displaystyle 2$, $\displaystyle \ldots$, $\displaystyle i$ értékek páronként különböző ciklusokban vannak, illetve tudjuk, $\displaystyle \sigma\circ\pi_i$ ciklusainak számát. Az első ($\displaystyle i=1$) lépés könnyű: a $\displaystyle \pi_1 = \mathrm{id}$ megfelelő.

Tegyük fel induktívan, hogy az első $\displaystyle i-1$ lépés kész. Ekkor a második lemmában leírtak szerint derítsük ki, hogy $\displaystyle \sigma\circ\pi_{i-1}$-ben $\displaystyle i$ melyik $\displaystyle 1\leq j\leq i-1$ értékkel van egy ciklusban, vagy hogy egyikkel sincs. Ha egyikkel sincs, akkor $\displaystyle \pi_i=\pi_{i-1}$ megfelelő.

Ha viszont a $\displaystyle j$ van $\displaystyle i$-vel egy ciklusban, akkor legyen $\displaystyle \pi_i = \pi_{i-1}(i\, j)$. Ez az 1. lemma bizonyításában látottak szerint két részre szakítja a közös ciklust. Mivel tudtuk, hogy $\displaystyle \sigma\circ \pi_{i-1}$-ben hány ciklus van, tudjuk, hogy $\displaystyle \sigma\circ\pi_i$-ben $\displaystyle 1$-gyel több (erre nem vesztegetünk kérdést).

Az $\displaystyle n$-edik lépés után kaptunk egy olyan $\displaystyle \pi = \pi_n$-t, mely megfelel a kezdeti célnak ($\displaystyle \sigma\circ \pi_n$-ben $\displaystyle n$ ciklus van), így készen vagyunk. Most vizsgáljuk meg, hány kérdést használtunk.

A $\displaystyle i$-edik lépésben legfeljebb $\displaystyle \lceil \log_2(i)\rceil$-t, illetve az elején rákérdeztünk a $\displaystyle \pi=\mathrm{id}$-re, ez összesen

$$\begin{align*} 1+\sum_{i=1}^{n} \lceil \log_2(i)\rceil &\leq 1+\int_1^{n} \log_2(x)\mathrm{d}x +\log_2(n)+1\\ &= 2 + \frac{1}{\log(2)} \int_1^{n} \log(x)\mathrm{d}x + \log_2(n)\\ &= 2 + \frac{\left [ x\log x - x \right ]_1^{n}}{\log(2)} + \log_2(n)\\ &= 2 + \frac{n\log(n) - n + 1}{\log(2)} + \log_2(n) \\ &= n\log_2(n) - 1 + \left [3 + \frac{1}{\log(2)} + \log_2(n) - \frac{n}{\log(2)} \right ]. \end{align*}$$

Könnyű ellenőrizni, hogy a zárójeles kifejezés értéke negatív $\displaystyle n\geq 5$ esetén. $\displaystyle n=2$-re $\displaystyle 1$ kérdés elég, $\displaystyle n=3$ esetén a harmadik lépésben elég $\displaystyle 1$ kérdés, így összesen $\displaystyle 3$ kérdés elég, $\displaystyle n=5$ esetén a jobboldal értéke $\displaystyle 1+0+1+2+2=6$, tehát mindig elég $\displaystyle n\log_2(n) - 1$ kérdés.

A b) rész megoldásához egy új trükkre van szükség, mellyel egyszerre két új értéket tudunk beskatulyázni.

Tegyük fel, hogy tudjuk, hogy $\displaystyle \sigma \circ \pi_{i-2}$-ben (ahol $\displaystyle i\geq 3$) az $\displaystyle 1$, $\displaystyle 2$, $\displaystyle \ldots$, $\displaystyle i-2$ értékek különböző ciklusokban vannak, és tudjuk $\displaystyle \sigma\circ \pi_{i-2}$ ciklusainak számát. Konstruálunk egy $\displaystyle \pi_i$ permutációt, melyre $\displaystyle \sigma\circ\pi_i$-ben az $\displaystyle 1$, $\displaystyle 2$, $\displaystyle \ldots$, $\displaystyle i$ értékek különböző ciklusokban vannak.

Először rákérdezünk $\displaystyle \sigma\circ\pi_{i-2}\circ (i-1\, i)$ ciklusainak számára, ebből kiderül, $\displaystyle i$ és $\displaystyle i-1$ azonos ciklusban vannak-e. Ha igen, akkor innen könnyű dolgunk van: a 2. lemmában látott kereséssel megkeressük, hogy $\displaystyle i-1$ melyik $\displaystyle j<i-1$ értékkel van egy ciklusban (vagy egyikkel sem), és a megfelelő transzpozícióval leválasztjuk. Az új permutációban $\displaystyle i$ csak $\displaystyle i-1$-gyel vagy $\displaystyle j$-vel (ha az létezik) lehet egy ciklusban, ezt további $\displaystyle 1$ kérdéssel könnyű kideríteni. Ekkor összesen

$\displaystyle \left \lceil \log_2(i-1) \right \rceil + 2 $

kérdést használtunk, és előállt a $\displaystyle \pi_i$ permutáció $\displaystyle \pi_{i-2}$ és $\displaystyle 0$, $\displaystyle 1$ vagy $\displaystyle 2$ transzpozíció szorzataként.

Most ellenőrizzük, hogy $\displaystyle i-1$ és $\displaystyle i$ biztosan egy ciklusban van-e valamely kisebb $\displaystyle j_{i-1} < i-1$ és $\displaystyle j_i < i-1$ értékekkel (már tudjuk, hogy $\displaystyle j_{i-1} \neq j_i$). Ehhez elég két kérdés (külön összefűzzük $\displaystyle i-1$-et a korábbi értékekkel, és $\displaystyle i$-t). Amennyiben valamely (vagy mindkét) esetben nemleges választ kapunk, újfent elég

$\displaystyle \left \lceil \log_2(i-1) \right \rceil + 3 $

kérdés.

Az egyszerű esetekkel kész vagyunk (ezek csak azért kellettek, hogy könnyebb legyen a bizonyítás, igazából elhagyhatóak). A továbbiakban az algoritmus két fázisból fog állni:

Az $\displaystyle A$ fázis: még nem rendelkezünk két diszjunkt $\displaystyle Y, Z\subset \{1, 2, \ldots, i-2\}$ halmazzal, melyre tudjuk, hogy $\displaystyle j_{i-1}\in Y$ és $\displaystyle j_i\in Z$. Viszont rendelkezünk egy $\displaystyle X\subset \{1, 2, \ldots, i-2\}$ halmazzal, melyre $\displaystyle j_{i-1}, j_i\in X$. Ez a fázis elején teljesül $\displaystyle X = \{1, 2, \ldots i-2\}$-re.

Először két kérdéssel keressünk egy $\displaystyle X'\subset X$ halmazt, melyre

$\displaystyle \left \lceil \frac{|X|}{4} \right\rceil \geq |X'| \geq \left \lfloor \frac{|X|}{4} \right\rfloor $

és $\displaystyle j_{i-1}\in X'$. Most egy kérdéssel derítsük ki, hogy $\displaystyle j_i$ benne van-e $\displaystyle X'$-ben. Ha igen, akkor $\displaystyle 3$ kérdéssel nagyjából lenegyedeltük $\displaystyle X$ méretét, mivel most tudjuk folytatni az $\displaystyle A$ fázist $\displaystyle X'$-vel.

Ha $\displaystyle j_i\notin X'$, akkor viszont találtunk megfelelő $\displaystyle Y$, $\displaystyle Z$ halmazokat. Mielőtt a $\displaystyle B$ fázisba lépnénk, ezeket picit megpofozgatjuk: legyen $\displaystyle Y=X'$, és két kérdéssel szűkítsük $\displaystyle j_i$ lehetséges értékeit egy $\displaystyle Z\subset X\setminus X'$ halmazra, melyre $\displaystyle |Z| = |Y|$.

A $\displaystyle B$ fázis: már rendelkezünk a fent leírt $\displaystyle Y$, $\displaystyle Z$ halmazokkal. Célunk, hogy egyszerre $\displaystyle 3$ kérdéssel leharmadoljuk $\displaystyle Y$ és $\displaystyle Z$ méretét. Legyen $\displaystyle Y=Y_1\cup Y_2\cup Y_3$ és $\displaystyle Z=Z_1\cup Z_2\cup Z_3$, ahol a megfelelő halmazok páronként diszjunktak, és méreteik páronként legfeljebb $\displaystyle 1$-gyel térnek el. Legyen $\displaystyle Y_1 = \{y_1, y_2, \ldots, y_k\}$ és $\displaystyle Z_1 = \{z_1, z_2, \ldots, z_l\}$.

Először kérdezzünk rá $\displaystyle \sigma\circ\pi_{i-2}\circ (y_1\, \ldots\, y_k\, i-1)\circ (z_1\, z_2\, \ldots\, z_l\, i)$ ciklusainak számára.

Ha $\displaystyle j_{i-1}\in Y_1$, $\displaystyle j_i\in Z_1$, akkor $\displaystyle -k-l+2+2$-vel változott a körök száma.
Ha $\displaystyle j_{i-1}\in Y_1$, $\displaystyle j_i\notin Z_1$, vagy fordítva, akkor $\displaystyle -k-l-1+2+1$-gyel változott a körök száma.
Ha $\displaystyle j_{i-1}\notin Y_1$, $\displaystyle j_i\in Z_1$, akkor $\displaystyle -k-1-l-1+1+1$-gyel változott a körök száma.

Látható, hogy ezek az esetek jól megkülönböztethetőek. Az első esetben már ez az $\displaystyle 1$ kérdés elég volt a célunkhoz, $\displaystyle Z_1$ és $\displaystyle Y_1$ megfelelő, és folytatjuk a $\displaystyle B$ fázist.

A harmadik esetben $\displaystyle j_{i-1}\in Y_2\cup Y_3$ és $\displaystyle j_{i}\in Z_2\cup Z_3$, vagyis mindkét halmazt meg tudjuk felezni további két kérdéssel.

Ha pedig a második eset áll fenn, akkor egy kérdéssel eldöntjük, hogy $\displaystyle j_{i-1}\in Y_1$ vagy $\displaystyle j_i\in Z_1$, és a másikkal megfelezzük a másik index halmazát.

Világos, hogy valamely $\displaystyle c_1$ konstansra mindig legfeljebb

$\displaystyle 3\log_3(i-2) + c_1 $

kérdést alkalmazunk a $\displaystyle \pi_i$ permutáció előállításához (az $\displaystyle A$ fázisban olcsóbb szűkíteni a halmazokat, mint a $\displaystyle B$ fázisban).

Tehát összesen valamely $\displaystyle c_2$ konstansra mindig elég

$\displaystyle \dfrac{n}{2}\cdot 3\log_3(n) + c_2n = \dfrac{3\log_3(2)}{2}n\log_2(n) + c_2n$

kérdés. Legyen

$\displaystyle \dfrac{3\log_3(2)}{2} < c_3 < 1, $

illetve $\displaystyle K$ egy olyan határszám, melyre $\displaystyle n\geq K$ esetén

$\displaystyle \dfrac{3\log_3(2)}{2}n\log_2(n) + c_2n \leq c_3n\log_2(n). $

Végül mivel az $\displaystyle a)$ rész alapján minden $\displaystyle n$-re elég $\displaystyle n\log_2(n) - 1$ kérdés is, legyen $\displaystyle c_4 < 1$ olyan, hogy minden $\displaystyle n<K$ esetén

$\displaystyle c_4n\log_2(n) \leq n\log_2(n) - 1. $

Ekkor $\displaystyle c = \max (c_3, c_4) < 1$ megfelel a feladat feltételeinek.

Statisztika:

10 dolgozat érkezett.

5 pontot kapott: 1 versenyző.

4 pontot kapott: 3 versenyző.

1 pontot kapott: 2 versenyző.

0 pontot kapott: 3 versenyző.

Nem versenyszerű: 1 dolgozat.

A KöMaL 2025. szeptemberi matematika feladatai

10 dolgozat érkezett.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	3 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	3 versenyző.
Nem versenyszerű:	1 dolgozat.

Már regisztráltál?
Új vendég vagy?