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.