## Real MATHEMATICS – Puzzle #4

Naughty Students

Among all friendships, being classmates has a special part. Inside every classroom, each student has a friend who would cause trouble if they sit adjacent (side to side, front-back and diagonal) to each other. This is why teachers change the sitting-order to find the optimal situation for each classroom.

Steve the teacher and his problem

Teacher Steve realizes in one of his classes that in total 8 students cause trouble during lessons whenever they sit adjacent (from now on I will refer to being adjacent as “being neighbor”).

The Situation

• Neighbor students are the students who sit either side to side, front and back or diagonal to each other.
• If two students cause trouble whenever they are neighbors, there is a <–> sign between their names.
• Deniz <–> Ali <–> Kirk <–> Jane <–> Poseidon <–> Rebecca <–> Lucreita <–> Bran
• Sitting plan for these 8 students is shown in the following:

Steve the teacher doesn’t want to change other students’ sitting plan. Hence his problem becomes as follows:

“How can I find an order for these 8 students so that there won’t be neighbor students who will become naughty?”

Hint: Assign numbers to the students.

I will explain the answer in the next post.

M. Serkan Kalaycıoğlu

## Real MATHEMATICS – Game #8

Judge Seesaw 2.0.1

In the previous post I asked how you can find the 12th box when we don’t know whether it is heavier or lighter than the rest of the boxes.

To start the solution, we will divide the boxes into three groups of 4. But this time I will assign names to these groups and boxes:

In the first try we’ll place the groups A and B to the end of the seesaw. There will be two possible outcomes:

Outcome 1: Seesaw is in balance.

This outcome shows that the boxes of A and B are identical.

Then, we can conclude that oddly-weighted box is among the group C.

In the second try let’s place any three boxes of the group C with any three boxes of the group A. (Why three from A? Since all the boxes of A and B are identical, it doesn’t matter which three boxes I choose among them. I selected three from the group A. I could have selected two boxes from A and one from B as well. It wouldn’t change anything.)

After the second try, we will again left with two possible outcomes:

a. Seesaw is in balance.

It means three boxes of C and A are identical. Then we can conclude that the forth box of C is the oddly-weighted box.

b. Seesaw is tilted.

This concludes that one of the three boxes I choose from C is the oddly-weighted box. In this case the seesaw is either tilted towards C or A which tells us our box is either heavier or lighter than the rest of the boxes.

In other words, after the second try we ended up with the following question: “Two of three boxes have the same weight. If you know whether the odd box is heavier or lighter than the other two, how can you find the odd box?”

This can be solved with exactly one try on the seesaw. Select any two of the three boxes, place them on the seesaw.

If seesaw is in balance, then the third box is the odd one:

In case seesaw is tilted, as we know whether the odd box is heavier or lighter than the others, we can find the box we’ve been looking for:

Outcome 2: Seesaw is tilted.

In this case the box we are looking for is either inside the group A or inside the group B.

Another deduction we can make is that one of these groups is heavier than the other. For the sake of a clearer solution I am going to assume that A is heavier than B. (I could have chosen the other way around; it wouldn’t change anything.)

Before starting the second try I will be swapping a box between A and B. Also I will be replacing the remaining three boxes of B with three boxes of C.

There are three possible outcomes:

a. Seesaw is balanced.

This means that all the boxes sitting on the seesaw are identical. Hence the box we are looking is among the three boxes of group B which we replaced. We can also deduce that oddly-weighted box is lighter than the other boxes since the seesaw is balanced.

At this point all we need to do is to find the lighter one inside three boxes. As we showed in the previous situation, it can be done with comparing any two of those boxes.

b. Seesaw is tilted in the same direction as the first try.

This means that the oddly-weighted box is among the three boxes of A. We can also conclude that this box is heavier than the rest.

Again we have three boxes with one of them heavier than the other two. We can find that box with simply comparing any two of those boxes with the seesaw.

c. Seesaw is tilted in the opposite direction of the first try.

This means that the oddly-weighted box is either one of the boxes which we swapped between A and B. But in this situation we have no clue if the box we are looking for is heavier or lighter.

In order to find our box, we should compare one of those two boxes with any one of the remaining 10 boxes.

If there is a balance on the seesaw, it means our box is the one we didn’t place on the seesaw:

If the seesaw is tilted, then it means our box (in the following cases it is A4) is the one we’ve chosen and placed on the seesaw.

M. Serkan Kalaycıoğlu

## Real MATHEMATICS – Game #7

Judge Seesaw

There are 12 gift boxes on the table. They all have identical sizes and gift wraps.

11 of them weight the same as the 12th box weights different from others.

Goal: Finding the oddly-weighted box.

Prize: 50 million old Turkish liras worth Oreo. (Because Oreo is the most beautiful thing in life.)

Tools: You can use a seesaw to compare the weights of the boxes.

Challenge: You will have to guess the oddly-weighted box in at most 3 tries.

Judge Seesaw 1.0.1

It is the most basic version of the game where it is known if the 12th box is heavier or lighter than other 11 boxes.

At this point give yourself a few minutes and think on a solution when it is known that the 12th box is heavier than the rest.

***

Time is up. Here is the solution:

I assumed that the 12th box is heavier than the rest of the boxes. Then we should divide 12 boxes into three groups of 4.

In the first try we will take any two of those groups of 4 and place them on the ends of the seesaw. There will be exactly two possible outcomes:

Situation A: Seesaw is balanced.

Two groups have equal weights which would mean the oddly-weighted box must be among the third group of 4.

In the second try we will take the third group of 4, divide those two-by-two and place them on the ends of the seesaw.

We will be seeing that the seesaw is tilted to one side. That happens because heavy box sits on the seesaw.

In the third try we’ll be taking the heavier couple from previous measure and place them one-by-one on the ends of the seesaw.

The seesaw will be tilted in favor of the heavier box. Hence we found the oddly-weighted box in exactly three tries.

Situation B: Seesaw is tilted.

This happens because oddly-weighted box is among one of the groups of 4 boxes. Take that group and apply the same methods we did in situation A.

One wonders…

Judge Seesaw 2.0.1

In this version of the game we have no idea whether the 12th box is heavier or lighter than the rest of the boxes.

Even though it seems like a slight change, this game has become much harder compared to the version 1.0.1.

This is why I will give you a little time. I’ll include the answer in the next post.

M. Serkan Kalaycıoğlu

## Real Mathematics – Puzzle #1

Crossing the River

A farmer is walking back home with a wolf, a goat and some lettuce. As he was on his way a river appears in front of him. Luckily for him, he sees an abandoned boat. Though it turned out the boat was not big enough for all of them. Farmer had to choose either one of the wolf, goat or lettuce in each time he crosses the river.

But there was a catch here: If they are left alone wolf would eat the goat and goat would eat the lettuce. What is farmer’s strategy in order to cross this river? (P.s: It is not possible to swim across the river.)

Between these three only wolf and lettuce can be left alone. Then farmer should start the process with carrying the goat to the right side of the river.

Then he should return the left side and picks up either of the wolf or the lettuce. (Let’s assume that he picks the lettuce.) Farmer reaches the right side of the river with the lettuce. Now before he leaves he realizes that lettuce and goat can’t be left alone. So he takes the goat with him to the left side.

Now, lettuce is alone on the right side of the river as farmer, goat and the wolf are all on the left side. At this point farmer should carry the wolf to the right side and leaves it there with the lettuce as lettuce and wolf can be left alone without a problem.

In the end farmer can go back to the left side of the river and takes the goat to the right side. Hence the problem gets solved.

There wouldn’t be a solution for this puzzle if wolf was eating the lettuce. But, in order to understand that we had to check every possible variation. This would have been a waste of time and energy. Thus we haven’t found an actual method for the solution of this puzzle.

River Algorithm

Graph Theory is a relatively new subject of mathematics. In Graph Theory what matters is the placement and the connection; not the shape. In this part of mathematics objects are described with dots and connections with lines. Then wolf, goat and the lettuce can be represented as dots. Only connection between these three is whether they eat one another or not. In the puzzle goat eats lettuce and wolf eats goat. Hence connections (or lines) should be between them.

If dot disappears, then the connections within disappears as well. In the puzzle we can take only one dot at a time. In the first move we choose the goat. This can be shown in graph as follows:

Deleting the goat dot means to delete the lines connected to it. Graph has no line after the first move which is what we want to accomplish and we managed to do it with deleting only 1 dot. This means another thing: In order to solve the puzzle there must be as many spaces as the deleted dots in the boat.

Let me explain this with an example: Assume that we have to take at least n dots away from the graph in order to get rid of all the lines. This means if boat has n empty spaces the puzzle can be solved.

Let’s add a rabbit to this puzzle.

Second River Puzzle

Now farmer has a goat, a wolf, some lettuce and a rabbit. On top of the previous puzzle rabbit eats the lettuce and wolf eats the rabbit.

In the first puzzle we took goat’s dot and saw that there was no line left in the graph. But in the second puzzle none of the four dots is able to extinguish all the lines of the graph.

This is why in order to extinguish all the lines; we must try to remove at least two dots. For instance:

As seen above when we take goat and the rabbit, all the lines inside the graph disappears. Using graphs we found an algorithm and with that algorithm we know that the boat must have at least 2 spaces in order to solve the second puzzle.

One Wonders…

1. Solve the second puzzle.
2. Let’s add carrot, cat and mice to the second puzzle. Goat, rabbit and mice eats the carrot and cat eats the mice. Try to find how big the boat should be and solve the puzzle for that boat.

M. Serkan Kalaycıoğlu

## Real Mathematics: Patterns #3

Problem of Serkanus

All the participants sit down on a round table that has ascending numbers on it. Last person sitting is the winner and claimer of the magnificent banana cake.

Rules:

Game can have as many players as wanted.

When players sit, each and every one of them gets a number between 1 and the #of players.

Elimination always starts from player 1 and goes clockwise.

Every second player gets eliminated. In other words, if it is your turn, you’ll eliminate the person who is after you in clockwise direction.

Game 1: One player.

It means that there is only one player who is the winner naturally.

Winner: 1.

Game 2: Two players.

There are two numbers at the table: 1 and 2. Player 1 starts eliminating the player that is on his/her clockwise direction. This means player 1 eliminates player 2.

Since there is no other player left, player 1 claims victory.

Winner: 1.

Game 3: Three players.

There are 1, 2 and 3 sitting at the table. Game starts with player 1 eliminating player 2. Now it is player 3’s turn.

Player 3 eliminates the player that sits on his/her clockwise direction. That means player 1 is eliminated and player 3 is the last one sitting at the table.

Winner: 3.

Game 4: Four players.

Numbers 1, 2, 3 and 4 are sitting at the table. Player 1 starts the game with eliminating player 2. Now it is player 3’s turn and he/she eliminates player 4 who is sitting on the clockwise direction.

It is clear to see that only player 1 and 3 are left at the table and it is player 1’s turn to make a move. Player 1 eliminates player 3 and claims him/herself as the owner of the cake.

Winner: 1.

Game 5: Five players.

Player 1 eliminates player 2 and player 3 eliminates player 4. After these moves, it is player 5’s turn and he/she eliminates player 1 who is sitting at the clockwise direction.

Finally player 3 and 5 are left alone. Since it is player 3’s turn, player 5 gets eliminated. Hence player 3 wins the game.

Winner: 3.

Game 6: Six players.

Player 1 eliminates 2, 3 eliminates 4 and 5 eliminates 6.

In the second tour there are only 1, 3 and 5 left at the table and it is player 1’s turn.

Player 1 eliminates player 3.

Now it is player 5’s turn and he/she will eliminate player 1 to claim the righteous owner of the cake.

Winner: 5.

Game 7: Seven players.

Player 1 eliminates 2, 3 eliminates 4 and 5 eliminates 6 which gives player 7 right to eliminate.

Second tour at the table starts with Player 7 eliminating player 1 and player 3 eliminating player 5.

It the third tour it is again player 7’s turn and he/she eliminates the only player left: Player 5. That means player 7 wins the game.

Winner: 7.

Game 8: Eight players.

In the first tour player 1 eliminates 2, 3 eliminates 4, 5 eliminates 6 and 7 eliminates 8.

Second tour begins with player 1 and players 3, 5 and 7 are the ones who survived the first tour. Player 1 eliminates 3 and 5 eliminates 7.

Now only player 1 and 5 left at the table and it is player 1’s turn which makes him/her the victor.

Winner: 1.

Game 9: Nine players.

In the first tour player 1 eliminates 2, 3 eliminates 4, 5 eliminates 6 and 7 eliminates 8 which means player 9 will be starting the second tour.

In the second tour player 9 eliminates 1 and 3 eliminates 5. This means it is player 7’s turn.

Player 7 eliminates player 9 which leaves player 3 and player 7 are the survivors. But since it is player 3’s turn, he/she will win the game with eliminating player 7.

Winner: 3.

Game 10: Ten players.

In the first tour player 1 eliminates 2, 3 eliminates 4, 5 eliminates 6, 7 eliminates 8 and 9 eliminates 10. Player 1, 3, 5, 7 and 9 will advance to the second tour.

Second tour starts with player 1 eliminating 3 and player 5 eliminating 7. Now it is player 9’s turn who will eliminate player 1.

Finally, player 5 and 9 are left at the table and player 5 eliminates player 9.

Winner: 5.

Pattern

Let’s make a table and find out which player won in the first ten games.

This table tells us really interesting facts. First of all, you probably realized that there is no chance for an even numbered player to win the game. In fact, they always get eliminated in the first tour. If you are a good observer, you might find two patterns in this table:

First one is the whenever number of players and winner of the game has the same number, in case you add one more player to the game player 1 will win. Here lies the second pattern which is (if you exclude 1 player game) winners of the games will have odd ascending numbers until number of player will be equal to the number of winner. Check after game 3:

Winner of game 4 is player 1.

Winner of game 5 is player 3.

Winner of game 6 is player 5.

Winner of game 7 is player 7. They are equal so winner will be player 1 in the game 8.

If these two patterns are true, then we can write down on paper who will win in the next games even without playing the game. When it is applied it turns out the winner of game 15 is player 15. If our pattern is correct then winner of game 16 must be player 1.

Let’s check it out:

In the first tour players 2, 4, 6, 8, 10, 12, 14 and 16 will get eliminated.

Since it will be player 1’s turn, players 3, 7, 11 and 15 will get eliminated in the second tour.

Now only players survived are 1, 5, 9 and 13. It is player 1’s turn in the third tour as well, so players 5 and 13 get eliminated.

In the forth tour only survivors are 1 and 9 with player 1 has the right to start. Player 9 gets eliminated.

Player 1 claims that he/she is the king of 16 players!

In other words: We have found a pattern that works!

Josephus Problem

This is a famous problem that is named after Flavius Josephus, an important figure in the Jewish history who lived in the 1st century AD.

Story is kind of a myth which was supposedly lived during the Roman-Jewish war. Josephus was trapped in a cave with his 40 soldiers and they were at the mercy of Roman army. Those 41 men had two choices: Surrender or commit suicide. They decided to commit suicide but Josephus his friend thought it was nonsense and therefore he quickly found a solution.

He convinced all men to make a circle. He suggested that when it is his turn; every man should kill the man who is third in the clockwise position. Josephus thought if they could be in the right position, he and his friend would be the last ones survived in the circle.

Question is: Where should Josephus and his friend locate inside the circle of 41 men?

M. Serkan Kalaycıoğlu

## Real Mathematics: Graphs #2

You’ve been sent for scouting a forest nearby your village. You are done with your duty and on your way back home you are bringing a wolf, a goat and some cabbage with you. Wolf would like a piece of goat and goat is looking hostile against the cabbage, but they can’t do anything with your presence. Then you come across with a deep river. Luckily for you, there is a small boat on coast.

The Catch: Boat is so small it allows you to take only either one of wolf, goat or cabbage. Is there any way you can take everything to the other side of the river safely?

Solving Puzzles with Graphs

In the previous article I told you how Euler used a brand new approach to a seemingly insignificant puzzle and how his method became the basis of graph theory. Drawing graphs in certain cases really improve the chances of reaching an answer. Graphs also help us understand why there is not a solution, in case problem has no solution. Graphs are so powerful at times they can even show us what kinds of conditions are needed to solve a problem that has no solution.

In the river problem, let’s use Euler’s methods. You are all on the left side of the river and you have to get across the right side of it. Now assume that left side of the river is assigned as position 1, and right side as position 2.

There are wolf, goat and cabbage. In the puzzle, those three stand on the position 1 which might be shown as a point named 111 (wolf-goat-cabbage on the positions 1-1-1). Ultimate goal of the puzzle is to find a way to get them all to the point 222.

There are eight different positions for the wolf, goat and cabbage: 111, 112, 121, 122, 211, 212, 221 and 222. For instance 112 means wolf is at position 1 (left side of the river), goat is at position 1 (left side of the river) and cabbage is at position 2 (right side of the river).

Drawing the Graph

We assumed that all these 3-digit numbers represent a point. To get from one point to another, we could only change exactly one digit of it, as we are allowed to take exactly one of wolf, goat or cabbage into our boat. Then there are limited ways to go from one point to another. Let’s assume that if you can go from one point to another, then there is a line connecting those two points.

For instance 111 and 112 has a connection as there is exactly one digit that differ those numbers. Although 111 and 212 has no connection as there are more than one digit that differ those numbers.

Finally we found our points and lines and how they could be drawn as a graph. I think Euler would be proud of us.

Our starting point 111 has three options: 112, 121, 211. Our graph looks like following when all relationships between points are shown:

As our ambition is to reach point 222 from the point 111, it is easy to see the ways to the solution in the graph. However we can’t move between points as we’d like to. We can only use paths which satisfy puzzle’s rules: If they are left alone, wolf eats goat and goat eats cabbage.

Solution

The point 111 has three options: 112, 121 and 211. If we select 112 (taking cabbage to the right side) wolf and goat would be alone, so this path is not good for us. The point 211 would mean leaving goat with cabbage which is forbidden as well. Hence there is only one way to select from the point 111: The path to the point 121.

The point 121 has three options: 111, 122 and 221. We can’t go back, so the point 111 is out. We should choose either 122 or 221.

Choosing 122

This would mean that we are taking cabbage to the right side of the river, near the goat. There are again three options: 121, 222 or 112. We can’t go backwards, so the point 121 is out.

222: Choosing this path would give us the answer. But, in order to do that we must leave goat and cabbage alone and go get wolf. Until we are back to the right side of the river, goat would be doing its final chewing. Hence, we can’t choose this path.

112: This is the only real option we can choose.

From 112, there are again three options: 122, 212 and 111. We can’t go backwards, so the points 122 and 111 are out. Path to the point 212 is the only choice.

At the point 212, wolf and cabbage are on the right side of the river and goat is on the left side. Here, we can go to the left side, pick goat with us and reach the point 222. This would give us the solution we were looking for.

Choosing 221

Now go back and choose the path to the point 221. There are again three options from 221: 222, 211 and 121. We can’t choose the point 121 as it would mean going backwards. Going to the point 222 would solve all our problems, but if we try to do that, we would have to leave wolf and goat alone at the position 2. This gives us the option 211.

The point 211 also gives us three options: 111, 221 and 212. Choosing 111 and 221 would mean going backwards. Then we must follow the path to 212. From the point 212, we can directly choose the path to the point 222. And we would again find the solution within the lines of the rules of the puzzle.

Check It Out

Add other animals and vegetables to these three and try to draw the graph. Using the graph, see if you can find a solution to your puzzle.

M. Serkan Kalaycıoğlu

## Real Mathematics: What are the chances?! #1

In 1987, Thomas M. Cover from Stanford University published an article which contained a bizarre result. Cover suggested the following question:

Player A and Player B will get into a competition.

Player A will be writing down distinct numbers on two pieces of papers, while Player B will be choosing one of the papers and will be reading the number written on it. Then Player B will have to decide if the bigger number is on his/her paper, or on the other one.

Naturally, Player B’s chance of finding the bigger number is 50%. In fact knowing one of the numbers has no use for his chance… or not?

Magic of Mathematics

Is there a strategy for Player B to use so that he/she will have more than 50% chance to win the game?

Although it sounds unlikely, there really is a strategy which Player B could use to win the game with a probability that is greater than 50%.

Strategy: Player B thinks of a number T on his/her mind. Every time Player B selects a paper, he/she uses T for comparison.

• If T is greater than the selected number, Player B chooses the other paper.
• If T is smaller than the selected number, Player B chooses the selected paper.

Theory

Let’s assume x and y are the numbers that are written on the papers. (x is greater than y) There are exactly three different scenarios for the game:

1. T is smaller than x and y. In this case Player B has exactly 50% chance of winning the game.
2. T is greater than both x and y. In this case Player B again has 50% chance of winning the game.
3. T is greater than y, less than x. In this case if Player B picks y, since T is greater than y, he/she will be choosing the other paper. And if Player B picks x, since T is less than x, he/she will be choosing the paper he/she picked. In both situations Player B wins the game which gives Player B a 100% chance of winning the game.

An Example

I will try to explain these three scenarios with an example.

Assume T is 80 and x and y are;

1. 120 and 287,
2. 1 and 2,
3. 64 and 15000.

Solutions:

1. Player B picks either 120 or 287. Since both numbers are greater than T (which is 80), Player B sticks with the paper he/she picks. In this case probability of picking 287 is exactly 50%.
2. Player B picks either 1 or 2. Since both numbers are less than T, Player B claims the other paper has the greater number on it. In this case probability of picking 1 is again exactly 50%.
3. Player B picks either 64 or 15000. T is between these numbers. If Player B picks 64, since it is less than T, Player B would pick the other paper. If Player B picks 15000, since it is greater than T, Player B would claim that the paper he/she picked is the greater number. In both cases Player B wins, which gives him/her a probability of 100% for winning the game.

## Real Mathematics: Puzzle #2

There are certain movies I remember from my childhood which are among my favorites of all times. It would be though to make a top-10 list but if I were to make such a list, Die Hard 3 would make the list with ease. Crazy German terrorist Simon Gruber against our heroes John McClane and Zeus Carver whom were performed by Bruce Willis and Samuel Jackson respectively… Now, that is action!

There is a scene from this movie which will be the main topic of this article. In this particular scene, Simon hands out another life-or-death assignment for our heroes. Click here for the scene.

Simon says…

“There is a timed bomb in this briefcase. You have a 3-liter and a 5-liter jug that you can fill from the fountain. In order to stop the timer you must use those jugs and fill exactly 4 liters. It has to be precisely 4 liters because once you fill the jug; you should put it on the briefcase which has a scale.”

Billiard Table

We could use try-and-see method to solve this riddle, but we might run out of time which would mean a sudden death for us. Obviously we don’t want that. To come up with a systematic method we have to set a few ground rules.

Rules

• Let’s assume that vertices represents water amount in liters and lines represents how quantity can change.
• Vertices will have number pairs. First number is for the 5 liter jug, second for the 3 liter jug.
• Both jugs start from the vertex (0,0) as they are empty.

Example: Vertex (1,2) means that there are 1 liter in the 5-litered jug, 2 liters in the 3-litered jug.

According to our rules, we would have the following graph.

Solution with the method

We used equilateral triangles to build the billiard table for a reason. Using a billiard ball in such shaped table, ball would travel according to our rules. And that is making a regular reflection. In other words, ball moves on the table like a light ray reflecting from a mirror.

Ball’s paths are clear. When it starts travelling from the starting point which is (0,0) it could only follow either (0,3) or (5,0) path. Let’s assume we hit the ball into the direction of (0,3). Ball would pass from the vertices (0,1) and (0,2) and reach (0,3) until it makes a regular reflection which is in the direction of the vertices (3,3) or (3,0).

From now on I will refer to 5-liter jug as “jug A”, and 3-liter jug as “jug B”. To start the solution, I choose the direction of the vertex (5,0).  Then let’s follow the direction of the vertex (2,3).

From the vertex (2,3) let’s use the path to the vertex (2,0).

I will hit the ball towards vertex (0,2) and (5,2) respectively.

Final step is to make the reflection into the path of the vertex (4,3). This vertex means jug A has 4 liters of water which was the amount Simon wanted us to achieve.

Solution with words

• Fill jug A.
• Pour it into jug B.
• Empty jug B.
• Pour the 2 liters (which was inside jug A) into jug B.
• Fill jug A completely and pour it on top of what jug B has (at the point jug B has only 1 liter of capacity).
• Jug A has exactly 4 liters of water.

If only our heroes knew the power of vertices and lines, they would have solved this problem in a much shorter time. Although I would have forgotten my name if I was in front of a bomb. So, I congratulate you boys!

Serkan says…

1. Is there a second way to find the 4 liters with our method?
2. Find both ways to get 1 liter of water.
3. If jugs were 6 and 15 liters in capacity, would it be possible to have 5 liters of water? Give your answer with a proof.

M. Serkan Kalaycıoğlu