Feladat:	2016. évi Nemzetközi Matematika Diákolimpia 21. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Baran Zsuzsanna
Füzet:	2016/november, 450 - 452. oldal		PDF  |  MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia, Számhalmazok, Maradékos osztás, kongruenciák, Ellenpélda, mint megoldási módszer a matematikában
Hivatkozás(ok):	Feladatok: 2016/szeptember: 2016. évi Nemzetközi Matematika Diákolimpia 21. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Baran Zsuzsanna megoldása. Be fogjuk látni, hogy a legkisebb ilyen $b$ pozitív egész a $b=6$. A feladat az, hogy minél kevesebb szomszédos pozitív egész számot kell találnunk úgy, hogy azok közül mindegyik $P$-jének legyen közös prímosztója valamelyik másik elem $P$-jével. Ehhez megvizsgáljuk, hogy közeli számok $P$-jeinek milyen közös prímosztója lehet, azaz hogy adott kicsi pozitív egész $x$-ekre milyen $p$ prímre lehet $p\mid P\left(n\right)$ és $p\mid P\left(n+x\right)$ ($n$ pozitív egész). Az $x=1$, 2, 3 és 4-et fogjuk megvizsgálni. Először is, mivel $n^2+n=n\left(n+1\right)$ páros, ezért $P\left(n\right)$ mindig páratlan, így $p$ nem lehet 2. $x=1$-re: ${\displaystyle \begin{array}{cc}\hfill {\displaystyle \left(n^2+n+1;{\left(n+1\right)}^2+\left(n+1\right)+1\right)}& {\displaystyle =\left(n^2+n+1;2n+2\right)=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =\left(n^2+n+1;n+1\right)=\left(n^2;n+1\right)=1.}\hfill \end{array}}$ Azaz $P\left(n\right)$-nek és $P\left(n+1\right)$-nek nem lehet közös prímosztója. $x=2$-re: ${\displaystyle \begin{array}{cc}\hfill {\displaystyle 0}& {\displaystyle \equiv n^2+n+1\equiv {\left(n+2\right)}^2+\left(n+2\right)+1=n^2+5n+7\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}p\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle 0}& {\displaystyle \equiv 4n+6\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}p\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle 2n}& {\displaystyle \equiv -3\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}p\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle 0}& {\displaystyle \equiv 4n^2+4n+4\equiv {\left(-3\right)}^2+2\left(-3\right)+4=7\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}p\right)\mathrm{.}}\hfill \end{array}}$ Így csak akkor lehetséges $p\mid P\left(n\right)$ és $p\mid P\left(n+2\right)$, ha $p=7$ és $2n\equiv -3\equiv 4\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}7\right)$, így $n\equiv 2\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}7\right)$. Ilyenkor tényleg fennáll az oszthatóság: $2^2+2+1\equiv 4^2+4+1\equiv 0\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}7\right)$. $x=3$-ra: ${\displaystyle \begin{array}{cc}\hfill {\displaystyle 0}& {\displaystyle \equiv n^2+n+1\equiv {\left(n+3\right)}^2+\left(n+3\right)+1=n^2+7n+13\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}p\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle 0}& {\displaystyle \equiv 6n+12\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}p\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle 3n}& {\displaystyle \equiv -6\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}p\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle 0}& {\displaystyle \equiv 9n^2+9n+9\equiv {\left(-6\right)}^2+3\cdot \left(-6\right)+9=27\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}p\right)\mathrm{.}}\hfill \end{array}}$ Így csak a $p=3$ jöhet szóba. Ekkor $1^2+1+1\equiv 0\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}3\right)$, de $0^3+0+1\equiv 2^2+2+1\not\equiv 0\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}3\right)$, így az $n\equiv 1\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}3\right)$ jó, de más nem. Tehát $P\left(n\right)$ és $P\left(n+3\right)$ közös prímosztója csak a 3 lehet, mégpedig ha $n\equiv 1\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}3\right)$. $x=4$-re: ${\displaystyle \begin{array}{cc}\hfill {\displaystyle 0}& {\displaystyle \equiv n^2+n+1\equiv {\left(n+4\right)}^2+\left(n+4\right)+1=n^2+9n+21\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}p\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle 0}& {\displaystyle \equiv 8n+20\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}p\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle 2n}& {\displaystyle \equiv -5\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}p\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle 0}& {\displaystyle \equiv 4n^2+4n+4\equiv {\left(-5\right)}^2+2\cdot \left(-5\right)+4=19\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}p\right)\mathrm{.}}\hfill \end{array}}$ Így csak a $p=19$, $2n\equiv -5\equiv 14\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}19\right)$, azaz $n\equiv 7\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}19\right)$ jöhet szóba. Ez megfelelő is: $7^2+7+1\equiv 9^2+9+1\equiv 0\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}19\right)$. Tehát $P\left(n\right)$ és $P\left(n+4\right)$ közös prímosztója csak a 19 lehet, mégpedig ha $n\equiv 7\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}19\right)$. Most az eddigiek alapján próbáljunk létrehozni egy megfelelő 6 elemű halmazt. Szeretnénk egy olyan $a$-t találni, hogy $P\left(a+1\right)$-nek és $P\left(a+5\right)$-nek, $P\left(a+2\right)$-nek és $P\left(a+4\right)$-nek, illetve $P\left(a+3\right)$-nak és $P\left(a+6\right)$-nak legyen közös prímosztója. Legyen $b=6$ és $a\equiv 1\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}3\right)$, $a\equiv 6\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}19\right)$ és $a\equiv 0\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}7\right)$ (ennek a kínai maradéktétel szerint van pozitív egész megoldása). Ekkor $a+1\equiv 7\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}19\right)$, így $19\mid P\left(a+1\right)\mathrm{,}P\left(a+1+4\right)$, míg $a+2\equiv 2\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}7\right)$, így $7\mid P\left(a+2\right)\mathrm{,}P\left(a+2+2\right)$, végül $a+3\equiv a+6\equiv 1\left(\text{<span style="font-weight: normal;font-style: normal;">mod</span>}3\right)$, így $3\mid P\left(a+3\right)\mathrm{,}P\left(a+6\right)$. Így a fenti $a$ mellett a $\left\{P\left(a+1\right)\mathrm{,}P\left(a+2\right)\mathrm{,}\text{...}\mathrm{,}P\left(a+6\right)\right\}$ halmaz mindegyik eleméhez található egy másik elem, amivel van közös prímosztója, azaz a halmaz illatos. Tegyük fel, hogy van kisebb megfelelő $b$ is, azaz létezik $b\le 5$ pozitív egész, amihez létezik $a$ pozitív egész, hogy $\left\{P\left(a+1\right)\mathrm{,}\text{...}\mathrm{,}P\left(a+b\right)\right\}$ illatos. Nem lehet $b=2$ vagy $b=3$, mert $P\left(a+2\right)$ relatív prím $P\left(a+1\right)$-hez és $P\left(a+3\right)$-hoz is. Nem lehet $b=4$, mert akkor $P\left(a+2\right)$ relatív prím $P\left(a+1\right)$-hez és $P\left(a+3\right)$-hoz, így $P\left(a+4\right)$-gyel kell közös prímosztója legyen, ami csak a 7 lehet ($P\left(n\right)$ és $P\left(n+2\right)$ közös prímosztója csak a 7 lehet). Hasonlóan $P\left(a+3\right)$-nak $P\left(a+1\right)$-gyel kell közös prímosztója legyen, de ez is csak a 7 lehet. Ez viszont azt jelentené, hogy $P\left(a+1\right)$ és $P\left(a+2\right)$ egyaránt oszthatóak 7-tel, ami ellentmondás. Nem lehet $b=5$ sem, mert akkor $P\left(a+3\right)$ relatív prím a szomszédjaihoz, így $P\left(a+1\right)$-gyel vagy $P\left(a+5\right)$-tel kell közös prímosztója legyen, ez a prímosztó pedig csak a 7 lehet. Ha $7\mid P\left(a+3\right)$, akkor $7\nmid P\left(a+2\right)\mathrm{,}P\left(a+4\right)$. Eközben $P\left(a+2\right)$ relatív prím a szomszédjaihoz és mivel nem osztható 7-tel, ezért relatív prím $P\left(a+4\right)$-hez is. Ekkor $P\left(a+5\right)$-tel kell közös prímosztója legyen, ami viszont csak a 3 lehet ($P\left(n\right)$ és $P\left(n+3\right)$ közös prímosztója csak a 3 lehet). Hasonlóan $P\left(a+4\right)$-nek $P\left(a+1\right)$-gyel kell közös prímosztója legyen, ami viszont szintén csak a 7 lehet. Ekkor azonban $7\mid P\left(a+1\right)$ és $7\mid P\left(a+2\right)$, ami ellentmondás. Tehát mégsem lehet $b\le 5$, a legkisebb megfelelő $b$ szám a $b=6$.