Tübitak Lise 2. Aşama 1999 Soru 6

[geo]

$40$ sayının toplamını, $8$ "işlemci'' kullanarak bulmak istiyoruz. Başlangıçta, her işlemcinin ekranında $0$ sayısı bulunuyor. Herhangi bir işlemci, kendisine dışarıdan verilen ya da başka bir işlemciden aktarılan sayıyı, ekranındaki mevcut sayıyla bir birim zamanda toplayarak, elde ettiği sonucu ekranına yazıyor. Ekranındaki sayıyı başka bir işlemciye aktaran bir işlemcinin ekranı kararıyor. Verilen $40$ sayıdan istediklerimizi istediğimiz işlemciye girerek ve işlemcilerin elde ettiği kısmi toplamları da istediğimiz işlemciye aktararak, bu $40$ sayıyı en az kaç birim zamanda toplayabiliriz?

[geo]

Belli bir anda, herhangi bir işlemciye girilmemiş sayılarla, işlemcilerin ekranlarındaki sayılara "işlem görecek kalem'' diyelim. $n\left(c\right)$ ile, $c$ zaman birimi sonundaki işlem görecek kalem sayısını gösterelim. $n\left(0\right)=40+8=48$ dir. $\overline{c}$ zaman sonunda istenen toplam elde edilmişse $n\left(\overline{c}\right)=1$ olur. (Burada genelliği yitirmeden her işlemcinin kullanıldığını varsayıyoruz.) Bir zaman biriminde en fazla $8$ işlem yapılabilir; ayrıca yine bir zaman biriminde, işlem görecek kalem sayısı, en fazla yarıya indirilebilir. Dolayısıyla, $$n\left(c\right)-n\left(c+1\right)\le {\min  \left\{\dfrac{n\left(c\right)}{2},8\right\}\ },$$ ya da eşdeğer biçimde, $$n\left(c+1\right)\ge {\max  \left\{\dfrac{n\left(c\right)}{2},n\left(c\right)-8\right\}\ }$$ olur. Şimdi $M\left(0\right)=48$; $M\left(c+1\right)={\max  \left\{\left\lceil \dfrac{M\left(c\right)}{2}\right\rceil ,\ M\left(c\right)-8\right\}\ }$ sistemine bakalım. ($\left\lceil x\right\rceil :=x$'ten büyük ya da $x$'e eşit olan en küçük tamsayıdır.)

$\overline{C},M\left(\overline{C}\right)=1$ koşulunu sağlayan en küçük tamsayı; $\hat{C}\ $da aranan yanıt ise; $\hat{C}\ge \overline{C}$ dir. $\overline{C}$ yı bulalım: $$\begin{array}{ll}
M\left(0\right)=\ 48; & M\left(1\right)={\max  \left\{\left\lceil \frac{48}{2}\right\rceil ,40\right\}=40\ };\\ \\
M\left(2\right)={\max  \left\{\left\lceil \frac{40}{2}\right\rceil ,32\right\}=32\ }; & M\left(3\right)={\max  \left\{\left\lceil \frac{32}{2}\right\rceil ,24\right\}=24\ };\\ \\
M\left(4\right)={\max  \left\{\left\lceil \frac{24}{2}\right\rceil ,16\right\}=16\ }; & M\left(5\right)={\max  \left\{\left\lceil \frac{16}{2}\right\rceil ,8\right\}=8\ };\\ \\
M\left(6\right)={\max  \left\{\left\lceil \frac{8}{2}\right\rceil ,0\right\}=4\ }; & M\left(7\right)={\max  \left\{\left\lceil \frac{4}{2}\right\rceil ,-4\right\}=2\ }; \\ \\
M\left(8\right)={\max  \left\{\left\lceil \frac{2}{2}\right\rceil ,-6\right\}=1\ }. & \end{array}$$
Yani $\overline{C}=8$ dir. Aranan sayı $\hat{C}\ge 8$ olur.

Aşağıdaki çizelgede, köşeler işlemcileri; üçgenler ilk beş zaman biriminde işlemcilere girilen sayıyı; yönlü kenarlar da, hangi işlemcinin kısmi toplamının hangi işlemciye aktarıldığını göstermek üzere; istenen toplamın $8$ zaman biriminde elde edilebileceği görülmektedir. Yani $\hat{C}=8$ dir.

Kaynak:
Matematik Dünyası 2000-II