Real MATHEMATICS – Game #12

Triangle Invasion

Invasion is a multiplayer game which needs only a pencil and a pen. To start the game one should draw a big triangle on a paper whilst assigning the corners with 1-2-3:

20190530_145646.jpg

Then the big triangle should be triangulated (without any rules):

20190531_125538.jpg

Once the construction is over, we can start labeling the triangle corners with the direction of the following rules:

  1. One can label 1-2 side with either of 1 or 2.
  2. One can label 1-3 side with either of 1 or 3.
  3. One can label 2-3 side with either of 2 or 3.
  4. One can label the inside of the original triangle with any of 1, 2 or 3.

Progress of the Game

  • Assign the corners according to the rules.
  • In order to invade a triangle, player must assign the final unattached corner of that specific triangle.
  • Goal is to avoid invading a triangle that has corners 1-2-3. Winner is the player who invaded least number of such triangles.

Sperner’s Triangle

Idea of the invasion game comes from the Sperner’s triangle which is discovered by Emanuel Sperner in the 20th century. Triangulated shape in the invasion game is an example of Sperner’s triangle.

After labeling the corners a Sperner triangle will always give a small triangle that has corners 1-2-3:

20190531_125917.jpg

Actually, Sperner’s triangle always has odd-numbered 1-2-3 triangles.

This is why invasion game never ends with draw.

Dead End

Sperner’s triangle can be used to construct many games. For example, let’s say in a Sperner’s triangle all the sides of the little triangles that are connected between 1 and 2 are doors. And all the other sides are walls:

If one tries to walk through these doors, that person will end up in two situations:

  1. The person will end up inside a 1-2-3 triangle:
  2. The person will find him/herself outside of the triangle:

    M. Serkan Kalaycıoğlu

Matematik Atölyesi – Oyun #12

Üçgen İstilası

İki kişilik bir oyun olan üçgen istilasını oynamak için öncelikle bir üçgen çizin ve bu üçgenin köşelerine farklı isimler verin (1-2-3 gibi):

20190530_145646.jpg

Daha sonra büyük üçgenin içine aşağıdaki gibi küçük üçgenler çizin:

20190531_125538.jpg

(Küçük üçgen sayısı istenildiği kadar artırılabilir.)

Üçgende köşeleri aşağıdaki kurallara uyarak adlandırın:

a. 1-2 kenarında bulunan köşeler 1 veya 2 olabilir.

b. 1-3 kenarında bulunan köşeler 1 veya 3 olabilir.

c. 2-3 kenarında bulunan köşeler 2 veya 3 olabilir.

d. Büyük üçgenin içerisinde kalan köşeler 1, 2 veya 3’ten herhangi biri olabilir.

Oyunun İşleyişi

  • Yukarı kuralları izleyerek sırayla köşeler adlandırılır.
  • Oyuncular son köşesini adlandırdıkları üçgenleri istila etmiş sayılır.
  • Amaç 1-2-3 üçgeni yapmamaktır. En az 1-2-3 üçgeni istila etmiş olan kişi oyunu kazanır.

Sperner’in Üçgeni

Üçgen istilası oyunu aslen Sperner üçgeninden gelir. Emanuel Sperner’in bulduğu Sperner üçgeni, çok basit kuralları olmasına rağmen şaşırtıcı bir sonucu içerisinde barındırır. Sperner üçgeni aynı üçgen istilasında olduğu gibi büyük bir üçgenin içine küçüklerinin çizilmesi ve bunların köşelerinin adlandırılmasıyla elde edilir.

Kurallara göre köşeler etiketlendiğinde muhakkak köşeleri 1-2-3 olan bir üçgen bulunur:

20190531_125917.jpg
Örnekte üç tane 1-2-3 üçgeni vardır.

Hatta Sperner bu kurallar çerçevesinde her zaman tek sayıda 1-2-3 üçgenleri olacağını söyler.

Bu yüzden de üçgen istilası hiçbir zaman beraber bitmez.

Çıkmaz Sokak

Sperner üçgeninde 1 ve 2 arasında kalan kenarlar kapı, kalan tüm kenarlar ise duvar olsun. Bir 1-2 kapısından başlanan yürüyüşte karşılaşılan tüm kapılar kullanılmak zorundadır:

Bu durumda üçgenin dışından başlayan bir yürüyüş iki şekilde bitebilir:

  1. Büyük üçgenin içinde bulunan bir 1-2-3 üçgeninde:

    Sol kenarda üç tane 1-2 kapısından başlanan yürüyüşlerin hepsi 1-2-3 üçgenlerinde bitmiştir.

  2. Büyük üçgenin dışında:

    Sol üstteki kapıdan başlayan yürüyüş üçgenin dışında bitmiştir.

M. Serkan Kalaycıoğlu

Real MATHEMATICS – AlgorIthm #5

Optimum Pizza Slice

Three friends will be sharing three slices of pizza.

Pizza Slices:

68591

Pizza 1: Four cheese.

20665-white-chicken-pizza-600X600

Pizza 2: Chicken.

pineapple pizza

Pizza 3: Pineapple.

Three friends could share the slices in six possible ways:

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

Eventually answer is one of those possibilities.

How much do you want it?

Choosing a slice of pizza seems like a very basic procedure. Though, there are many factors behind this simple decision. First of all finance is involved. And obviously “preferences” is an important factor: Not everybody has the same taste for food.

Let’s add these factors to our pizza slice situation. I will assume that 6 dollars is paid in total for the pizza slices, and three friends Ali, Steve and Jane have preferences as follows:

  1. Ali’s first choice is four cheese. If he can’t get that, his second and third choices are chicken and pineapple in order.
  2. Steve’s first choice is chicken. His second and third choices are pineapple and four cheese in order.
  3. Jane’s first choice is also chicken. Her second and third choices are four cheese and pineapple respectively.

In such situation, how can these friends decide fairly who gets which slice for how much?

Rental Harmony Problem

Two (or more) friends decide to rent an apartment. Rooms of the apartment are different in sizes and in some other factors (getting sunlight, having its own bathroom and such). For years mathematicians showed great interest towards the problematic of this situation: How can the rent and rooms be divided?

In 2004, three Turkish scientists Atila Abdulkadiroglu, Tayfun Sönmez and Utku Ünver published a paper that had a solution for the rental harmony problem. This paper shows an ingenious auction algorithm for the solution. (In fact, a famous website that is created to solve rental harmony problems named Spliddit had used this algorithm for almost a decade.)

The Algorithm

  • Roommates write their offers for every room in a closed envelope. For each roommate, total of the offers must be equal to the total rent of the apartment. (For instance, if the rent is 3000 dollars and total of the offers for each person must be equal to 3000 dollars.)
  • Envelopes are opened in front of everyone. A room goes to its highest bidder.
  • In the end, all the winner bids are added together. If it is equal to the rent, then winning bids are the amounts that are going to be paid. If it is exceeds or falls under the total rent, each offer gets to be corrected proportionally.

Answer to the Pizza Slices

We can use the auction algorithm in order to find a solution to the pizza slices problem. Assume that we have offers from Ali, Steve and Jane as follows:

20190514_170542.jpg

Highest bids:

For the pizza 1 is Ali with 4 dollars.

For the pizza 2 is Steve with 4 dollars.

For the pizza 3 is Jane with 2 dollars.

Total of the winning bids is

4 + 4 + 2 = 10

which is higher than 6 dollars. Hence we have to correct the amounts that need to be paid for each of the friends:

20190514_170425.jpg

In conclusion Steve and Ali would pay 2,4 dollars which is less than their offers. Jane would pay 1,2 dollars and it is also less than her offer. Auction algorithm helped these friends to select their pizza slices. The algorithm also helped them to pay less than what they were willing to. Hence, everyone is happy and envy-free with the conclusion.

M. Serkan Kalaycıoğlu

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