Geomania.Org Forumları

Yarışma Soruları => Uluslararası Matematik Olimpiyatı => 2001 => Konuyu başlatan: ERhan ERdoğan - Haziran 05, 2014, 09:14:28 ös

Başlık: Uluslararası Matematik Olimpiyatı 2001 Soru 4
Gönderen: ERhan ERdoğan - Haziran 05, 2014, 09:14:28 ös
$n$, $1$ den büyük tek bir tam sayı olsun. $k_1,k_2,\dots,k_n$ tam sayıları verilsin. $1,2,\dots,n$ sayılarının her $a=(a_1,a_2,\dots,a_n)$ permütasyonu için $$S(a)=\sum\limits_{i=1}^{n}k_ia_i$$ şeklinde tanımlanıyor. $n!$, $S(b)-S(c)$ yi bölecek şekilde $b$ ve $c$ permütasyonlarının ($b\neq c$) olduğunu kanıtlayınız.
Başlık: Ynt: Uluslararası Matematik Olimpiyatı 2001 Soru 4
Gönderen: geo - Eylül 19, 2021, 08:31:26 ös
Tüm permütasyonları sırasıyla yazalım:

$\begin{array}{lcl}
p_1  & = & (1,2,\dots, n-1, n) \\
p_2  & = & (1,2,\dots, n, n-1) \\
& \dots & \\
p_{(n-1)!} & = & (1, n, \dots, 3, 2) \\
p_{(n-1)! + 1} & = & (2,1,\dots, n-1, n)\\
& \dots & \\
p_{2(n-1)!} & = & (2, n, \dots, 3, 1) \\
& \dots & \\
p_{(n-1)(n-1)! + 1} & = & (n,1,\dots, n-2, n-1)\\
& \dots & \\
p_{n!} & = & (n, n-1, \dots, 2, 1) \\
\end{array}$

$\sum\limits_{i = 1}^{n!} S(p_i)$ toplamını hesaplayalım.

$\begin{array}{lcl}
\sum\limits_{i = 1}^{n!} {S(p_i)} & = & (n-1)!\cdot \dfrac {n(n+1)}{2} \cdot \sum\limits_{i = 1}^{n} k_i \\
 & = & n!\dfrac{n+1}{2} \sum\limits_{i = 1}^{n} k_i \\
\end{array}$

$n$ tek olduğu için $ \sum\limits_{i = 1}^{n!} {S(p_i)} \equiv 0 \pmod {n!}$ olacaktır.

Herhangi $b,c \in \{p_1, p_2, \dots, p_{n!}\}$ ve $b \neq c$ çifti için $S(b) - S(c) \not \equiv 0 \pmod {n!}$ olmadığını varsayalım.
Bu durumda $S(p_i)$ ifadelerinin her biri $\bmod {n!}$ de farklı bir değere denk olacaktır.

$\begin{array}{lclr}
\sum\limits_{i = 1}^{n!} {S(p_i)} & \equiv & 0 + 1 + \cdots + (n! - 1) & \pmod {n!}\\
 & \equiv & \dfrac {(n!-1)n!}{2} & \pmod {n!} \\
\end{array}$

Bulduğumuz bu iki toplamı eşitlersek ($c_1$ ve $c_2$ birer tam sayı olmak üzere)

$c_1\cdot n! = c_2\cdot n! + \dfrac {n! - 1}{2} \cdot n!$

elde ederiz. Buradan $\dfrac {n! - 1}{2}$ ifadesinin bir tam sayı olması gerektiği çıkar. $n>1$ iken $n!$ çift ve $n! - 1$ tek sayı olacağı için bu mümkün değildir. Çelişki.

O halde, ($i \neq j$ olmak üzere) en az bir $(p_i, p_j)$ çifti için $S(p_i) \equiv S(p_j) \pmod {n!}$ olmak zorunda. $\blacksquare$
SimplePortal 2.3.3 © 2008-2010, SimplePortal