Matematik Atölyesi – Algoritma #5

Doğru Pizza Dilimi

Üç arkadaş üç farklı pizza dilimini paylaşacaktır.

Pizzalar:

68591

Pizza 1: Dört peynirli.

20665-white-chicken-pizza-600X600

Pizza 2: Tavuklu.

pineapple pizza

Pizza 3: Ananaslı.

Üç arkadaş bu üç pizzayı altı şekilde paylaşabilir:

20190514_170727.jpg
P1:Pizza 1, P2:Pizza 2, P3:Pizza 3.

Ne Kadar Çok İstiyorsun?

Birer dilim pizza yemek çok basit bir işmiş gibi görünse de olayın arka planında tahmin edilemeyecek kadar çok detay vardır. Öncelikle bu üç dilimin maliyeti işin içindedir. Bir de tercih meselesi vardır; malum herkesin damak tadı aynı değil.

Diyelim ki bu üç dilim toplam 6 lira tuttu. Ali, Steve ve Jane için pizza tercihleri de aşağıdaki gibi olsun:

  1. Ali için ilk tercih dört peynirli. Eğer onu alamazsa tavuklu; son tercihi ise ananaslı.
  2. Steve için ilk tercih tavuklu, ikincisi ananaslı ve son olarak dört peynirli.
  3. Jane’in tercihleri sırasıyla tavuklu, dört peynirli ve ananaslı şeklindedir.

Bu durumda kimin hangi dilimi kaç liraya alacağına (adil bir şekilde) nasıl karar verilebilir?

Ev Arkadaşı Problemi (Kira Harmonisi Problemi)

İki (veya daha fazla) arkadaş kiraladıkları evde odaları ve kirayı adil olarak nasıl bölüşür sorusu uzun yıllar matematikçileri meşgul etmiştir. Ev arkadaşı problemi olarak bilinen bu soru adil paylaşmanın en bilindik problemlerinden biridir.

Ev arkadaşı probleminin adil ve kıskanç olmayan çözümlerinden biri 2004’te yayımlanan Atila Abdulkadiroğlu, Tayfun Sönmez ve Utku Ünver’in ortak çalışmasında yer alır. Bu üçlünün açık artırma algoritması adil paylaşımın en ünlü çözümlerinden biridir. (Hatta ev arkadaşı problemini çözmek için kurulmuş olan Spliddit isimli web sitesinde uzun yıllar 2004’teki algoritma kullanılmıştı.)

Algoritmanın İşleyişi

  • Kirayı bölüşecek kişiler kapalı her oda için kapalı zarfta teklif verir. Odalara yapılan teklifler toplam kirayı vermelidir. (Örneğin 3000 liralık bir evdeki iki odaya yapılacak tekliflerin toplamı tam olarak 3000 lira etmelidir.)
  • Zarflar herkesin gözü önünde açılır. Bir odanın kazananı o odaya en yüksek teklifi yapandır.
  • Bir oda için teklifi kazanan kişinin diğer teklifleri geçersizdir.
  • Kazanan tüm teklifler toplanınca tam olarak kiraya denk geliyorsa, herkesin vereceği miktar belirlenmiş demektir.
  • Eğer tekliflerin toplamı kiradan az veya fazla ise, basit orantı işlemleriyle herkes için verilmesi gereken kira belirlenir.

Pizza Dilimi Cevabı

Üç arkadaşın pizza dilimi seçimi açık artırma algoritmasıyla çözülebilir. Üçlünün kapalı zarf teklifleri aşağıdaki gibi olsun:

20190514_170542.jpg

Tek tek pizzalara bakıldığında ilk pizzayı Ali 4 liraya, ikinciyi Steve 4 liraya, üçüncüyü ise Jane 2 liraya kazanmış olur:

Tekliflerin toplamı

4 + 4 + 2 = 10

liradır. Teklif toplamları pizza dilimlerine verilecek 6 liradan fazla olduğu için tekliflerin oranları hesaplanır:

20190514_170507.jpg

Bu durumda Ali ve Steve 4 lira vermeye hazır oldukları pizza dilimlerine 2,4’er liraya, Jane ise 2 lira vermeye hazır olduğu pizza dilimine 1,2 liraya kavuşur. Algoritma sonucunda hem herkes istediği pizza dilimini düşündüklerinden daha ucuza almış olur.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Algoritma #4

Adil Pasta Kesimi

Adil bir şekilde pasta kesmenin bir yolu var mı?

Bunu resmen bir matematik problemi olarak gören ilk kişi Hugo Steinhaus isminde bir matematikçiydi. Steinhaus 1944 yılında bir pastayı iki kişinin nasıl paylaşabileceği üzerine kafa yormuştu.

Ona göre birbirlerinin seçimlerini kıskanmadan iki kişinin pastayı paylaşmasının yolu “biri keser, diğeri seçer” yöntemiydi:

İlk kişi pastayı ikiye böler, ikinciyse iki parçadan istediğini alır. Bu yöntemde ikinci kişi istediği parçayı alabildiği için tercihinden memnundur. İlk kişiyse pastayı eşit olarak iki parçaya ayırdığını düşündüğü için iki parçadan kendisine hangisi kalırsa kalsın memnun olacaktır. Steinhaus’un bu yöntemi bilinen ilk kıskanç olmayan yöntemdi.

Peki üç kişi bir pastayı birbirlerinin seçimlerini kıskanmadan nasıl paylaşabilir?

İnanılmaz ama bu soru ancak 1962’de cevaplanmıştı. Soruyu birbirinden bağımsız olarak çözen J. H. Conway ve J. Selfridge’e göre yöntem şu şekilde ilerler:

Ali, Steve ve Jane

  1. Ali pastayı üç (kendince) eşit parçaya böler.
  2. Steve bu parçaları kontrol eder. Eğer Steve kontrol sonrası bir şey yapmazsa sıra Jane’e geçer.
  3. İlk seçimi Jane, ikinci seçimi Steve, son seçimiyse Ali yapar.

Gelin yöntemi ayrıntılarıyla açıklayalım:

Adım #1: Ali ne yapmalı?

Ali göz kararı bir şekilde pastayı üç eşit (ya da en azından denk) parçaya böler:

Adım #2: Steve ne yapmalı?

Steve bu parçaları kontrol eder. Burada ihtimaller Ali’nin kesiminin değerlendirilmesiyle şekillenir:

  1. Eğer Steve parçalardan en az ikisinin en iyi (yani en büyük) parçalar olduğuna kanaat getirirse bir şey yapmaz ve sıra Jane’e geçer. Steve’e göre böyle bir durumda iki ihtimal vardır:
    a. Parçaların hepsi birbirine eşitse Jane hangisi seçerse seçsin kalan parçaların hepsi Steve’i memnun eder:

    20190502_152944.jpg
    Üç parça da eşitse ikinci seçimi yapacak olan Steve mutlu olacaktır.

    b. Eğer iki parça birbirine eşit ve üçüncü parçadan büyükse, Jane büyük parçalardan birini alsa dahi diğer büyük parça Steve’e kalır ki bu da onu memnun eder.

  2. Parçalardan biri diğer ikisinden büyükse Steve bir şey yapmak zorundadır. Aksi takdirde Jane tek büyük parçayı alır:
    20190502_153002.jpg
    Steve ortadaki parçanın diğer ikisinden daha büyük olduğunu fark eder. Eğer bir şey yapmazsa bu parça Jane’e gidecektir.

    Bu durumda Steve büyük parçayı traşlayarak düzenler ve fazla parçayı bir kenara ayırır. Böylece Steve Jane’e seçmesi için en kötü ihtimalle birbirine eşit iki büyük parça bırakmış olur:

    Steve ortadaki parçayı traşlar ve fazlalığı başka yere koyar. Örnekte orta ve sağ en iyi parçalardır. Jane bu ikisinden birini aldığı takdirde diğeri Steve’e kalacaktır.

Adım #3: Jane ne yapmalı?

Steve memnun olduğuna kanaat getirdikten sonra sıra Jane’e gelir:

  1. Eğer Steve hiçbir şey yapmamışsa üç parça birbirine eşit demektir. Bu durumda ilk Jane seçimini yapar, sonra da Steve. Son parça ise Ali’nindir. Böylece kıskanç olmayan kek kesimi gerçekleşmiş olur.
  2. Eğer Steve’e göre Ali’nin kestiği üç parçadan biri diğer ikisinden büyükse Steve bu büyük parçayı yukarıdaki adımda anlatıldığı gibi düzeltir ve sıra Jane’e öyle gelir. Böyle bir durumda Jane istediği parçayı seçer. Fakat Jane’in seçtiği parça yöntemin geri kalanını etkiler:
    a. Eğer düzenlenmiş kek parçasını Jane seçerse kalan iki parçayı sırasıyla Steve ve Ali alır. Bu durumda ayrılmış olan dördüncü parçayı Steve eşit üç parçaya böler. Bu üç parçayı sırasıyla Jane, Ali ve Steve seçer ve adil paylaştırma sona erer:

    b. Eğer Jane düzenlenmiş kek parçasını almazsa bu parçayı Steve almak zorundadır. Bu durumda ayrılmış olan dördüncü parçayı Jane eşit üç parçaya böler. Bu üç parça sırasıyla Steve, Ali ve Jane tarafından seçilir ve adil paylaştırma sona erer.

Bi’ Göz Atmakta Fayda Var

Buraya kadar olan senaryo kıskançlıktan uzak mıdır?

(Okumadan önce cevap üzerine bir süre kendiniz düşünün.)

*

*

*

Cevaplar

Ali İçin: Evet. Çünkü orijinal keki üç eşit parçaya ayırdığını düşündüğü için hangi parça gelirse gelsin memnun olacaktır. Artan kısım olursa Ali için zaten eşit olduğunu düşündüğü parçaya biraz daha fazla pay gelmiş olacaktır.

Steve İçin: Evet. Çünkü kek parçalarından en az ikisinin en iyi (yani en büyük) olmasını garantilemeden Jane’e sırayı vermez. Eğer parçalardan birinde düzeltme yaptıysa ve bu parçayı Jane aldıysa, artan parçayı üç eşit parçaya bölen Steve olur ki bu da Steve’in herhangi bir artan parça ile memnun olacağı anlamına gelir.

Jane İçin: Evet. Çünkü orijinal parçalardan ilk seçimi yapan o olur: Bu sayede kendinden en iyi parçayı seçebilir. Ayrıca Steve’in üçe böldüğü artan kısımda da ilk seçimi yapacağı için paylaşımdan memnun olacaktır.

M. Serkan Kalaycıoğlu