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

[geo]

Ekranı kararan işlemcinin bir daha kullanılmadığını düşünerek sonuca gitmeye çalışacağım. Böyle düşünmemdeki neden, soruda aktarma yapan işlemcinin ekranında $0$ yazar şeklinde bir ifade olmaması.
Büyük ihtimalle çözüm için işlemcilerin ekranının kararmasına gerek yok; ama soruda böyle verdiği için buna göre bir çözüm yapacağım.

Bir işlemciye dışarıdan bir sayı verildiyse o işlemci $Y$ (yükleme) işlemi, başka bir işlemciden sayı alan işlemci $T$ (toplama) işlemi, başka bir işlemciye sayı veren işlemci $A$ (aktarma) işlemi, boşta duran işlemci de $B$ (boşta) işlemi yapmış olsun.

$8$ işlemci ile $8$ birim zamanda (adımda) şöyle bir toplama gerçekleştirilebilir:
İlk $5$ sürede, $40$ sayı işlemcilere yüklenir.
Sonra $2\to 1$, $4\to 3$, $6\to 5$, $8\to 7$ şeklinde aktarma yapılır.
Sonra $3\to 1$, $7\to 5$ şeklinde aktarma yapılır.
Sonra da $5\to 1$ şeklinde aktarma yapılır.

Daha az sayıda sürede bu toplama işleminin yapılamayacağını göstereceğiz.
$p\leq 5$ işlemci ile sadece yüklemeler (en az) $\left \lceil \dfrac {40}{p} \right \rceil \geq \dfrac {40}{5} = 8$ birim zamanda yapılabilir.
Bu durumda; $8$ den az sürede tamamlamak için $p=6$, $p=7$ ya da $p=8$ işlemci kullanılabilir. Hiç kullanılmayan işlemcileri yok gibi düşüneceğiz, yani onlar için $B$, yani boşta demeyeceğiz.

$p=6$ işlemci kullanıldığını varsayalım. $40$ tane $Y$ yapılacağı için, $7$ birim zamanda tamamlamaya çalışacağız. Toplamda $7\times 6 = 42$ işlem yapılması gerek. $6$ işlemcinin toplamlarını birbirine aktarmak için sadece ilk kısmi toplam hesapları için bile $3T$, $3A$ yani $6$ işlem gerekecek. $40 + 6 > 42$ olduğu için; $p=6$ işlemci ile $7$ birim zamanda bu toplama işlemi yapılamaz.

$p=7$ işlemci kullanıldığını varsayalım. $7\times 7 = 49$ işlem yapılması gerek. $40Y$ işlemi yüklemeler için gerekli. $7$ işlemcinin kısmi toplamları için $6T$ ve $6A$ işlem gerekli. $40+12 > 49$ olduğu için; $p=7$ işlemci ile $7$ birim zamanda bu toplama işlemi yapılamaz.

$p=8$ işlemci kullandığımızı varsayalım. $7 \times 8 = 56$ işlem yapılması gerek. $40Y$ işlemi yüklemeler için gerekli. $8$ işlemcinin kısmi toplamları için $7T$ ve $7A$ işlem gerekli. Toplamda $40 + 14 = 54$ işlem oldu. $3$ tane $B$ durumu (işlemi) bulursak; $p=8$ işlemci ile $7$ birim zamanda bu toplama işleminin yapılamayacağını göstermiş olacağız. İlk aktarma işleminin $t_1$, ikinci aktarma işleminin $t_2 \geq t_1$,  son aktarma işleminin $t_7$ de yapıldığını varsayalım. Bir adımda en fazla $4$ aktarım yapılabileceği ve son aktarımın gerçekleştiği sürede başka aktarım yapılamayacağı için (aksi halde iki aktarımın kısmi toplamları tekrardan aktarılmalı) $t_7 - t_1 \geq t_7 - t_2 \geq 2$ olmalı. Bu da ilk iki aktarımda kullanılan işlemcilerin en az $2$ şer kez $B$ durumunda kalacağı anlamına gelir. En az $4$ tane $B$ durumu elde etmiş olduk. $(40 + 14) + 4 = 58 > 56$ olduğu için $p=8$ işlemci ile $7$ birim zamanda bu toplama işlemi yapılamaz.

Not: $p=6,7$ işlemci için $B$ durumunu kullanmamıza gerek kalmadı. Yani aktarma yapan işlemcinin kararınca bir daha kullanılmadığı varsayımını yapmamıza gerek kalmadı.
$p=8$ işlemci için $3B$ durumunu aktarma yapan işlemcinin bir daha kullanılabileceği şekilde bulabilirsek; çözümün başındaki kabulü yapmamıza gerek olmayacaktır.

[geo]

Ekranı kararan işlemcinin bir daha kullanılabildiği durum için de bir çözüm vermeye çalışacağım.

Amacımız, $40$ sayının toplamını $8$ işlemci kullanarak minimum sürede hesaplamak. Her işlemci, bir zaman biriminde şu işlemlerden birini gerçekleştirebilir:

• bir sayıyı yükleme ($Y$),
• iki sayıyı toplama ($T$),
• bir sayıyı başka bir işlemciye aktarma ($A$), veya 
• boşta kalma ($B$).

 
$8$ İşlemci ile $8$ Birim Zamanda Çözüm 

• Yükleme Aşaması ($5$ birim zaman) 
     - $40$ sayı, $8$ işlemciye dağıtılır ve yüklenir. Her işlemci bir zaman biriminde bir sayı yükleyebilir. 
     - $8$ işlemci ile her bir zaman biriminde $8$ sayı yüklenebilir. 
     - Bu nedenle, tüm $40$ sayının yüklenmesi için gereken süre: \[
     \lceil 40 / 8 \rceil = 5 \, \text{birim zaman.}
     \]
• Aktarım Aşaması ($3$ birim zaman.) 
     - Adım 1: $P_2 \to P_1$, $P_4 \to P_3$, $P_6 \to P_5$ ve $P_8 \to P_7$. 
     - Adım 2: $P_3 \to P_1$ ve $P_7 \to P_5$ aktarılır.
     - Adım 3: $P_5 \to P_1$. $P_1$ işlemcisi toplam sonucu barındırır. 
  Bu aktarım aşaması $3$ zaman birimi sürer. 
  

Yükleme ve aktarım aşamalarını toplarsak:  \[
5 \, \text{(yükleme)} + 3 \, \text{(aktarım)} = 8 \, \text{birim zaman.}
\] 

8 Zaman Biriminden Daha Az Sürenin İmkansız Olduğunun Kanıtı 

$8$ zaman biriminden daha az sürede işlemi tamamlamanın imkansız olduğunu kanıtlamak için gereken minimum işlem sayısını hesaplayacağız ve bu işlemlerin mevcut işlemcilerle $8$ birimden az sürede gerçekleştirilemeyeceğini göstereceğiz. 
$t$ ile toplam birim zamanı, $p$ ile de tüm işlemler yapılırken kullanılan farklı işlemci sayısını ifade edelim.

Her işlemci $t$ zaman biriminde $t$ işlem gerçekleştirebilir. $8$ işlemci ile toplam $8t$ işlem yapılabilir. 

Toplam İş Yükünün Ana Bileşenleri 

1. Yükleme İşlemleri: 
   $40$ sayının yüklenmesi tam olarak $40$ işlem gerektirir. 

2. Aktarım ve Toplama İşlemleri: 
   $p$ işlemci kullanıldığı durumda en az $(p - 1)$ aktarım ve $(p - 1)$ toplama işlemi gerekir, toplamda $2(p - 1)$ işlem. 

3. Boşta Kalma İşlemleri: 
   - Eğer bir adımda en çok $p$ işlemci aktifse, kalan en az $8 - p$ işlemci o adımda boşta kalır. 
   - Son adımda, en az $6$ işlemci boşta kalır; çünkü sadece ya bir işlemciye yükleme yapılabilir ya da birer işlemci toplama ve aktarımda yer alır. 
Toplam boşta kalma işlemleri:  \[
(t - 1)(8 - p) + 6\] 
Toplam İş Yükü Denklemi 

Toplam işlem sayısı şu koşulu sağlamalıdır:  \[
\text{Yükleme İşlemleri} + \text{Aktarım + Toplama İşlemleri} + \text{Boşta Kalma İşlemleri} \leq 8t
\] 
Yerine koyarsak:  \[
40 + 2(p - 1) + (t - 1)(8 - p) + 6 \leq 8t
\] 

Terimleri açıp:  \[
40 + 2p - 2 + 8t - 8 - pt + p + 6 \leq 8t
\] 

Düzenlersek:  \[
p(t - 3) \geq 36 \implies t-3\geq \dfrac{36}p \geq \dfrac{36}8 = \dfrac 92 \implies t\geq \dfrac{15}2
\] elde ederiz. O halde, $t \geq 8$. 

Sonuç:  
$8$ işlemci ile $40$ sayının toplamını hesaplamak için gereken minimum süre:  \[
\boxed{8 \, \text{birim zaman.}}
\]