Tübitak Lise 2. Aşama 1988 Soru 7

[Lokman Gökçe]

İki kişinin bir keki paylaşmasının her iki tarafı da hoşnut eden ve adil bir yöntemi şudur: Biri keki iki parçaya ayırır, diğeri parçalardan birini kendine seçer. Diğer bir deyişle keki $[0,1]$ aralığı gibi düşünürsek, birinci kişi $x_1\in [0,1]$ seçer; ikinci kişi ise $x_1$ ve $1-x_1$ sayılarından birini seçer. (Burada her iki tarafın da "keksever'' olduğu varsayıldığından, ikinci kişinin $x_1$ ve $1-x_1$ sayılarından daha büyük olanını seçeceği ve dolayısıyla birincinin de $x_1 = \dfrac 12$ seçimini yapacağı kolaylıkla görülür.) Üç keksever kişi için benzer bir paylaşma yöntemi bulabilir misiniz?

[geo]

Cake Cutting Problem diye bilinen soru sorulmuş. Literatürde bu konu Fair Division (Adil Paylaşım) olarak geçiyor.
Sorudaki örneğe, Divide and Choose (Böl ve Seç) yöntemi deniyor. Böl ve Seç yöntemi, adil paylaşımın birden fazla çeşidini barındırıyor. Birincisi, Proportional Fair Division (Orantılı Adil Paylaşım) ya da diğer ismiyle Simple Fair Division (Basit Adil Paylaşım). İkincisi, Envy-free (Kıskanılacak bir durumun olmadığı) paylaşım.

Sorudaki örnekte, keki bölen kişi, parçaların eşit olduğunu düşünüyor. Kendisi hangi parçayı alırsa alsın, kekin yarısını aldığını düşünüyor. Diğer parçanın kendisinin alacağı parçadan büyük olmadığını da düşündüğü için bir kıskançlık duymuyor.
İkinci kişi ise, seçtiği parçanın seçmediği parçadan küçük olmadığını düşündüğü için adil bir paylaşım olduğunu düşünüyor.

Üç kişilik durumda ise işler biraz karışıyor. Orantılı paylaşıma göre, bir kişi kekin üçte birini aldığını düşünmeli. Kıskanılacak bir durumun olmadığı paylaşıma göre ise, bir kişi, kendisindekinden daha büyük bir kekin olmadığına ikna olmalı. Açık şekilde, kıskanılacak bir durumun olmadığı paylaşımın aynı zamanda orantılı olduğu görülebilir.

Üç kişilik kek problemi için üç temel yaklaşım var:

• The Lone Divider (Tek Bölücü) Yöntemi: Orantılı paylaşım
• The Last Diminisher (Son Eksiltici) Yöntemi: Orantılı paylaşım
• Selfridge-Conway Yöntemi: Kıskanılacak bir durumun olmadığı paylaşım (hem de orantılı)

Selfridge-Conway Yöntemi ile çözelim.

Ahmet, Burak, Can keki paylaşan çocuklar olsun.

• Ahmet, keki kendisine göre $A,B,C$ gibi $3$ eşit parçaya bölsün.
• Burak, en büyük parçanın $A$, ondan sonraki en büyük parçanın $B$ olduğunu düşünsün.
  
  • Eğer $2$ tane en büyük varsa, Can $3$ parçadan birini seçer. Burak en büyük olduğunu düşündüğünü seçer, Ahmet de son kalan parçayı seçer.
• Burak, $A$ ile $B$ yi yapıştırıp, kendince, $A-B$ parçasını iki eşit parçaya böler. $A$ nın daha büyük olduğunu düşündüğü için, $A$ dan $B$ ile eşit olan parçaya $A1$, geri kalan $A$ parçasına da $A2$ diyelim.
• Can, $A1-B-C$ parçalarından istediğini alır.
• Burak, Can $A1$ i almadıysa, $A1$ i almak zorunda olacak şekilde geri kalan parçalardan birini alır.
• Böylelikle Ahmet, Burak'ın kesmediği parçalardan birini alır.

Buraya kadar, Ahmet, kendi böldüğü parçalardan birini aldığı için, hakkını aldığını düşünüyor. $A2$ parçası da henüz paylaşılmadığı için, kimsenin kendisinden daha fazla almadığından emin. Can da, $A1-B-C$ parçalarından ilk seçimi yapan kendisi olduğu için, en büyüğünü aldığını düşünüyor. Burak da en büyük iki parça olduğunu düşündüğü için ve ikisinden birini aldığı için, o da kimsenin kendisinden büyük parçaya sahip olmadığını düşünüyor. Kıskanılacak bir durum yok, yani. Ama herkesin gözü, Burak'ın böldüğü $A2$ parçasında.

• Burak ile Can'dan, $A1$ parçasını almamış olan, $A2$ parçasını üç eşit parçaya böler.
• Burak ile Can'dan, $A1$ parçasını almış olanı, ilk seçimi yapar.
• Ahmet, ikinci seçimi yapar.
• $A2$ yi bölen son parçayı alır.

Can, $A1+A2=B=C$ olduğunu düşünüyordu. Onun için, $A2$ paylaşılırken, ilk seçimi $A1$ parçasını alanın yapmasına ses etmiyor. Çünkü $A2$ nin tamamını alsaydı bile, $A1+A2$ toplamının kendisinin payından küçük olacağını biliyor. $A2$ yi bölen kişi, ilk turda en büyük parçalardan birini aldığı için, $A2$ yi de üç eşit parçaya böldüğü için ikinci tur sonunda kimsenin kendisinden daha fazla kek almadığından emin. Herkes, kendisinin en büyük parçayı aldığını düşünüyorsa, o zaman kıskanılacak bir durumun olmadığı bir paylaşım yapmış olduk.

Kaynak:

Fair Division-wikipedia
Adil Paylaşım-ekşi sözlük
Fair share-youtube