Real MATHEMATICS – AlgorIthm #4

Fair Cake Division

Is there a bullet-proof method for cutting a cake fairly?

This became a legitimate problem in mathematics back in 1944. A mathematician named Hugo Steinhaus published a paper for fair cake-cutting. According to him solution is trivial for two people. Method for two people is today commonly known as “one cuts, other picks”:

First person cuts the cake in half (on his/her point of view) and other person gets to pick any piece he/she wants. In this method both of them are happy and envy-free as first person believes the pieces are equal and second person picks the biggest piece on his/her view. Steinhaus’ answer is the first envy-free answer for fair cake division.

What if there are three people? Is there an envy-free method for cutting a cake for three people?

Incredible but answer wasn’t that obvious. Only 18 years after Steinhaus’ work (1962) J. H. Conway and J. Selfridge (independently) found an answer.

Ali, Steve and Jane

General method:

1. Ali cuts the cake into three equal (that he considers equal) pieces.
2. Steve evaluates the pieces. If he decides to do nothing Jane takes the turn.
3. Jane selects any piece she wants. Steve picks as second, Ali gets the last piece.

Obviously things are never this easy. Let’s examine the method in details and show how ingenious it is:

Step #1: What should Ali do?

First step is easy: Ali cuts the cake into three equal pieces. Since he cuts them, he will be pleased to receive any of the pieces.

Step #2: What should Steve do?

Steve checks the pieces. Here, there is more than one possibility depending on how Steve sees Ali’s cuts:

1. If Steve decides that at least two of the pieces are the best ones (best as in biggest) he does nothing and process continues with Jane selecting her piece.
a. In case Steve thinks that all three pieces are equal, whichever Jane selects, he will get the best piece according to him:

b. In case Steve thinks that two of the pieces are equal and best, even if Jane selects one of them, he will get to select the other best piece. He will be happy in either case.

• If Steve thinks one piece is bigger than the other two, he needs to do something. Otherwise Jane would get the biggest piece:

In such situation Steve trimmers the biggest piece which will result in a trimmed piece and a leftover:

This way trimmed piece will be equal to at least one of the two remaining pieces which means at least two (trimmed and one of the other two) of the cake pieces are the best ones. Now Steve is ready to let Jane select her piece.

Step #3: What should Jane do?

Here, Jane is free to choose whichever piece she’d like to:

1. If Steve did nothing, Jane will select any of the pieces. Steve goes after her and Ali will get whatever is left. Everyone will be content with his/her choice.
2. (Steve trimmed a piece.) In such situation Jane is still free to choose. But now her choice determines the rest of the game. There are two possibilities at this state:
a. Jane selects the trimmed piece. Then Steve and Ali will get their pieces in that order. In this situation Steve gets to cut the leftover into 3 equal pieces. Then Jane, Ali and Steve each select a piece of the leftover in that order:

b. Jane selects any of the untrimmed piece. In that case Steve must select the trimmed piece and Jane gets to cut the leftover into 3 equal pieces. Then Steve, Ali and Jane each select a piece of the leftover in that order.

One wonders…

Is this really envy-free?

*

*

*

For Ali: Yes, because Ali cuts the cake in three equal pieces on his view. He will be content with any of the pieces. Also he will not mind getting a part of the leftover.

For Steve: Yes, because Steve decides that there are at least two best pieces and he will be content with any of them. Also he will get to cut the leftover into 3 equal pieces which means he knows that he can get any of the leftover pieces.

For Jane: Yes, because she gets to select first for the original and leftover cake.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Algoritma #4

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:

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

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:

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:
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.

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

Matematik Atölyesi – Oyun #11

Lahana

1967’de M. S. Paterson ile J. H. Conway’ın yarattığı iki kişilik bir oyun olan lahanayı oynamak için kağıt ve kalemden başka bir şeye ihtiyacınız yoktur.

• Oyuna başlarken kağıt üzerine rastgele üç adet nokta koyulur:
• Oyuncular sırayla bir noktadan diğerine (veya bir noktadan yine kendisine) giden bir eğri çizer. Çizilen eğrinin üzerine bir de nokta konur:
• Çizilen eğriler birbirini kesemez.

• Bir noktaya bağlı üç tane eğri varsa, o nokta artık ölüdür: Yani o noktaya başka bir eğri bağlanamaz:
Soldaki resim ihlal içerirken sağdaki resimde A, B ve E noktaları “ölü”dür. Çünkü bu noktaların her biri üç çizgiye sahiptir.
• Son eğriyi çizen oyunu kazanır.

Brüksel Lahanası

Lahananın bir başka versiyonu olan Brüksel Lahanası’nda başlangıçta konulan noktaların ufak çizgileri vardır. Bu noktalar ve üzerinde bulunan çizgiler istenilen sayıda seçilebilir. Örneğin birinde 3, diğerinde 4 çizgi olan iki noktayla oyuna başlayalım:

Brüksel Lahanası’nda da oyuncular sırayla birer eğri çizer (her çizilen eğrinin üzerine yeni bir nokta ve iki küçük çizgi konur). Bu sefer eğriler noktalarda bulunan ufak çizgiler arasındadır:

Yine bir önceki oyunda olduğu gibi çizilen eğriler birbirini kesemez ve yine en son eğriyi çizen oyunu kazanır:

En sağdakinde çizgiler kesiştiği için ihlal vardır.

Euler ve Lahana

Euler ile bu basit görünümlü oyunların ne alakası var diyebilirsiniz. Euler karakteristiğinden daha önceki yazılarımda bahsetmiştim.

Euler der ki:

Bir düzlemde (kağıt üzerinde) V tane nokta ve bu noktalar arasında birbirini kesmeyen E tane çizgi olsun. Bu nokta ve çizgilerin çerçevelediği yüzlerin sayısı da F olsun (tüm kağıdın da bir yüz olduğunu unutmayın). O halde:

V – E + F = 2 olur.

Yani nokta sayısıyla yüz sayısını toplayıp bundan çizgi sayısını çıkarırsan cevap her zaman 2 olur.

Bitmiş bir Brüksel Lahanası oyununu ele alın. Nokta, çizgi ve yüz sayılarını belirleyin:

Euler’in formülüne sayıları yerleştirin:

Euler her defasında haklı çıkacak!

Dört Renk

Yine bitmiş bir Brüksel Lahanası’nı ele alın. Bu sefer dört farklı renkte kaleme ihtiyacınız olacak:

Bitmiş oyun üzerindeki alanları komşu olanlar farklı renkte olacak şekilde boyarsanız dört rengin yeterli olacağını göreceksiniz.

Bi’ Göz Atmakta Fayda Var

1. Lahana oyununu 3 nokta ile en fazla kaç el oynayabilirsiniz?
2. Lahanayı kazanmak için bir strateji bulabilir misiniz?
3. Brüksel lahanasında üçer dikeni olan iki nokta ile en fazla kaç el oyun sürdürülebilir?

M. Serkan Kalaycıoğlu

Real MATHEMATICS – Game #11

Sprouts

Sprouts is a multiplayer game which was created by M. S. Paterson and brilliant J. H. Conway back in 1967. All you need for playing sprouts are just a piece of paper and a pen/pencil.

• Game starts with 3 dots on a paper:
• Players take turns and draw lines from one dot to another (a line can be drawn to the same dot as well). Lines don’t have to be straight and a new dot must be placed on each line:
• Lines can’t cross one another:
• A dot is called “dead” if it has 3 lines coming out of it. In other words any dot can be connected to at most 3 lines:

On right: A, B and E have 3 dots. This means A, B and E are all “dead”.

• Player who draws the last possible line is the winner.

Brussels’ Sprouts

Brussels’ sprouts is a different kind of sprouts game. It is a multiplayer game just like regular sprouts and all it needs are a paper and a pen/pencil as well. But this time game starts with dots that have thorns. Assume that we will start a Brussels’ with two dots with 3 and 4 thorns on them:

Players take turn to draw lines between thorns. When a player draws a line, he/she should mark a new dot that has two thorns on it:

Just like regular sprouts, lines can’t cross in Brussels’ sprouts. And the player who draws the last line wins the game:

Euler and Sprouts

You might wonder how on Earth I get to mention Euler in a game that was created about 200 years after he passed away. I recommend you to check Euler characteristics article.

Euler says:

Let’s imagine that V dots and E lines (which don’t cross one another) are sitting on a plane. If the number of faces on this shape is F (don’t ever forget to count the whole plane as one face), then the equation

V – E + F = 2

will always be satisfied.

Take a finished Brussels’ sprouts game on hand:

Find the numbers of the dots, lines and faces:

Apply Euler’s formula:

Euler will always be right!

Four Colors

Now take any Brussels’ sprouts sheet and color the faces on it. (Neighboring faces have different colors.)

You will see that four different colors will be enough to color any Brussels’ sheet:

One wonders…

1. At most how many turns can there be in a regular sprouts game that starts with 3 dots?
2. Is there a winning strategy for sprouts?
3. Start a Brussels’ sprouts with 3 dots. If each of them has 3 thorns, at most how many turns can there be?

M. Serkan Kalaycıoğlu