KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem A. 698. (May 2017)

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 pont)

Deadline expired on 12 June 2017.


Sorry, the solution is available only in Hungarian. Google translation

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:

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

Our web pages are supported by:   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