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

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