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:
    20190429_140440.jpg
  • 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:
    20190429_140912.jpg
  • 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:

20190429_141609.jpg

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:

20190429_142541.jpg

Find the numbers of the dots, lines and faces:

Apply Euler’s formula:

20190429_142635.jpg

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

Real MATHEMATICS – Graphs #6

Bequeath Problem

King Serkan I decides to allocate his lands to his children. Obviously he had set up some ground rules for the allocation:

  • Each child will get at least one land.
  • Same child can’t have adjacent lands.

Problem: At least how many children should Serkan I has so that allocation can be done without a problem?

Map #1

Let’s start from a simple map:

20190423_000256.jpg

In this case Serkan I can have two children:

20190423_000310.jpg

As you can remember from the previous article a map and a graph is irreversible. If we represent lands with dots, and let two dots be connected with a line if they are adjacent, we can show maps as graphs:

20190423_000334.jpg

Let’s add another land to this map:

20190423_000402.jpg

Adding a land on a map is the same thing as adding a dot on a graph:

20190423_000507.jpg

Map #2

Let’s assume there are three lands on a map:

20190423_000523.jpg

We can convert this map into graph as follows:

20190423_000537.jpg

As seen above, three children are needed in order to fulfill Serkan I’s rules:

20190423_000553.jpg

Map #3

Let the third map be the following:

20190423_000627.jpg

According to Serkan I’s rules, we will need four children for such map:

20190423_000642.jpg

Map #3 can be shown as a graph like the following:

20190423_000728.jpg

Map #4

For the final map, let’s assume Serkan I left a map that looks like USA’s map:

480271690e1e0485f71988e273730559

Surprisingly four children are enough in order to allocate the lands on the map of USA:

amarikaaa

What is going on?

Careful readers already noticed that adding a dot that connects the other dots in the second map’s graph gives the graph of the third map. Same thing is true for the first and second maps:

Hence, adding a new dot to the graph means adding a new child.

Q: Is it possible to create a map that requires at least five children?

In other words: Is it possible to add a fifth dot to the graph so that it has connection to all existing four dots? (Ps: There can be no crossing in a graph as our maps are planar.)

Then, all we have to do is to add that fifth dot… Nevertheless I can’t seem to do it. When I add the fifth dot outside of the following graph:

It is impossible to connect 1 and 5 without crossing another line. No matter what I try, I can’t do it:

Four Color Theorem

About 160 years ago Francis Guthrie was thinking about coloring maps:

“Can the areas on any map be colored with at most four colors such that no pair of neighboring areas get the same color?”

Incredibly the answer is yes.

This simple problem was introduced for the first time by Francis Guthrie in 1852. Not until 1976 there was no proof for Guthrie’s conjecture. Only then with the help of computers the conjecture was proved. This proof is crucial for mathematics world as it is known as the mathematical theorem that was proven with the help of computers.

One wonders…

20190423_003916.jpg

Add a fourth dot to the graph you see above and connect that dot to the existing dots. (You are free to place the fourth dot wherever you want on the graph.)

Now check your graph: One of those four dots is trapped inside the lines, isn’t it?

Can you fix that?

Explain how you can/can’t do it.

M. Serkan Kalaycıoğlu