Az A. 698. feladat (2017. május)

A. 698. Legyenek \(\displaystyle m\) és \(\displaystyle n\) pozitív egészek, és legyen \(\displaystyle H\) az \(\displaystyle \{1,2,\ldots,m\} \times \{1,2,\ldots,n\}\) halmaz egy részhalmaza. Mutassuk meg, hogy ha \(\displaystyle |H|>m+ {(m+n)}\log_2n\), akkor vannak olyan \(\displaystyle 1\le u<v\le m\) és \(\displaystyle 1\le x<y<z\le n\) egészek, amelyekre \(\displaystyle (u,x)\), \(\displaystyle (u,y)\), \(\displaystyle (v,x)\) és \(\displaystyle (v,z)\) is elemei \(\displaystyle H\)-nak.

(5 pont)

A beküldési határidő 2017. június 12-én LEJÁRT.

Megoldás. Jelölje minden \(\displaystyle m,n\ge 1\) esetén \(\displaystyle f(m,n)\) azt a legnagyobb értéket, amit \(\displaystyle |H|\) felvehet, ha \(\displaystyle H\) olyan részhalmaza \(\displaystyle \{1,2,\dots,m\}\times \{1,2,\dots,n\}\)-nek, melyre teljesül az \(\displaystyle (m,n)-(*)\) feltétel, azaz hogy nincs \(\displaystyle 1\le u<v\le m\) és \(\displaystyle 1\le x<y<z\le n\), melyre

\(\displaystyle (u,x),(u,y),(v,x),(v,z)\in H. \)

Ha pedig \(\displaystyle m=0\), akkor \(\displaystyle f(0,n):=0\). Végső célunk belátni, hogy \(\displaystyle f(m,n)\le m+(m+n)\log_2 n\) teljesül minden \(\displaystyle m\ge 0\), \(\displaystyle n\ge 1\) esetén. Ezt egy rekurzív egyenlőtlenségből vezetjük majd le.

Lemma. Legyenek \(\displaystyle \alpha+\beta=n\) adott pozitív egészek. Ekkor léteznek olyan \(\displaystyle p,q\ge 0\) egészek, melyekre \(\displaystyle p+q=m\) és

\(\displaystyle f(m,n)\le f(q,\alpha)+(\alpha+p)+f(p,\beta). \)

Bizonyítás. Válasszunk egy \(\displaystyle (m,n)-(*)\) tulajdonságú \(\displaystyle H\)-t. Jelölje \(\displaystyle i=1,2,\dots,m\) esetén \(\displaystyle S_i\) azon \(\displaystyle \{1,2,\dots,n\}\)-beli \(\displaystyle x\) elemek halmazát, melyekre \(\displaystyle (i,x)\in H\). Ezzel magát a \(\displaystyle H\) halmazt az \(\displaystyle S_1,S_2,\dots,S_m\) halmazokkal kódoltuk. A \(\displaystyle (*)\) feltétel pedig "makroszkópikusabb" ekvivalens alakjában is kimondható: minden \(\displaystyle u<v\) esetén, ha \(\displaystyle (S_u\cap S_v)\) nemüres és minimális eleme \(\displaystyle x\), akkor \(\displaystyle S_u\cap (x;n]\) minden eleme legalább akkora, mint \(\displaystyle S_v\cap (x;n]\) minden eleme.

Most kettévágjuk az \(\displaystyle \{1,\dots,n\}\)-et: az \(\displaystyle A=\{1,2,\dots,\alpha\}\) és a \(\displaystyle B=\{\alpha+1,\dots,\alpha+\beta=n\}\) részekre. Különböztessünk meg kétféle \(\displaystyle S_i\) halmazt: aminek nincsen \(\displaystyle B\)-ben eleme, illetve aminek van \(\displaystyle B\)-ben eleme. Előbbi \(\displaystyle S_i\)-k indexhalmaza \(\displaystyle U\), utóbbiak indexhalmaza \(\displaystyle V\) legyen, és legyen \(\displaystyle q=|U|\), \(\displaystyle p=|V|\). Mivel az \(\displaystyle \{S_i|i\in U\}\) családra a \(\displaystyle (q,\alpha)-(*)\) feltétel érvényes (vagy \(\displaystyle q=0\)-ra üres),

\(\displaystyle \sum_{i\in U}|S_i|\le f(q,\alpha). \)

Ha \(\displaystyle p=0\), kész. Ha \(\displaystyle p>0\), legyen \(\displaystyle V=\{i_1<i_2<\dots<i_p\}\), és \(\displaystyle T_j:=S_{i_j}\). A következő trükköt alkalmazzuk. [Tekintsük \(\displaystyle T_\ell\) halmazt. Legyen \(\displaystyle x\) olyan eleme \(\displaystyle (T_\ell\cap A)\)-nak, amely \(\displaystyle T_{\ell+1},T_{\ell+2},\dots,T_p\) halmazok egyikében is benne van (ha \(\displaystyle \exists x\)), mondjuk \(\displaystyle x\in (T_j\cap A)\), ahol \(\displaystyle \ell<j\). Mivel \(\displaystyle (T_j\cap B)\) nem üres, ezért van \(\displaystyle z\) eleme, s így nincs \(\displaystyle y\in T_\ell\), melyre \(\displaystyle x<y<z\). Mivel \(\displaystyle z>\alpha\), ezért kaptuk, hogy nem lehet \(\displaystyle x\)-nél nagyobb eleme \(\displaystyle (T_\ell\cap A)\)-nak.] Ebből következik, hogy nem lehet \(\displaystyle 1\)-nél több eleme \(\displaystyle (T_\ell\cap A)\)-nak, amely \(\displaystyle T_{\ell+1},\dots,T_p\) egyikében is benne van. Ha pedig van ilyen elem, akkor azt eltávolítva, \(\displaystyle (T_\ell\cap A)\) diszjunkt lesz \(\displaystyle T_{\ell+1},\dots,T_p\) halmazoktól. Tehát rendre eltávolítva \(\displaystyle (T_1\cap A)\), \(\displaystyle (T_2\cap A)\), \(\displaystyle \dots\), \(\displaystyle (T_p\cap A)\) maximum egy-egy elemét, a kapott halmazok páronként diszjunktak lesznek, s így összesen legfeljebb \(\displaystyle |A|\) darab elemük lesz:

\(\displaystyle \sum_{i\in V}|S_i\cap A|=\sum_{j=1}^p |T_j\cap A|\le \alpha+p. \)

Végül a \(\displaystyle (p,\beta)-(*)\) feltétel érvényes az \(\displaystyle (S_i\cap B)\) halmazokra (\(\displaystyle i\in V\)), így

\(\displaystyle \sum_{i\in V}|S_i\cap B|\le f(p,\beta). \)

A három becslést összeadva, a Lemma adódik. \(\displaystyle \blacksquare\)

A befejezés pedig rutinszerű indukció. Jelölje minden \(\displaystyle N\ge 1\)-re \(\displaystyle P(N)\) azt az állítást, hogy \(\displaystyle \forall m\ge 0\) \(\displaystyle f(m,N)\le m+(m+N)\log_2 N\). Ha \(\displaystyle N=1\), akkor ez \(\displaystyle f(m,1)\le m+0\), ami nyilván igaz, mert \(\displaystyle |\{1,\dots,m\}\times \{1\}|=m\). Tegyük fel indirekt, hogy valamely \(\displaystyle N\ge 2\)-re \(\displaystyle P(N)\) nem igaz, és vegyük a legkisebb ilyen \(\displaystyle N\)-et.

Ha \(\displaystyle N\) páros, \(\displaystyle N=2n\) alakú, ahol \(\displaystyle 1\le n<N\) lévén \(\displaystyle P(n)\) igaz. A Lemmát \(\displaystyle \alpha=\beta=n\) esetre alkalmazva, \(\displaystyle P(N)\) igaznak adódik, ugyanis \(\displaystyle \forall m\) \(\displaystyle \exists (p+q=m)\):

\(\displaystyle f(m,N)\le (n+p)+f(p,n)+f(q,n)\)

\(\displaystyle \le (n+m)+[p+(p+n)\log_2 n]+[q+(q+n)\log_2 n] \)

\(\displaystyle =(n+m)+(p+q)(1+\log_2 n)+2n\log_2 n \)

\(\displaystyle =(n+m)+m\log_2 (2n)+2n(\log_2(2n)-1)<m+(m+2n)\log_2(2n).\)

Ha \(\displaystyle N\) páratlan, \(\displaystyle N=2n+1\) alakú, ahol \(\displaystyle P(n)\) és \(\displaystyle P(n+1)\) igaz, mert \(\displaystyle n+1<N\) és \(\displaystyle n\ge 1\). A Lemmát \(\displaystyle \alpha=n+1\), \(\displaystyle \beta=n\) esetre alkalmazva, \(\displaystyle P(N)\) igaznak adódik, ugyanis \(\displaystyle \forall m\) \(\displaystyle \exists (p+q=m)\):

\(\displaystyle f(m,N)\le (n+1+p)+f(p,n)+f(q,n+1) \le (n+1+p)+[p+(p+n)\log_2 n]+[q+(q+n+1)\log_2(n+1)] \)

\(\displaystyle = p[2+\log_2 n]+q[1+\log_2(n+1)]+(n+1)+n\log_2 n+(n+1)\log_2(n+1)\)

\(\displaystyle = p[1+\log_2(2n)]+q[1+\log_2(n+1)]+n\log_2 [n(n+1)]+(1+\log_2(n+1))\)

\(\displaystyle \le (p+q)[1+\log_2(2n+1)]+n\log_2 \left(n+\frac12\right)^2+(1+n) \qquad /\text{mert }2^n\ge 1+\binom n1 \)

\(\displaystyle \le m[1+\log_2(2n+1)]+2n[\log_2(2n+1)-1]+(2n) \)

\(\displaystyle \le m+(m+2n+1)\log_2(2n+1).\)

Mindkét esetben \(\displaystyle P(N)\) mégis igaz, ami ellentmondás, így \(\displaystyle (\forall n\ge 1:P(n))\) is igaz, és készen vagyunk.

Statisztika:

3 dolgozat érkezett.
5 pontot kapott:	Imolay András, Williams Kada.
0 pontot kapott:	1 versenyző.

A KöMaL 2017. májusi matematika feladatai