Kezdőlap


Feladat:	B.3859	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Blázsik Zoltán , Dányi Zsolt , Farkas Ádám László , Honner Balázs , Károlyi Márton , Kornis Kristóf , Kovács 111 Péter , Kovács 129 Péter , Kunovszki Péter , Kutas Péter , Mészáros Gábor , Nagy János , Szabó Tamás , Szaller Dávid , Szalóki Dávid , Szegvári Gábor , Szentandrási István , Szilágyi Csaba , Szücs Gergely , Tomon István , Tóthmérész Lilla , Udvari Balázs , Varga László , Varga Péter , Véges Márton
Füzet:	2006/szeptember, 345 - 346. oldal		PDF \| MathML
Témakör(ök):	Oszthatóság, Számsorozatok, Feladat
Hivatkozás(ok):	Feladatok: 2005/november: B.3859

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.

Megoldás. Ha létezik ilyen sorrend, akkor szükségképpen $a_{1} = 1$ (különben valamelyik szorzat egyenlő lenne a rákövetkezővel) és $a_{n} = n$ , mert ellenkező esetben egynél több szorzat is osztható lenne $n$ -nel, azaz nulla maradékot adna $n$ -nel osztva. Először megmutatjuk, hogy $n$ nem lehet 4-nél nagyobb összetett szám. Tételezzük fel ugyanis, hogy $4 < n = a b$ , ahol $2 \leq a \leq b < n$ . Ekkor $b > 2$ miatt $2 a = \frac{2 n}{b} < n$ , így $a \neq b$ vagy $2 a \neq b$ folytán $a_{1} a_{2} \dots a_{n - 1}$ is nulla maradékot ad $n$ -nel osztva, hiszen osztható $a b$ -vel.
Az $n$ tehát csak 4 vagy prímszám lehet. Az $n = 4$ -re egy alkalmas sorrend 1, 3, 2, 4. Megmutatjuk, hogy akkor is létezik megfelelő sorrend, ha $n$ értéke prím. Legyen ekkor ‐ ahogy szükséges ‐ $a_{1} = 1$ , $a_{n} = n$ , az $a_{2}, ..., a_{n - 1}$ számokat pedig úgy választjuk $2,3, ..., n - 1$ közül, hogy $a_{i} (i - 1)$ -nek az $n$ -nel való osztási maradéka $i$ legyen. Ez a következőképpen lehetséges: adott $2 \leq i \leq n - 1$ esetén szorozzuk meg az $1,2, ..., n - 1$ számok mindegyikét $(i - 1)$ -gyel; mivel $n$ prím, a kapott szorzatok egyike sem osztható $n$ -nel, és mind különböző maradékot adnak. Ellenkező esetben, ha pl. $a_{k} (i - 1)$ és $a_{t} (i - 1)$ ugyanazt a maradékot adná, akkor a különbségük, $(a_{k} - a_{t}) (i - 1)$ osztható lenne $n$ -nel; ez lehetetlen, mivel sem $i - 1$ , sem $a_{k} - a_{t}$ nem lehet $n$ -nel osztható.
Így viszont az $n - 1$ különböző nemnulla maradék között minden nemnulla maradék megtalálható, ezért $i$ is. Abban is biztosak lehetünk, hogy az eképpen kapott $a_{i}$ szám nem az $a_{1} = 1$ , hiszen akkor $a_{i} (i - 1) = i - 1$ lenne, amelynek a maradéka nem $i$ .
Ezután igazoljuk, hogy a különböző $i$ sorszámokra kapott $a_{i}$ értékek mind különbözőek. Ha ugyanis valamilyen $i \neq j$ -re $a_{i} = a_{j} = c$ ( $\neq a_{1} = 1$ ) adódna, akkor $c (i - 1) = a_{i} (i - 1)$ osztási maradéka $i$ , $c (j - 1) = a_{j} (j - 1)$ osztási maradéka pedig $j$ ; így $c (i - j) = c ((i - 1) - (j - 1)) = c (i - 1) - c (j - 1)$ osztási maradéka $i - j$ lenne, azaz $(c - 1) (i - j) = c (i - j) - (i - j)$ osztható $n$ -nel, ami lehetetlen.
Végül megmutatjuk, hogy az $a_{2}, ..., a_{n - 1}$ számok ebben a sorrendben (előttük $a_{1} = 1$ -gyel, utánuk legvégül pedig $a_{n} = n$ -nel) teljesítik a feladat követelményeit. Az $a_{1}$ maradéka 1, $a_{1} a_{2}$ maradéka $1 \cdot a_{2}$ maradéka, azaz $2$ , $a_{1} a_{2} a_{3}$ maradéka $2 a_{3}$ maradéka, azaz 3 stb.: ha már tudjuk, hogy $a_{1} a_{2} \dots a_{k}$ maradéka $k$ (ahol $k < n - 1$ ), akkor $a_{1} a_{2} \dots a_{k} a_{k + 1}$ maradéka $k a_{k + 1}$ maradéka, azaz $k + 1$ . Végül $a_{1} a_{2} \dots a_{n}$ maradéka nyilván $0$ .