Matematik Atölyesi: Bulmaca #1

Nehir Geçme Bulmacası

Evine dönerken yanında bir kurt, bir keçi ve biraz da lahana bulunduran çiftçinin karşısına bir nehir çıkar. Nehrin kenarında gördüğü kayık çiftçinin her seferde kurt, keçi ya da lahanadan birini yanına almasına izin verecek büyüklüktedir.

Problem ise şudur: Eğer yalnız kalırlarsa kurt keçiyi, keçi ise lahanayı yiyecektir. Bu durumda çiftçi ne yapmalıdır? (Not: Nehrin karşısına yüzerek geçmek mümkün değildir.)

Cevap

Bu üçlü arasında sadece kurt ile lahananın yalnız kalmasında sorun yoktur. O halde önce keçi karşıya geçilir.

Geri dönülür kurt veya lahanadan biri alınır. (Biz lahanayı aldığımızı düşünelim.) Lahana karşıya bırakılınca keçi ile yalnız kalmaması için keçi geri götürülür ve nehrin sol tarafına bırakılır.

Bu sefer kurt kayığa alınır ve nehrin sağ tarafına götürülür. Böylece nehrin sağ tarafında kurt ile lahana kalmış olur ki bunda bir sorun yoktur.

En son hamlede keçi karşıya geçirilir ve problem çözülmüş olur.

Bulmacada kurt yalnız kaldıklarında lahanayı da yiyor olsaydı, çözüm mümkün olmazdı. Fakat bunu anlayabilmek için tüm varyasyonları denememiz gerekecekti. Bu da boşa zaman ve enerji kaybı anlamına gelir. Yani bulmacada çözüme ulaşılmasına rağmen doğru bir yöntem bulmuş değiliz.

Peki bu tip bir soruyla uğraşırken işi kolaylaştıracak genel bir yöntem bulmak mümkün müdür?

Nehir Algoritması

Matematiğin görece yeni bir alanı olan çizge teorisinde bir cismin ne olduğu değil, nerede ve kimlerle bağlantılı olduğu önemlidir. Bu dalda noktalar cisimleri, çizgiler ise bağlantıları gösterir. O halde bulmacadaki keçi, kurt ve lahananın her birini nokta olarak gösterelim. Örneğin kurt yalnız kaldıkları takdirde keçiyi yediği için kurtla keçi arasında yeme ilişkisini ifade eden bir çizgi bulunsun.

Yani çizgilerle bağlanan noktalar bulmaca için tehlike arz eder. Çizilecek grafikte bir nokta ortadan kaybolduğunda, noktaya bağlı olan çizgiler de kaybolur.

Bulmacaya göre her seferinde yanımıza üçlüden birini alabiliyoruz. Bunu yaparken hangisini seçeceğimize nokta-çizgi yöntemiyle şöyle karar veririz: Noktalardan hangisi kapatılırsa (o noktaya bağlı olan doğrular da kaybolacağı için) tüm grafikte çizgi kalmaz?

Eğer keçiyi gösteren nokta kapatılırsa, ona bağlı olan doğrular da yok sayılır. Geride sadece kurt ve lahanayı gösteren noktalar kaldığı için soruya buradan başlamak gerekir.

Yarattığımız algoritmanın bize söylediği başka bir şey daha var: Kayıkta en az silinen nokta sayısı kadar yer olmalıdır. Böylece çizilen grafik ne kadar karmaşık olursa olsun kayıkta yer durumuna bakarak sorunun çözümünün olup olmadığı hemen anlaşılabilir.

Peki nehir bulmacasındaki üçlüye bir de tavşan eklenirse ne olur?

İkinci Nehir Örneği

Diyelim ki çiftçinin yanındakiler kurt, keçi, lahana ve tavşan olsun. Yalnız kaldıkları takdirde keçi ve tavşanı kurt, lahanayı ise keçi ve tavşan yiyor. Bu durumda grafik şöyle olur:

Bulmacanın bir önceki versiyonunda sadece keçiyi gösteren noktayı kapamak grafikteki tüm çizgileri yok etmişti. Bu sefer dörtlünün her biri teker teker denenmesine rağmen hiçbir nokta tek başına grafikteki tüm çizgileri yok edemiyor.

1. Tavşan noktası ve noktaya bağlı çizgiler kaldırılınca.
2. Lahana noktası ve noktaya bağlı çizgiler kaldırılınca.
3. Keçi noktası ve noktaya bağlı çizgiler kaldırılınca.
4. Kurt noktası ve noktaya bağlı çizgiler kaldırılınca.

O halde iki noktayı kaldırmayı denemeliyiz. Örneğin;

tavşan ve keçi noktaları ile noktalara bağlı çizgiler kaldırılınca grafik bu hale geliyor. Yani sonuca ulaşmak için ilk adımı başarıp kayıkta kaç kişilik yer olması gerektiğini bulduk: Kayıkta en az iki kişilik yer olunca bulmaca çözülebilir.

Başta basit bir bulmaca gibi görünen nehirden karşıya geçme sorusunu çizge teorisiyle birleştirince karşımıza önce grafikler çıktı. Bu grafikleri düşünerek bir algoritma yazdık ve karmaşık durumları hızlıca çözme yolunun nereden geçtiğini öğrenmiş olduk.

Bi’ Göz Atmakta Fayda Var

1. Kurt-keçi-lahana-tavşan sorusunu çözün.
2. Kurt-keçi-lahana-tavşan dörtlüsünün yanına havuç, kedi ve fare üçlüsünü ekleyelim. Havucu keçi, tavşan ve farenin, fareyi ise sadece kedinin yediğini varsayalım. Bu durumda her şeyi nehrin öteki tarafına geçirebilmek için kayığın boyutu en az kaç kişilik olmalıdır?

M. Serkan Kalaycıoğlu