Tübitak Lise 1.Aşama 1995 Soru 34

[matematikolimpiyati]

$1$ den $56$ ya kadar doğal sayılar$,$ bir çember etrafına$,$ herhangi ardışık dizili $5$ sayının toplamı en az $K$ olacak şekilde dağıtılmıştır. $K$ en çok kaç olabilir?

$\textbf{a)}\ 15  \qquad\textbf{b)}\ 56  \qquad\textbf{c)}\ 142  \qquad\textbf{d)}\ 143  \qquad\textbf{e)}\ 270$

[Metin Can Aydemir]

Cevap: $\boxed{\text{Hiçbiri}}$

Öncelikle cevabın $140$'dan büyük olamayacağını gösterelim. $56$ dışındaki $55$ sayıyı ardışık beşli sayılar olarak gruplarsak $11$ tane $5$'li grup vardır. Her birindeki sayıların toplamı en az $K$ olduğundan toplam en az $11K$ olacaktır. Dolayısıyla $$1+2+3+\dots+55=\frac{55\cdot 56}{2}\geq 11K\implies 140\geq K$$ elde edilir. Ancak $K$ sayısı $113$'den de büyük veya eşit olmalıdır. Çünkü $1,56,2,54,4,52,6,50,8,48,10,46$, $12$, $44$, $14$, $42$, $16$, $40$, $18,38,20,36,22,34$, $24,36,26,34,28$, $32,30,31,29,33,27$, $35,25,33,23,35,21$, $37$, $19$, $39$, $17$, $41$, $15$, $43$, $13,45,11,47$, $9,49,7,51,5,53,3,55$ şeklindeki bir dizilimde ardışık $5$ sayının toplamı en az $113$'tür. Dolayısıyla istenilen şartı sağlayan en büyük $K$ tamsayısı $113$ ile $140$ arasında olmalıdır. Şıklardan hiçbiri bunu sağlamaz.

[geo]

Yanlış anlamadıysam $K$ sayısının kaç olduğunu bulamadınız; ama $K=113$ olan bir dağılım verdiniz. Cevabın $113$ ile $140$ arasında olduğunu tespit ettiniz.

Ben de biraz uzun bir şekilde $57 \leq K < 142$ olduğunun ispatını birazdan vereceğim, bu da sorunun hatalı olduğu anlamına gelecek.

[geo]

Yanıt: Şıklardan hiçbiri.

$\begin{array}{lclcl}
a_1 + a_2 + a_3 + a_4 + a_5 &=& k_1 &\geq& K \\
a_2 + a_3 + a_4 + a_5 + a_6 &=& k_2 &\geq& K \\
\vdots \\
a_{56} + a_1 + a_2 + a_3 + a_4 &=& k_{56} &\geq& K \\
\end{array}$

Taraf tarafa toplarsak $\displaystyle 5 \cdot \sum_{i=1}^{56}a_i = \sum_{i=1}^{56} k_i \geq 56\cdot K $ elde ederiz.

$\displaystyle \sum_{i=1}^{56}a_i = \sum_{i=1}^{56}i = \dfrac {56\cdot 57}{2}$ eşitliğini yerine yazarsak $\dfrac {5 \cdot 56 \cdot 57}{2} \geq 56\cdot K$ eşitliğini elde ederiz. Eşitsizliği sağlayan en büyük tam sayı $K=142$ dir.

Bu aşamada cevabın $142$ olduğunu düşünebiliriz. Büyük ihtimalle soruyu hazırlayan da böyle düşündü.
Cevabın $142$ olduğunu varsayalım.
$\bmod {56}$ da düşünürek $k_i \neq k_{i+1}$ olmalı. ($k_{i+1} - k_i = a_{i + 5} - a_i$ ve tüm $a_i$ ler birbirinden farklı olmak zorunda)
Örneğin, $k_1 = 142$ olsun, $k_2 \geq 143$ olmak zorunda.
Bu durumda tüm $k_i$ lerin toplamı en az $28\cdot 142 + 28 \cdot 143 = 28 \cdot  285 = \dfrac{5 \cdot 56 \cdot 57}{2}$ olacaktır. Zaten $\displaystyle \sum_{i=1}^{56} k_i = \dfrac{5 \cdot 56 \cdot 57}{2}$ olduğu için $k_i \leq 143$ olmalı.
Bu da ardışık $k_i$ lerin farkının tam olarak $1$ olduğu anlamına gelir.
$|k_{2} - k_{1}| = |a_{6} - a_1| = 1$ omalı.
$a_i$ lerden den biri $1$ olmak zorunda, $a_1=1$ olsun. $a_6 = 2$ olmak zorunda. Yani $k_1 = 142$ ve $k_2 = 143$ (Tekler $142$, çiftler $143$). $k_6 = 143$, $k_7 = 142$. $k_7 - k_6 = a_{11} - a_6 \Rightarrow a_{11} = 1 = a_1$ olmak zorunda. Çelişki.

O halde cevap $142$ den küçük olmalı.
$56$ olabilir mi?
$[1, 2, 3, 4, 47, 5, 6, 7, 8, 31, 9, 10, 11, 12, 15, 13, 14, 16, \dots, 56]$ şeklinde bir dizilim de $K = 57$ oluyor.
Bu durumda $57 \leq K < 142$ olduğunu söyleyebiliriz.

[geo]

Problemi $1$ den $N$ ye kadar olan sayılar için düşündüğümüzde,
İlk etapta $K \leq  \frac {5(N+1)}{2} $.
$N \geq 11$ için yukarıda verdiğim yöntemle $ K = \left \lfloor \frac {5(N+1)}{2} \right \rfloor$ için çelişki elde ediyoruz.
$N = 5k+1$ için Metin Can Aydemir'in çözümdeki yaklaşımıyla $K \leq \dfrac {5N}{2}$ elde ediliyor.

Bilgisayar yardımıyla $N=6, \dots, 18$ için

$\begin{array}{c|c|}
N & K_{\max} & \left \lfloor \frac {5(N+1)}{2} \right \rfloor & \left \lfloor \frac {5(N)}{2} \right \rfloor \\
\hline 6 & 15 & 17 & 15 \\
\hline 7 & 19 & 20 & - \\
\hline 8 & 21 & 22 & - \\
\hline 9 & 23 & 25 & - \\
\hline 10 & 27 & 27 & - \\
\hline 11 & 27 & 30 & 27 \\
\hline 12 & 31 & 32 & - \\
\hline 13 & 33 & 35 & - \\
\hline 14 & 35 & 37 & - \\
\hline 15 & 39 & 40 & - \\
\hline 16 & 40 & 42 & 40 \\
\hline 17 & 43 & 45 & - \\
\hline 18 & 46 & 47 & - \\
\end{array}$

şeklinde bir sonuç elde ediyoruz.
Sadece $N=10$ için $K_{\max} = \left \lfloor \frac {5(N+1)}{2} \right \rfloor = 27$ olabiliyor.

[Lokman Gökçe]

Yanıt: Şıklarda yoktur.

Metin Can Aydemir'in çözümünde $K\leq 140$ olduğu gösterilmişti. Bilgisayar taraması ile $56$ pozitif tam sayı için $K=140$ durumunun örneği aşağıdaki gibidir. Böylece $K_{\max} = 140$ elde edilir.

\[
\begin{array}{c|l|c}
\text{Başlangıç} & \text{Ardışık }5\text{ sayı} & \text{Toplam}\\
\hline
1 & 56,45,23,6,22 & 152\\
2 & 45,23,6,22,44 & 140\\
3 & 23,6,22,44,46 & 141\\
4 & 6,22,44,46,24 & 142\\
5 & 22,44,46,24,7 & 143\\
6 & 44,46,24,7,20 & 141\\
7 & 46,24,7,20,43 & 140\\
8 & 24,7,20,43,47 & 141\\
9 & 7,20,43,47,25 & 142\\
10 & 20,43,47,25,8 & 143\\
11 & 43,47,25,8,18 & 141\\
12 & 47,25,8,18,42 & 140\\
13 & 25,8,18,42,48 & 141\\
14 & 8,18,42,48,26 & 142\\
15 & 18,42,48,26,9 & 143\\
16 & 42,48,26,9,16 & 141\\
17 & 48,26,9,16,41 & 140\\
18 & 26,9,16,41,49 & 141\\
19 & 9,16,41,49,27 & 142\\
20 & 16,41,49,27,10 & 143\\
21 & 41,49,27,10,14 & 141\\
22 & 49,27,10,14,40 & 140\\
23 & 27,10,14,40,50 & 141\\
24 & 10,14,40,50,28 & 142\\
25 & 14,40,50,28,11 & 143\\
26 & 40,50,28,11,12 & 141\\
27 & 50,28,11,12,39 & 140\\
28 & 28,11,12,39,51 & 141\\
29 & 11,12,39,51,29 & 142\\
30 & 12,39,51,29,21 & 152\\
31 & 39,51,29,21,1 & 141\\
32 & 51,29,21,1,38 & 140\\
33 & 29,21,1,38,52 & 141\\
34 & 21,1,38,52,30 & 142\\
35 & 1,38,52,30,19 & 140\\
36 & 38,52,30,19,2 & 141\\
37 & 52,30,19,2,37 & 140\\
38 & 30,19,2,37,53 & 141\\
39 & 19,2,37,53,31 & 142\\
40 & 2,37,53,31,17 & 140\\
41 & 37,53,31,17,3 & 141\\
42 & 53,31,17,3,36 & 140\\
43 & 31,17,3,36,54 & 141\\
44 & 17,3,36,54,32 & 142\\
45 & 3,36,54,32,15 & 140\\
46 & 36,54,32,15,4 & 141\\
47 & 54,32,15,4,35 & 140\\
48 & 32,15,4,35,55 & 141\\
49 & 15,4,35,55,33 & 142\\
50 & 4,35,55,33,13 & 140\\
51 & 35,55,33,13,5 & 141\\
52 & 55,33,13,5,34 & 140\\
53 & 33,13,5,34,56 & 141\\
54 & 13,5,34,56,45 & 153\\
55 & 5,34,56,45,23 & 163\\
56 & 34,56,45,23,6 & 164
\end{array}
\]