Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

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 June 12, 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.

Problems in Mathematics of KöMaL, May 2017