![]() |
A C. 1917. feladat (2026. október) |
C. 1917. Egy \(\displaystyle 2026\times2026\)-os táblázat \(\displaystyle k\) darab mezőjét szeretnénk megjelölni egy-egy \(\displaystyle \times\)-szel úgy, hogy semelyik két \(\displaystyle \times\) ne legyen sem egy sorban, sem egy oszlopban. Milyen \(\displaystyle k\) esetén van erre a legtöbb lehetőségünk? (Az egymásba forgatható, tükrözhető eseteket is különbözőnek tekintjük.)
Javasolta: Ujházy Márton (Budapest)
(5 pont)
A beküldési határidő 2026. november 10-én LEJÁRT.
Megoldás. Első lépésként találjunk képletet arra, hogy hányféle lehetőségünk van k darab X elhelyezésére a táblázatban, a \(\displaystyle k\) darab X elhelyezési lehetőségeit jelölje \(\displaystyle L_k\).
Az \(\displaystyle X\)-ek lerakásához először válasszuk ki azt a \(\displaystyle k\) darab sort, ahová a jelek kerülni fognak, erre \(\displaystyle \binom{2026}{k}\) lehetőségünk van. Ezután lefelé haladunk soronként, az első X-et a legfelső kiválasztott sorban 2026 helyre, a következőt 2025 helyre, és így tovább, a \(\displaystyle k\)-adikat az utolsó kiválasztott sorban \(\displaystyle (2026-k+1)\) helyre rakhatjuk. Ebből fakadóan \(\displaystyle k\) darab \(\displaystyle X\) elhelyezésére a lehetőségek száma:
\(\displaystyle L_k=\binom{2026}{k}\cdot 2026\cdot 2025\cdot \ldots \cdot (2026-k+1).\)
Behelyettesítve a \(\displaystyle \binom{2026}{k}=\frac{2026\cdot 2025\cdot \dots \cdot (2026-k+1)}{k!}\) összefüggést, kapjuk, hogy \(\displaystyle L_k= \dfrac{2026^2\cdot 2025^2\cdot \ldots \cdot(2026-k+1)^2}{k!}\).
A továbbiakban azt a \(\displaystyle 0<k\leq 2026\) pozitív egész számot keressük, amelyre \(\displaystyle L_k\) értéke maximális. Ehhez a sorozat egymás melletti tagjait hasonlítjuk össze egymással. Írjuk fel a \(\displaystyle (k+1)\)-edik tagot: \(\displaystyle L_{k+1}=\dfrac{2026^2\cdot 2025^2\cdot \ldots \cdot(2026-k+1)^2\cdot (2026-k)^2}{(k+1)!}\).
Észrevehetjük, hogy az \(\displaystyle L_k\)-ból \(\displaystyle L_{k+1}\)-et úgy kapjuk, hogy \(\displaystyle L_k\)-t beszorozzuk \(\displaystyle \dfrac{(2026-k)^2}{k+1}\)-gyel, másképp fogalmazva, \(\displaystyle \dfrac{L_{k+1}}{L_k}=\dfrac{(2026-k)^2}{k+1}\).Fontos megfigyelés, hogy ha ez a hányados nagyobb 1-nél, akkor a \(\displaystyle (k+1)\)-edik elem nagyobb a \(\displaystyle k\)-adiknál, tehát a sorozat növekszik, ha a hányados kisebb 1-nél, akkor csökken.
Oldjuk meg az \(\displaystyle \dfrac{L_{k+1}}{L_k}=\dfrac{(2026-k)^2}{k+1}>1\) egyenlőtlenséget! Felszorozhatunk a nevezővel, hiszen az pozitív, zárójelfelbontás és rendezés után a következő másodfokú egyenlőtlenséget kapjuk:
\(\displaystyle k^2 - 4053k + 4104675 > 0.\)
A másodfokú kifejezés zérushelyei közelítőleg \(\displaystyle 1981,48\) valamint \(\displaystyle 2071,52\), amiből a \(\displaystyle k>2071,53\) nem része az alaphalmaznak. Tehát az \(\displaystyle \dfrac{L_{k+1}}{L_k}>1\) egyenlőtlenség \(\displaystyle k<1981,48\), esetén teljesül, a fordított irányú egyenlőtlenség alapján pedig az is elmondható, hogy \(\displaystyle 1981,48<k\leq2026\) esetén pedig \(\displaystyle \dfrac{L_{k+1}}{L_k}<1\).
Az eddigiek alapján tehát a sorozat szigorúan monoton növekedő az 1982-edik tagig, attól kezdve pedig szigorúan monoton csökken. Emiatt a legtöbb féle X-elési lehetőség 1982 darab X lerakása esetén lehetséges.
Statisztika:
A C. 1917. feladat értékelése még nem fejeződött be.
A KöMaL 2026. októberi matematika feladatai
