 |
Az A. 863. feladat (2023. november) |
A. 863. Legyen adott egy \(\displaystyle n\ge 2\) egész szám. Legfeljebb mekkora lehet \(\displaystyle N\), ha tudjuk, hogy végtelen sokféleképpen választható ki \(\displaystyle N\) egymást követő egész szám úgy, hogy egyiknek se legyen 1-nél nagyobb \(\displaystyle n\)-edik hatvány osztója?
Javasolta: Pach Péter Pál (Budapest)
(7 pont)
A beküldési határidő 2023. december 11-én LEJÁRT.
Válasz: \(\displaystyle 2^n-1.\) Az egyik irányú becslés világos: \(\displaystyle 2^n\) egymást követő szám között már mindig van egy, ami osztható \(\displaystyle 2^n\)-nel, ami egy \(\displaystyle n\)-edik hatvány.
Közismert, hogy \(\displaystyle n\ge 2\)-re
\(\displaystyle \sum_{k=1}^{\infty} \frac{1}{k^n}\)
véges.
Ebből következik, hogy létezik \(\displaystyle M\), hogy
\(\displaystyle \sum_{k=M}^{\infty} \frac{1}{k^n}<\frac{1}{2^{n+2}}.\)
Legyen \(\displaystyle T=\prod_{k=1}^{M-1} k^n\). Azt állítjuk, hogy végtelen sok \(\displaystyle m\) pozitív egész van, amire az \(\displaystyle \{mT+1, mT+2, \ldots mT+2^n-1\}\) egymást követő \(\displaystyle 2^n-1\) szám közül egyik sem osztható \(\displaystyle n\)-edik hatvánnyal.
Ennek bizonyítására vegyünk egy nagyon nagy \(\displaystyle K\) számot. Tetszőleges \(\displaystyle r\in \{1, 2, \ldots 2^n-1\}\)-re legyen \(\displaystyle X_r\) azon számok száma \(\displaystyle \{T+r, 2T+r, \ldots KT+r\}\) közül, amik oszthatók egy \(\displaystyle n\)-edik hatvánnnyal.
Mivel \(\displaystyle T\) osztható minden \(\displaystyle M\)-nél kisebb szám \(\displaystyle n\)-edik hatványával, és \(\displaystyle r<2^n\), ezért \(\displaystyle sT+r\) csak \(\displaystyle M\)-nél nagyobb-egyenlő számok \(\displaystyle n\)-edik hatványával lehet osztható, és nyilván legfeljebb \(\displaystyle \sqrt[n]{KT}\) méretű szám \(\displaystyle n\)-edik hatávnyával lehetnek oszthatók. Továbbá tetszőleges \(\displaystyle k\)-ra a \(\displaystyle K\) elemű \(\displaystyle \{T+r, 2t+r, \ldots KT+r\}\) számtani sorozatnak legfeljebb \(\displaystyle \lceil \frac{K}{k^n} \rceil\) elem lehet osztható \(\displaystyle k^n\)-nel, mivel feltehetjük, hogy \(\displaystyle k^n\) relatív prím a sorozat differenciájával, \(\displaystyle T\)-vel (különben a sorozat egyik tagja sem lesz osztható \(\displaystyle k^n\)-nel). Ezek szerint
\(\displaystyle X_r\le \sum_{k=M}^{\sqrt[n]{KT}} \lceil \frac{K}{k^n} \rceil\le \sqrt[n]{KT}+\sum_{k=M}^{\infty} \frac{K}{k^n} \le \sqrt[n]{KT}+\frac{K}{2^{n+2}}.\)
\(\displaystyle K\)-t elég nagyra választjuk, hogy \(\displaystyle \sqrt[n]{KT}<\frac{K}{2^{n+2}}\) teljesüljön, így azt kapjuk, hogy \(\displaystyle X_r<\frac{K}{2^{n+1}}\).
Az \(\displaystyle \{mT+1, mT+2, \ldots mT+2^n-1\}\) egymást követő szám-\(\displaystyle 2^n-1\)-esek közül amikre \(\displaystyle m\le K\), \(\displaystyle X_r\) van kizárva amiatt, mert \(\displaystyle mT+r\) osztható egy \(\displaystyle n\)-edik hatvánnyal. Mivel \(\displaystyle X_1+X_2+\ldots +X_{2^{n}-1}<\frac{K}{2}\), ezért összesen csak ennyi van kizárva az \(\displaystyle m\le K\) számok közül.
Tehát minden kellően nagy \(\displaystyle K\)-ra teljesül, hogy \(\displaystyle 1\)-től \(\displaystyle K\)-ig legalább \(\displaystyle \frac{K}{2}\) olyan \(\displaystyle m\) érték van, hogy az \(\displaystyle \{mT+1, mT+2, \ldots mT+2^n-1\}\) számok közül egyik sem osztható \(\displaystyle 1\)-től különböző \(\displaystyle n\)-edik hatvánnyal. Ez bizonyítja, hogy végtelen sok ilyen \(\displaystyle m\) létezik.
Statisztika:
21 dolgozat érkezett. 7 pontot kapott: Bodor Mátyás, Chrobák Gergő, Czanik Pál, Diaconescu Tashi, Fleischman Illés, Foris Dávid, Holló Martin, Nguyen Kim Dorka, Simon László Bence, Szabó 810 Levente, Szakács Ábel, Varga Boldizsár, Wiener Anna, Zömbik Barnabás. 5 pontot kapott: 2 versenyző. 4 pontot kapott: 1 versenyző. 3 pontot kapott: 1 versenyző. 1 pontot kapott: 2 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2023. novemberi matematika feladatai