Gönderen Konu: Uluslararası Matematik Olimpiyatı 2001 Soru 4  (Okunma sayısı 1756 defa)

Çevrimdışı ERhan ERdoğan

  • G.O Genel Moderator
  • Geo-Maniac
  • ********
  • İleti: 1421
  • Karma: +12/-0
Uluslararası Matematik Olimpiyatı 2001 Soru 4
« : 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.

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1801
  • Karma: +8/-0
Ynt: Uluslararası Matematik Olimpiyatı 2001 Soru 4
« Yanıtla #1 : 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$

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 
SimplePortal 2.3.3 © 2008-2010, SimplePortal