KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

ELTE

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

A. 698. Let \(\displaystyle m\) and \(\displaystyle n\) be positive integers, and let \(\displaystyle H\) denote a subset of the set \(\displaystyle \{1,2,\ldots,m\}\times\{1,2,\ldots,n\}\). Show that if \(\displaystyle |H|>m+(m+n)\log_2n\), then there exist integers \(\displaystyle 1\le u<v\le m\) and \(\displaystyle 1\le x<y<z\le n\) such that the pairs \(\displaystyle (u,x)\), \(\displaystyle (u,y)\), \(\displaystyle (v,x)\) and \(\displaystyle (v,z)\) are elements of \(\displaystyle H\).

(5 points)

Deadline expired on 12 June 2017.


Google Translation (Sorry, the solution is published in Hungarian only.)

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.


Statistics on problem A. 698.
3 students sent a solution.
5 points:Imolay András, Williams Kada.
0 point:1 student.


  • Problems in Mathematics of KöMaL, May 2017

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley