Kezdőlap


Feladat:	2001. évi Nemzetközi Matematika Diákolimpia 21. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Kovács Erika Renáta
Füzet:	2001/október, 392. oldal		PDF \| MathML
Témakör(ök):	Indirekt bizonyítási mód, Permutációk, Maradékosztályok, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 2001/szeptember: 2001. é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.

¹ Legyen az $n!$ permutáció $A_{1}$ , $A_{2}$ , $...$ , $A_{n!}$ . Tegyük fel, hogy az állítás nem igaz, vagyis $n! ∤ S (A_{i}) - S (A_{j})$ , ahol $i \neq j$ . Mivel $n!$ permutáció van, és $n!$ -féle maradék $n!$ -sal osztva, ez csak úgy lehetséges, hogy minden maradék pontosan egyszer fordul elő.
Így egyrészt

\begin{matrix} \sum_{i = 1}^{n!} S (A_{i}) \equiv 1 + ... + n! \equiv (\frac{n! + 1}{2}) n! ≢ 0 (mod n!), \end{matrix}

mivel

\frac{n! + 1}{2}

nem egész, hiszen

n! + 1

páratlan.
Másfelől az 1, 2,

...

n

számok mindegyike

(n - 1)!

permutációban szerepel adott

k_{i}

szorzóval, vagyis

\begin{matrix} \begin{matrix} \sum_{i = 1}^{n!} S (A_{i}) = (n - 1)! \cdot \sum_{i = 1}^{n} k_{i} (1 + 2 + ... + n) = (n - 1)! \cdot \frac{(n + 1)}{2} \cdot n \cdot \sum_{i = 1}^{n!} k_{i} = \\ = \sum_{i = 1}^{n!} k_{i} \cdot n! \cdot (\frac{n + 1}{2}) \equiv 0 (mod n!), \end{matrix} \end{matrix}

hiszen

\frac{n + 1}{2}

egész.
Ellentmondásra jutottunk, hiszen a tagokat kétféle módon összeadva eltérő maradékokat kaptunk

n!

-sal osztva, vagyis a feltevésünk nem teljesül, tehát az állítás igaz.

Kovács Erika Renáta (Fazekas M. Főv. Gyak. Gimn., 11. o.t.)

¹A megoldás során a feladat eredeti szövegétől eltérően a permutációkat nagybetűkkel jelöljük.