Az idei EGMO feladatai

1. nap

1. feladat. Egy \(2026\times 2026\)-os négyzetrácsot bordónak nevezünk, ha a \(2026^2\) darab egységcellája közül legalább egy pirosra van színezve. Egy cellákból álló téglalap alakú régiót páratlanosnak hívunk, ha páratlan sok piros cellát tartalmaz. Határozd meg azt a legnagyobb pozitív egész \(M\) számot, amelyre bármely \({2026\times 2026}\)-os bordó négyzetrács esetén létezik egy legalább \(M\) cellából álló páratlanos régió.

Megjegyzés: Egy téglalap alakú régió oldalai párhuzamosak a négyzetrács oldalaival és tartalmazza a belsejét.

2. feladat. Adott egy pozitív egész \(n\). Mária a következő játékot játssza a táblán: kezdetben felírja az \(1\)-et, majd minden lépésben választ egy \(1\le j\le n\) egész számot és a táblán szereplő \(V\) számot lecseréli a \(j \cdot R\left(\frac{V}{j}\right)\) számra, ahol \(R(x)\) az \(x\)-hez legközelebbi egész számot jelöli. Ha az \(x\) éppen félúton van két szomszédos egész szám között, akkor felfelé kerekít. Például \(R(1,3)=1\) és \(R(1,5)=R(1,8)=2\).

1. Bizonyítsd be, hogy minden adott \(n\)-re létezik olyan \(B\) pozitív egész szám, amelynél nagyobb számot Mária sohasem írhat fel a táblára.

2. Egy \(n\) egész számra jelölje \(f(n)\) a legnagyobb számot, amelyet Mária a táblára véges sok lépés után felírhat. Bizonyítsd be, hogy létezik \(N\) pozitív egész, amelyre minden \(n\ge N\) esetén \(f(n)\) osztható \(2026\)-tal.

3. feladat. Jelölje \(\mathbb{R}\) a valós számok halmazát. Határozd meg az összes \(f\colon\mathbb{R}\rightarrow \mathbb{R}\) függvényt, amelyre tetszőleges \(x\), \(y\) valós számokra teljesül, hogy \[f\left(\bigl(f(x)+f(y)\bigr)^2\right)=(x+y)f(x+y).\]

2. nap

4. feladat. Legyen \(1=a_1 \ge a_2 \ge a_3 \ge \dots\) egy valós számokból álló végtelen számsor, amelyre minden \(n\) pozitív egész szám esetén teljesül, hogy \(a_n = a_{2n}+a_{2n+1}\). Legyen \(r=2026^{2026}\). Bizonyítsd be, hogy \[\dfrac1{r} \le a_{r} \le \dfrac{2}{r+1}.\]

5. feladat. Legyen \(ABC\) egy hegyesszögű háromszög, amelyre \(AC>AB\). Jelölje \(ABC\) köréírt körét \(\omega\) és legyen \(\omega\) középpontja \(O\). Az \(\omega\)-hoz \(B\)-ben és \(C\)-ben húzott érintők \(K\)-ban metszik egymást. Legyen az \(ABK\) háromszög köréírt körének és a \(BC\) egyenesnek a második metszéspontja \(Z\). Jelöljük \(KZ\) felezőpontját \(L\)-lel. Legyen a \(KZ\) és \(AB\) egyenesek metszéspontja \(X\). Az \(O\)-ból \(KZ\)-re állított merőleges az \(ABL\) háromszög köréírt körét a \(BC\) egyenes \(A\)-felőli oldalán egyetlen pontban metszi. Legyen ez a pont \(V\). Bizonyítsd be, hogy \(LV\) merőleges \(CX\)-re.

6. feladat. Vegyünk egy \(p\) prímszámot és legyen \(n\) egy pozitív egész szám, amelyre \(p\) nem osztja \(n\)-et. Legyen az \(n\) pozitív osztóinak száma \(k\) és az osztókat jelöljük \(1 = d_1<d_2<\dots<d_k = n\)-nel. Minden \(i = 1, 2, \dots, k\)-ra jelölje \(c_i\) a \(d_i^2\) olyan pozitív \(\ell\) osztóinak számát, amelyekre \(p\) osztja \(d_i-\ell\)-et. Bizonyítsd be, hogy \[(p-1)\left(c_1+c_2+\cdots+c_k\right) \ge k^2.\]

Az 1. feladat megoldása. A \(2026\times2026\)-os négyzetrács sorait számozzuk fentről lefelé, oszlopait pedig (figyelem, a szokásostól eltérően!) jobbról balra 1-től 2026-ig. Az \(i\). sorban és \(j\). oszlopban lévő cellát jelölje \((i;j)\).

Először belátjuk, hogy \(M\leq 1013^2\). Megmutatjuk, hogy ha \(M>1013^2\), akkor van olyan 2026 x 2026-os bordó négyzetrács, amiben nincs legalább M cellás páratlanos régió. Vizsgáljuk azt az elrendezést, amelyben a középső 4 cella piros, a többi fehér (1. ábra). Ha egy téglalap vízszintes oldala hosszabb, mint 1013 egység, akkor vagy \((1013;1013)\)-at és \((1013;1014)\)-et is tartalmazza, vagy egyiket sem. \((1014;1013)\) és \((1014;1014)\) közül is 0-t vagy 2-t tartalmaz, tehát páros sok piros négyzet van benne. Szimmetria miatt ugyanez a helyzet, ha a függőleges oldala hosszabb, mint 1013 egység. Tehát ebben az esetben egy páratlanos téglalap minden oldala legfeljebb 1013 egység hosszú, vagyis legfeljebb \(1013^2\) cellából áll.

Tegyük fel, hogy \(M<1013^2\), azaz létezik olyan elrendezés, amelyben akárhogy választunk egy legalább \(1013^2\) cellából álló téglalapot, páros darab piros cella lesz benne. Teljes indukcióval belátjuk, hogy ekkor nincs piros cella a négyzetrácson. 0 sor és egy sor nulladik cellája között nyilván nincs piros cella. Tegyük fel, hogy már beláttuk, hogy az első \(i\) sorban és az \((i+1)\). sor első \(j\) cellája közt nincs piros cella (\(0\leq i\), \(j\leq 1012\)). A négyzetrács bizonyos pontjaira használjuk a 2. ábrán lévő betűzést. \(LO=2026-(j+1)\geq 1013\) és \(FL=2026-(i + 1)\geq 1013\), ezért \(FGOL\) legalább \(1013^2\) cellából áll, vagyis páros sok piros négyzet van benne. \(ABNL\), \(FKNL\) és \(CDOL\) tartalmazzák \(FGOL\)-t, emiatt az ő területük is elég nagy ahhoz, hogy páros sok piros cella legyen bennük. Ezért \(CDOL\) és \(FGOL\) „különbségében”, \(CDFG\)-ben, és hasonlóan \(GKNO\)-ben is páros számú piros cella van. Az \(ABKHEC\) területen nincs piros négyzet. Tehát \(ABNL\)-ben és \(ABNL\) \((i+1;j+1)\)-en kívüli részében is összesen páros piros cella van, vagyis \((i+1;j+1)\) nem piros.

Ezzel a gondolatmenettel azt kapjuk, hogy az \((i+1)\). sor \(1\), \(2\), \(\ldots\), \(1013\) cellái nem pirosak. Logikai szimmetriával (az ábrát horizontálisan tükrözve) ugyanígy adódik, hogy a \(2026\), \(2025\), \(\ldots\), \(1014\) cellák sem pirosak, vagyis az egész \((i+1)\). sorban nincs piros cella. (Az \(i=0\) vagy \(j=0\) esetben bizonyos pontok egybeeshetnek, de ez lényegében nem befolyásolja a bizonyítást.) Így összességében az \(1\)., \(2\)., \(\ldots\), \(1013\). sorban nincs piros cella. Logikai szimmetriával (az ábrát horizontálisan tükrözve) hasonlóan adódik, hogy a \(2026\)., \(2025\)., \(\ldots\), \(1014\). sorban sincs piros cella, tehát beláttuk, hogy az egész négyzetrácson nincs piros cella. Ez ellentmond a feladat feltételeinek, tehát az \(M<1013^2\) feltevés nem igaz. Ebből a fentebb belátott \(M\leq 1013^2\) feltételt kihasználva az következik, hogy \(M=1013^2\).