Ay: Kasım 2015

Bir tartı sorusu üzerine çeşitlemeler (Çözüm)

Her gruptan farklı miktarda para seçmemiz lazım ama hileli torba sayısını bilmediğimizden bir gruptan alınan paraların sayısının diğer gruplardan alınan paraların toplamı şeklinde yazılamayacağını sağlamamız lazım. Örneğin birinci torbadan 1, ikinci torbadan da 2 para alırsak başka bir torbadan, diyelim üçüncü torbadan 1+2=3 para alamayız. Hileli torba sayısı bilinmediğinde eğer toplamda 3 gram eksiş çıkarsa birinci ve ikinci torbalar mı yoksa sadece üçüncü torba mı hileli sorusunu tek tartıyla çözemeyiz.

Bu şekilde torbalardan toplam şartını sağlayacak şekilde en küçük miktarda parayı alarak seçimimizi yapalım.

Birinci torba: 1 para

İkinci torba: 2 para

Üçüncü torba: 4 para. 3 para olmaz çünkü 1 + 2 = 3.

Dördüncü torba: 8 para. 1, 2 ve 4 para ile 1’den 7’ye kadar her toplam üretilebilir.

Beşinci torba: 16 para. 1, 2, 4 ve 8 para ile 1’den 15’e kadar her toplam üretilebilir.

Altıncı torba: 32 para. 1, 2, 4, 8 ve 16 para ile 1’den 31’e kadar her toplam üretilebilir.

Yedinci torba: 64 para. 1, 2, 4, 8, 16 ve 32 para ile 1’den 63’e kadar her toplam üretilebilir.

Sekizinci torba: 128 para. 1, 2, 4, 8, 16, 32 ve 64 para ile 1’den 127’ye kadar her toplam üretilebilir.

Dokuzuncu torba: 256 para. 1, 2, 4, 8, 16, 32, 64 ve 128 para ile 1’den 255’ye kadar her toplam üretilebilir.

Onuncu torba: 512 para. 1, 2, 4, 8, 16, 32, 64, 128 ve 256 para ile 1’den 511’ye kadar her toplam üretilebilir.

Dikkat edilirse her torbadan 2’nin değişik kuvvetleri kadar para alıyoruz. Toplamda da

1+2+4+8+16+32+64+128+256+512 = 1023 adet para ile sorunu çözebiliriz.

Her torbadan yukarıda belirtilen miktarda para alarak tartımı yaptıktan sonra okuduğumuz değeri beklenen toplamdan (\(10\cdot{1023}=10230 \)) çıkarıyoruz. Yani tartıda eğer 10128 değerini okuduysak 10230 – 10128 = 102 farkını elde ediyoruz. Bu farkı ikilik düzende yazarsak 1100110 şeklinde hangi torbaların bu toplama etki ettiğini görürüz. Sayıyı sağdan sola doğru okuyarak ikinci, üçüncü, altıncı ve yedinci torbaların hileli paralar içerdiğini görürüz.

Tabii ki çeşitlemelere devam edilebilir. Korkmayın hemen, devam etmeyeceğim. Yani en azından bu yazıda devam etmeyeceğim.

Eğer her torbadaki hile miktarı değişik ise, yani bir torbadaki paralar 1 gram eksikse, bir başka torbadaki paralar 2 gram eksikse bu hileli torbalar tek tartıda bulunabilir mi? Her torba farklı miktarlarda hileliyse tek tartıda hangi torbanın ne kadar hileli olduğu bulunabilir mi? Torbalardaki hileler nasıl olmalıdır ki tek tartıda sayısı belli olmayan hileli torbalar bulunabilsin?

Cenaze

ACI KAYBIMIZ

Lambrecht eşrafından

AURORA DINKLY

24 Kasım 2015 gecesi hakk’ın rahmetine kavuşmuştur.

Cenazesi 28 Kasım 2015 günü öğle namazının ardından bahçedeki mezarlığa defnedilecektir.

İş arkadaşları Aurora'nın tabutu başında
İş arkadaşları Aurora’nın tabutu başında

Bir tartı sorusu üzerine çeşitlemeler

Klasik bir tartı sorusu vardır:

Kral kuyumcuya 10 torba her biri 10 gram ağırlığında altın para siparişi verir. Kuyumcu da siparişi yerine getirir ama kralın fark etmeyeceğini düşünerek bir torbadaki altınları 9 gram yapar. Bu hile bir şekilde kralın kulağına gider ve kuyumcuyu cezalandırmak ister. Son bir şans olarak da kuyumcudan hileli torbayı tek bir tartıda bulmasını ister. Bu tartıda her torbadan istediği kadar para kullanabilir ve terazi paraların ağırlığını oldukça duyarlı bir şekilde gösterebiliyor.

Bu soru genelde hep bu şekilde sorulur ve çok basit bir cevap beklenir. Hatta benim çalıştığım şirkette iş görüşmesinde adaylara sorulan standart sorulardan biridir. Cevap gerçekten de basittir. Birinci torbadan 1, ikinci torbadan 2, üçüncü torbadan 3 ve bu şekilde devam ederek son torbadan da 10 adet para alınır ve teraziye konur. Eğer paralar hilesiz olsaydı terazi bize 550 gram göstermeliydi. Beklenen ile gösterilen değer arasındaki fark torba numarasını verir. Örneğin eğer terazi 543 gram gösterirse demek ki 7 numaralı torba hileli paralarla doludur. Çünkü o torbadan 7 tane para aldık ve her para normalden bir gram daha hafif.

Bu soru çok daha değişik şekillerde de sorulabilir aslında. Örneğin en fazla bir torba hileliyse diye sorulsa yukarıdaki çözüm bunu da çözer. Eğer hileli torba yoksa terazide 550 gram okuruz.

Bir torba hileliyse en az kaç para ile hileli torbayı bulabiliriz? Eğer bir torbanın hileli olduğu verilmişse onuncu torbadan 10 tane para almaya gerek yok. O zaman çözümdeki mantığı 450 gram toplamı için yorumlamamız yeterli. Eğer terazi 450 gramdan az gösterirse hatalı torbanın numarası aradaki fark kadardır. Eğer 450 gram ölçersek de hatalı torba onuncu torbadır.

 Peki ya kaç torbanın hatalı olduğu verilmezse bu soruyu en az kaç parayla çözebiliriz?

Yazı Tura (Çözüm)

\(\frac{1}{3} \) olasılığını üretmek için yapmamız gereken tek şey birbirinden bağımsız eşit olasılıklı üç değişik olay bulmak ve geri kalan tüm olayları yok saymak. Böylece yeni sistemimizde her birinin olasılığı \(\frac{1}{3} \) olan üç olay bulunacak.

Hilesiz para için arka arkaya iki yazı tura atma olaylarını alalım. Yazı ve tura olasılıkları eşit olduğundan her ikili yazı turanın sonucu da eşit olasılıktadır. Bunları şöyle listeleyebiliriz.

\(p(YY) = p(Y)\cdot{p(Y)}=\frac{1}{2}\cdot{\frac{1}{2}}=\frac{1}{4} \)

\(p(YT) = p(Y)\cdot{p(T)}=\frac{1}{2}\cdot{\frac{1}{2}}=\frac{1}{4} \)

\(p(TY) = p(T)\cdot{p(Y)}=\frac{1}{2}\cdot{\frac{1}{2}}=\frac{1}{4} \)

\(p(TT) = p(T)\cdot{p(T)}=\frac{1}{2}\cdot{\frac{1}{2}}=\frac{1}{4} \)

Bu dört olaydan herhangi birini attığımız zaman istediğimiz sonucu elde ederiz. Örneğin iki kere tura gelme olayını atarsak, yani iki kere tura geldiğinde bunun yerine tekrar yine iki kere yazı tura atarsak, sadece her YY, TY ve YT olayları kalır ve her biri birbirinden bağımsız ve eşit olasılıktadır.

Eğer para hileli ise yukarıda tanımladığımız olaylarla problemi çözemeyiz çünkü eşit olasılıklı üç olay bulamayız.

\(p(Y)=p, p(T)=1-p, p\neq{\frac{1}{2}} \) olsun

\(p(YY) = p(Y)\cdot{p(Y)}=p\cdot{p} \)

\(p(YT) = p(Y)\cdot{p(T)}=p\cdot{(1-p)} \)

\(p(TY) = p(T)\cdot{p(Y)}=p\cdot{(1-p)} \)

\(p(TT) = p(T)\cdot{p(T)}=(1-p)\cdot{(1-p)} \)

Görüldüğü eşit olasılıklı iki olay var sadece (YT ve TY).

Bu durumda yapmamız gereken tek şey yazı turaları ikili gruplar halinde değil de üçlü gruplar halinde atmak. Şimdi bu olayların olasılıklarına bakalım.

\(p(YYY) = p(Y)\cdot{p(Y)}\cdot{p(Y)}=p\cdot{p}\cdot{p} \)

\(p(YYT) = p(Y)\cdot{p(Y)}\cdot{p(T)}=p\cdot{p}\cdot{(1-p)} \)

\(p(YTY) =p(Y)\cdot{p(T)}\cdot{p(Y)}=p\cdot{(1-p)}\cdot{p} \)

\(p(YTT) =p(Y)\cdot{p(T)}\cdot{p(T)}=p\cdot{(1-p)}\cdot{(1-p)} \)

\(p(TYY) = p(T)\cdot{p(Y)}\cdot{p(Y)}=(1-p)\cdot{p}\cdot{p} \)

\(p(TYT) = p(T)\cdot{p(Y)}\cdot{p(T)}=(1-p)\cdot{p}\cdot{(1-p)} \)

\(p(TTY) =p(T)\cdot{p(T)}\cdot{p(Y)}=(1-p)\cdot{(1-p)}\cdot{p} \)

\(p(TTT) =p(T)\cdot{p(T)}\cdot{p(T)}=(1-p)\cdot{(1-p)}\cdot{(1-p)} \)

Bu olaylar arasında olasılığı birbirine eşit üç olay seçmek kolay, örneğin YYT, YTY ve TYY aradığımız özelliğe sahip olaylardır. Yapılacak tek şey üç yazı tura ardından bu olaylar dışında başka bir sonuç çıkarsa bu olayı olmamış varsayıp yeniden üç kere yazı tura atmak.

Conway’in Hayat Oyunu

Conway’in hayat oyunu‘nu oynamak için basit bir javascript programı yazdım. Oyun, canlı ve cansız hücrelerden oluşan bir ızgara ve hücrelerde ölüm ve doğumu tanımlayan bir dizi kuraldan oluşuyor. Başlangıç durumu tanımlandıktan sonra oyun, daha doğrusu simülasyon, başka etkileşim olmadan bu kurallar doğrultusunda işlemeye başlıyor.

Oyun aslında sonsuz büyüklükte bir ızgara için tanımlanmış ama ben programda 20×20 büyüklüğünde ızgara kullandım ve ızgaranın dışındaki bölgede sadece ölü hücreler varmış gibi hesap yaptım. Programda canlı hücreler içi dolu siyah kareler, ölü hücreler de içi boş beyaz kareler şeklinde gösteriliyor.

Standart kurallara göre bir canlı hücrenin çevresinde eğer bir ya da daha az canlı hücre varsa o hücre ölüyor (aşırı yalnızlık). Eğer dört veya daha fazla canlı hücre varsa yine ölüyor (aşırı kalabalık). Eğer iki ya da üç canlı hücre varsa o zaman hücre canlı kalıyor. Ölü bir hücrenin etrafında eğer tam üç canlı hücre varsa o hücre canlanıyor (üreme). Bu kurallardaki sayılar programdaki bazı ayarlarla değiştirilebiliyor. Bu ayarların açıklamaları ayrıca program sayfasında bulunmaktadır.

Örnekler:

Hücrenin ölmesi:

İkinci sıra ve ikinci sütunda görülen canlı hücrenin çevresindeki sekiz hücre de ölü, yani doğrudan komşuluğundaki canlı hücre sayısı aşırı yalnızlıktan ölme sınırı olan birden az. Bu nedenle bir sonraki nesilde bu hücre de ölecektir.

single          →       empty

Hücrenin canlı kalması:

Aşağıdaki dört canlı hücrenin her birinin üç tane canlı komşusu var. Aşırı yalnızlık sınırından fazla aşırı kalabalık sınırından da daha az canlı komşu olduğundan bu hücreler bir sonraki nesilde yine canlı kalacaktır.

square       →       square

Hücrenin doğumu:

Aşağıdaki üç canlı hücrenin her birinin iki adet canlı komşusu var. Bu üç hücre de bir sonraki nesilde canlı kalacaktır. Bu üçlü grubun sol altındaki ölü hücrenin ise üç canlı komşusu var. Dolayısıyla bu hücre bir sonraki nesilde canlanacaktır. Diğer bütün ölü hücrelerin en fazla iki canlı komşusu olduğundan bu hücrelerde canlanma doğum olmayacaktır.

birth        →      square

Hepsi bir arada:

Ortadaki canlı hücrenin iki canlı komşusu var. Bu yüzden bu hücre bir sonraki nesilde canlı kalacak. En alttaki ve en üstteki canlı hücrelerin ise yalnızca bir canlı komşusu var. Dolayısıyla bu hücreler aşırı yalnızlıktan bir sonraki nesilde ölecek. Ortadaki canlı hücrenin solundaki ve sağındaki ölü hücrelerin ise üçer adet canlı komşusu bulunduğundan bu hücreler bir sonraki nesilde canlanacak, diğer bütün ölü hücreler ise ölü kalacak, çünkü hepsinin de en fazla iki tane canlı komşusu var. Bu yeni nesil de aynı mantıkla değişip bir sonraki nesilde ilk nesle dönüşecek.

vbar      →      hbar         →      vbar

 

Bu bağlantı üzerinden oyunu kendiniz de deneyebilirsiniz. Program javascript ile yazılmıştır ve kaynak kodu tarayıcı yardımıyla alınabilir.

yilmazaksoy.com/apps/GameOfLife.html