algorithm

Real Mathematics – Algorithm #7

How to fail your math test algorithm (H.T.F.Y.M.T.A.)

The late 90s…

At last, there is a computer at home. Now a new battle emerged between Steve and his brothers: “whose turn it is for the computer?”. Thanks to his high grades at school, Steve won this battle easily. After his victory, Steve started to crush zombies in Carmageddon, won the Champions League in Fifa 98, and did such things in Duke Nukem which I can only tell you face to face over a cup of latte.

Steve’s computer game madness went berserk after he met with a football simulation game called Championship Manager. On top of all these games, at least a few days a week, Steve continued to play football&basketball with his friends. A disaster was waiting for him at the end of this road. How didn’t he foresee this?! He was about to fail all his tests in school!

The first warning was the math test. There was less than a day left for the test. Steve should have studied, but he developed some habits since he had a computer. Now, instead of studying, he had a various number of chances to waste time:

1.Staying at home

When Steve decided to stay home, he would get stuck to his computer. Anyone can guess that he was not using his pc for his school. He was just playing one of the following games:
a. Fifa
b. Carmageddon
c. Championship Manager

2.Going out

Whenever Steve went out, he was not going to the library to study:

a. Chase any ball (football or basketball)
b. Behave like a bum with your friends (a.k.a. meet with your friends and do absolutely nothing productive)

Graph of H.T.F.Y.M.T.A.

In the previous posts, I mentioned what graphs are and how they can be useful in certain situations. In Steve’s situation, using graphs can be very helpful to understand what is going on. Since Steve chooses not to study for his math test, his decisions will lead him to fail the test:

What does the graph tell us?

In the graph above, lines represent Steve’s choices, and dots represent at what state he is in after his choices. The graph tells us two certain things: Steve decides not to study and eventually he fails the math test.

This is why the lines that show Steve’s choices have directions.

During making choices, some steps cannot be skipped. For example, in order to play Fifa, Steve first should sit beside his computer, and to do that, he first should decide to stay home.

Let’s assume that Steve’s choices are like the following:

Stay home -> Turn on the pc -> Play Fifa.

In such a situation, since Steve has limited time before the test, he cannot play Fifa and then return and study for the test. After his decisions, there is no other country than “fail-town”.

Another thing the graph tells us is that Steve cannot go back after making a decision. Mathematicians call these kinds of graphs as “acyclic/chain digraphs”.

Some Information

Acyclic Digraphs

An acyclic digraph does not have a cycle. In other words, once you start moving on an acyclic digraph, you can never go back to the point you previously were at.

An acyclic (finite) digraph has at least one “source” and at least one “sink”.

A point is called “source” if it has no lines leading into it from any other point(s). A point is called “sink” if there are no edges from that point to any other point(s). In the graph of Steve, “don’t study” is the source, and “Result: F for fail” is the sink.

One wonders…

We all use acyclic digraphs during our daily lives. To show an example, I will use Steve’s life once again.

Every school day, Steve takes a shower as soon as he wakes up and gets ready for school. His steps are more or less like the following:

Wake up

Get into the shower

Brush teeth after shower

Get dressed

(Steve’s school uniform consists of pants, shirt, tie, and a vest.)

Q: Draw the graph that shows the way Steve gets ready for school.

Ps. After the shower, Steve must complete his tasks in the right direction. For example, he cannot put on his boxer before pants, can he?!

M. Serkan Kalaycıoğlu

Real Mathematics – Algorithm #6

The year 2600…

Finally, we discovered a planet where we can live besides Earth. Scientists named this planet as T-489. The living conditions in T-489 seems very much like the Earth’s. Satellite views show that there is water on this planet. And scientists discovered that the atmosphere on this planet is almost the same as Earth’s atmosphere.

Space agencies of the world’s biggest countries gathered a team to discover T-489. According to the plan, the first team that lands on T-489 will secure the landing point and build a headquarter. This point is set beforehand with the use of the satellite photos.

After the completion of the headquarters, three separate teams will be sent to T-489 to discover certain points on the planet that was set beforehand. These teams will be searching for the possible existence of life forms as well as testing the life conditions on each location.

The map: Headquarters is at the yellow point. Other points must be discovered by the teams. In an emergency, teams can use the roads and return to the headquarters.

The headquarter of T-489 should develop a map for those three teams which will be scouting the planet. This map is crucial since it will show how those teams should travel on the planet, and it will also explain how a team can return to the headquarters in case of an emergency.

In certain situations such as not knowing where a team is at a given time, headquarters must add an algorithm to the map. This way, in an emergency, any team can use this algorithm and return to the headquarters safely.

Road Coloring Problem

In 1970, Roy Adler suggested the road coloring problem. After almost 40 years, an Israeli mathematician called Trahtman solved this problem.

Yellow point the headquarters. Select a point and use the roads that in this order three times: blue-red-red. You will always end up at the yellow point.

Trahtman thought of the map as a graph shown above; each road had a direction and a distinct color. Trahtman created these directions and colors such that, following a certain algorithm, your travel would always end up on a specific point. In this example, the algorithm is following blue-red-red roads three times and always ending up at the yellow point. You can try at any point and see by yourself.

Chaos on T-489

You must develop a map for the teams that will be scouting the planet. Headquarters and the locations to visit are shown as follows:

M is the headquarters. A, B and C are the points to be discovered by the teams.

You should prepare for the worst possible scenario. If the connection breaks between the headquarters and the scouting teams, and if those teams can’t access to the map, your algorithm might save their lives.

The idea is: Place a sign on the entry of each point. These signs will have only two pieces of information: The color and the direction of the roads. (Why don’t you just hang the map on these signs? Because you are not sure if there is an alien life form on the planet. And in case they exist, such maps might put the headquarters and the whole mission at danger.)

Let’s say you created a map as follows:

Such a map would have an algorithm like this: Follow red-blue twice, and you will always return to the headquarters.

One wonders…

Create a map and an algorithm that will let you arrive at the point M in each time.

Let’s say that there is one more point added to the discovery. Create a map and an algorithm such that, whenever you use the algorithm you will end up at the headquarters.

(Try to use the least number of roads on your map.)

M. Serkan Kalaycıoğlu

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:

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

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

One can label 1-2 side with either of 1 or 2.
One can label 1-3 side with either of 1 or 3.
One can label 2-3 side with either of 2 or 3.
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 20^th 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:

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:

The person will end up inside a 1-2-3 triangle:
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:

Pizza 1: Four cheese.

Pizza 2: Chicken.

Pizza 3: Pineapple.

Three friends could share the slices in six possible ways:

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:

Ali’s first choice is four cheese. If he can’t get that, his second and third choices are chicken and pineapple in order.
Steve’s first choice is chicken. His second and third choices are pineapple and four cheese in order.
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:

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:

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

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:

Ali cuts the cake into three equal (that he considers equal) pieces.
Steve evaluates the pieces. If he decides to do nothing Jane takes the turn.
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:

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:

Steve will select his piece as second and he will be pleased to get whichever piece as he thinks they are all equal in sizes.

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:
If Steve does nothing here, Jane will get the middle piece for sure.

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:

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.
(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?

(Give yourself some time to think before you read the answer.)

Answers

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

Real MATHEMATICS – LIfe vs. Maths #7

Game of H&G

I selected this name for the game as it reminds me of the story of Hansel and Gretel. (If you haven’t already, pretty please with sugar on top, read it!)

In H&G there is only one goal: Finding the shortest path. Though this game is not a board game; you have got to participate physically. You can find the answer if and only if you analyze your experience.

I have to mention it now: We learned this game from bugs, ants in particular. I will get back to that inside the article.

What is H&G? How can you play it?

Players walk between two places.
Start and finish are the same locations for all players.
There is more than one path for the walk.
Goal is to find the shortest one among those paths.
During the game it is forbidden to use any technological device. Yes, including watches and phones.
Only tool allowed is a pen.
Each player draws a line every time he/she hits the starting and finishing ends of the path.
In order to maintain same (or at least similar) speed for all players, it is forbidden to run.

Game #1

Assume that there are two paths for H&G as follows:

In the beginning players on paths A and B walk the same distance. But as walks progress players using the path A arrives to the finishing point way before than the players on path B:

When the players on path B arrive to the finishing point, they see a mark that is left from the players who use path A. This means that the path A is shorter than the path B. Most of the players from B would prefer path A for return. Some of them (stubborn ones) would follow B and see that they were behind of everyone else.

After some time everyone chooses the path A.

Game #2

Let’s say that we add obstacle on the path A:

After a decent amount of time some of the players will try the path B in order to see if it is the shortest path now:

There is a small but significant difference between B and A.

Careful players will realize that the numbers of lines on path B are increasing faster than the path A which would only mean that path B had become the shortest path.

In time all of the players will realize the fact that path B became the shortest path after the obstacle.

Game #3

Let’s add a third path; we’ll call it path C, to the existing game:

At least one player will be curious and try the path C. Just like the previous games, within time players will realize that the lines from path C increase faster than the other two. Hence players slowly understand that the path C is the shortest one among those three.

Best H&G Players: Ants

In the beginning I mentioned that ants taught us how to find the shortest paths. Back in 1992 a scientist named Marco Dorigo was researching the behaviors of ants. Dorigo soon discovered that ants choose particular paths from their nests to the food supplies.

Assume the map of a nest and a food supply looks like the following:

And assume that ants start using the following path:

Pheromone: A chemical secreted by an animal that shapes its social behavior. For instance ants leave this chemical with their footprints which can be traced by other ants.

Ants are in the search of pheromone when they decide their paths between their nest and food supply. If there are more ants on a path, there will be more pheromone. This will cause more ants to use that particular path. Here, pheromones are just like our pen marks:

Let’s add an obstacle to the path:

At first some of the ants will use the path I as others use the path II:

Since path I is shorter than the path II, after some time there will be more pheromone on path I. This is why ants will abondone path II will choose to use path I in the long run:

Ant Colony Optimization Algorithm (ACOA)

Modern people are impatient: They need to run their things in the fastest way, in the shortest time. Ant Colony Optimization Algorithms help people a lot for this cause. And this algorithm’s logic comes from the method ants use in order to find the shortest path.

Quicktron-Alibaba-warehouse — A warehouse of Alibaba where robots share a workspace.

For instance ACOA is crucial for robotic moves. Robots imitate ants when they learn how to move from one place to another. If there are a decent number of robots in a workspace, ACOA helps robots to avoid collisions.

M. Serkan Kalaycıoğlu

Real Mathematics – What are the chances?! #4

Coffee of Serkan

Certain days of the week (okay; at least six days a week) I visit a specific coffee shop. Almost all the baristas know what I drink because of my frequent visits… Or do they?

My preferences change every six months. In the period of October-March, I only drink either latte or filter coffee, while in the period of April-September I prefer iced latte or berry.

October-March: In case I drink latte today, there are 80% of chances that I will be drinking latte in the next day. If I drink filter coffee today, chances of me drinking filter coffee tomorrow are 60%.

April-September: If I drink iced latte today, tomorrow I will be drinking iced latte with %80 of probability. For berry that probability is 90%.

20190205_195230 — Diagram of my coffee selections in October-March period.

Question: If I drank filter coffee this morning, what are the chances that I will drink a latte 2 days later? (We are in February.)

This question resides one of the most crucial findings of mathematics with itself: Markov Chain.

20190205_194842 — A Markov Chain example. I will be explaining what it is in details inside the article.

It is clear to see that there are two different possibilities to drink latte two days from now. Sum of their probabilities will give us our answer:

Probability of drinking filter coffee (0,6) the next day, and latte (0,4) two days later: 0,6*0,4 = 0,24.

Probability of drinking latter (0,4) the next day, and again latte (0,8) two days later: 0,4*0,8 = 0,32.

Probability of drinking latte two days from now: 0,24 + 0,32 = 0,56.

It means the chance is 56%.

One wonders…

Does it matter which day of February it is today?
Would it change the answer if you learn that I drank filter coffee yesterday? Please elaborate your answer.
If I drink iced latte on June 11th, what is the probability of me drinking berry on June 14th?

Driverless Cars

In case you make a simple web search you will see that there are thousands of pages of articles that question where flying cars are. A few generations including mine have been dreaming about flying cars whenever we were just kids. “Back to the Future” was one of the main reasons why we had such dreams. And it is not like we expect time travel. We just want flying cars!

It is 2019 and there are still no flying cars around. Technology developed as much as making driverless cars only. (Only?!)

Decision making systems are among the key technologies needed for building driverless cars. Because a self-driving car will make hundreds of decisions even if it travels short distances.

Gist of decision making systems is the Markov Chain I mentioned in the Serkan’s Coffee. A concept known as Markov Decision Process is the powerful tool that is being used for driverless cars.

Markov Decision Process (MDP): It is a mathematically formulation for decision and control problems with uncertain behavior.

Memory-less Probability

Markov Chain: If there is Markov Chain inside an event or system, future of that system depends only at the current state of the system; not to its past. And it is possible to predict the future of that system.

One of the examples of Markov Chain is Drunkard’s Walk. Reminder: A drunkard makes random decisions while he/she is trying to find his/her home. Assume that the drunkard had made these moves:

Drunkard’s next move will not depend on the previous moves he/she had made. This only depends on his/her current state and probabilities of the possible moves.

rand2 — If drunkard will move from the point F, there are four possibilities and none of them depend on previous steps the drunkard took.

It goes the same for driverless cars: Decisions will not depend on the previous ones. For example if a driverless car is heading towards traffic lights its decision will depend on the color of the traffic light; not the left turn it made 200 meters behind.

Markov Chain was found more than 100 years ago and it is being used in economy, meteorology, biology, game theory and even modern technologies like driverless cars and voice recognition systems.

Mathematician Family

The person who gave Markov Chain its name is a Russian mathematician called Andrei Markov. His little brother, Vladimir Markov, was also internationally recognized mathematician. Vladimir died because of tuberculosis at the age of 25. Andrei’s son Andrei Markov Jr. was also a mathematician.

Politics and Andrei

Andrei Markov was involved with politics too. He was not in favor of Romanov dynasty which ruled Russia between 1613 and 1917. He showed his opposition with not participating in the 300^th year celebration of Romanov dynasty in 1913. Instead he celebrated 200^th year anniversary of the Law of Large Numbers! (I’ll get back to Law of Large Numbers later.)

M. Serkan Kalaycıoğlu

Real Mathematics – Geometry #16

Smell of a Cake

I smell something wonderful. I beam myself up to the kitchen to investigate the source of this smell. I find it: My mother’s chocolate-chipped cake. As I leaned towards the cake, someone grabs my arm: Mom caught me…

I use the emotional card. She doesn’t buy it anymore. My opponent is experienced; my opponent is winning the battle!

As I was thinking of giving up, she offers me a deal. If I can cut three equal pieces out of this cake, one of the pieces will be mine.

Mom’s conditions:

Only instrument of measurement allowed for the cut is a compass.
Goal is to cut three pieces that have the same area. Size of the pieces is up to my cutting skills.
While making the cut, small differences (as if one area is 3,04 and other is 3,09) will be ignored by the mother.
Most important condition: Pieces must be in the shape of a ring.
You only have one chance for cutting. There is no turning back after the knife touches the cake.

Art of Cutting Cakes

I tried to find a method on paper because I satisfy all the conditions for the cut.

First I drew a circle that has center O:

Then I created a chord which is as long as the radius of the circle:

I placed the chord on random places inside the circle and marked chord’s midpoints:

I chose any of those marked points and drew a new circle that has center O:

Then I followed the same procedure inside the new circle:

And finally I did the same things for the third time:

Areas which I colored with pens are equal to each other:

20190129_224139 — Radius of the biggest circle=5 cm.
Radius of the second circle=4,34 cm.
Radius of the third circle=3,56 cm.
Radius of the forth (smallest) circle=2,55 cm.

For those who wonder the areas, you could calculate and see the approximate results.

One wonders…

I found out that it is possible to cut equal areas that are ring-shaped with using only a compass as mother asks.

Now think: How long the chord should be in order to cut the biggest possible piece?

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

The Answer

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…

Solve the second puzzle.
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 – Game #5

Me versus You

I am going to play a game against you. Yes, I am talking to you, my beloved reader. I promise you that I will personally hand it to you whatever you win at the end of the game.

Rules:

You will start the game from top-left box. You will be making mini-runs. In other words you will take as many steps as I tell you to.
Each time you can take a step towards one of these four directions: Up, down, left and right.
In case you take a step from 1000-Euro box, you can either go right to the 1000-dollar box or down to the Iphone-box. You can’t go from 1000-Euro box to the Starbucks-coffee box with one step as going diagonal is not allowed.
As long as you follow the second rule you can move freely. It is allowed to visit the same box more than once. Also you can go backwards too.
You should start your next step wherever you stopped in the previous run.
After every run I will select a box or two and eliminate them from the game. In case I eliminate a box where you are currently sitting, you will be declared as winners.
I repeat: Your steps should be either of these directions: up-down-right-left.

We’ll start whenever you are ready. Good luck.

Game

1.You will be moving inside these 9 boxes starting from the top-left which is the 1000-Euro box. Take 5 steps.

2. I know that you didn’t stop at the 1000-Euro box. So I am eliminating it. Now, wherever you stopped in the previous run, start taking 7 steps. Did you do it? Okay, you can go to the next.

3. After those steps I am 100% certain that you didn’t stop at the 1000-dollar box. Thus I am eliminating it. Now continue the game with taking 11 more steps.

4. This time I will make a bold decision and eliminate two boxes: Left-bottom corner (a bag of money box) and car key box. You are sitting either one of the following five boxes. Now take 5 more steps.

5. I know that you are not standing on the Iphone box. I also know that you are not on the 100-dollar box. After eliminating them, take 1 last step from wherever you are standing.

Result: Now I can eliminate Starbucks coffee and 500-dollar boxes as you are standing on the zero box. I am afraid this is what you won: A big, fat zero.

One wonders…

You can play this game from top over and over again. In the end, you will get the same result. How is that possible? Why am I this confident?

M. Serkan Kalaycıoğlu