Posted in Science & Nature

Seven Bridges Of Konigsberg

The city of Königsberg (capital of Prussia, now Kaliningrad, Russia) has the Pregel River running through the middle, with islands at the centre of the river connected by seven bridges. Is it possible to cross all of these bridges while only crossing them only once each?

image

If you try to solve this problem, you soon discover that it is incredibly difficult not to cross the same bridge twice. But it is difficult to tackle this problem in a brute force manner. To calculate all of the permutations in the order of bridges, you use 7! = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5040, meaning that there are 5040 possible arrangements of bridges. Then how can you prove if the problem is solvable or not?

The great mathematician Leonhard Euler, upon being asked to solve the problem, is reported to have said that the problem is impossible to solve on the spot. In 1735, he proved his answer by modelling the seven bridges of Königsberg in a diagram of four dots connected by lines (representing the bridges).

image

By using this model, the problem is converted into a “draw in one stroke” problem, which is also called a Euler walk to honour Euler’s contributions. Euler discovered many properties and laws regarding such problems. If a certain point is the starting point, then the line must first leave the point, then even if it comes back to the point, it must leave again. Ergo, the starting point must have an odd number of lines connected to it. The opposite applies to the ending point, where a line must enter the point, and if it leaves the point it must come back to it. Ergo, the ending point must also have an odd number of lines connected to it. In the case of a Euler walk, the starting and ending points are identical, so the number of lines is the sum of two odd numbers, making it an even number. Thus, to find out whether a picture can be drawn using one line, use the following laws:

  1. If there are no points of odd degree (odd number of lines), the starting and ending points are identical.
  2. If there are two points of odd degree, the starting and ending points are different.
  3. If there are one of more than two points of odd degree, it is impossible to draw using one stroke.

Thus, a Euler walk is only possible if there are 0 or 2 points of odd degree. Looking at the seven bridges of Königsberg problem, we can see that A is connected to 5 lines and B, C and D are connected to 3 lines each. As there are four points of odd degree, we have thus proved that it is impossible to draw a path that crosses all the bridges while not crossing any bridge more than once.

image

Posted in Science & Nature

Rock-Paper-Scissors

Rock-paper-scissors is a game with a long history. The earliest example of the game is a Chinese game called huoquan, which follows a cyclic rule where the frog eats the slug, the slug dissolves the snake and the snake eats the frog. The reason why rock-paper-scissors has been saved throughout history is because of the uncertainty it contains. Any hand you choose, the chance of winning is the same. Ergo, there is no single best choice and there is no move that will always win. But this is still a game played by people. It is not a game played by emotionless machines, meaning that you can use human psychology, the surfacing of emotion and specific signs and movements to help deduce your opponent’s hand. Mentalist Derren Brown can read tiny flickering of muscles in the opponent and microexpressions to pull off his “undefeatable rock-paper-scissors trick”, but this is near impossible for a normal person to try. However, you can use the following strategies to improve your odds.

  1. Use paper on a beginner: Statistically, people prefer using rock. Males especially have a strong tendency to play rock.
  2. Use scissors on an experienced player: People who know the first trick can be defeated by going one step further.
  3. Use a hand that loses to the hand your opponent played: This uses the psychology of the opponent wanting to mix up hands and wanting to beat the hand you last played (which is the same as theirs as you drew).
  4. Say what you will play and play that hand: In a competitive situation like rock-paper-scissors, people tend not to trust others. Thus, if you say you will play a certain hand, they will think is a trap and not play the hand that defeats that hand. For example, if you said you will play scissors, the opponent will play paper or scissors and you will either win or draw.
  5. Do not give the opponent a chance to think: People have a subconscious tendency to play a hand that beats the hand that they played before. Without time to think, the subconscious takes action meaning that you can predict their move. If you do the same as strategy 3 and play a hand that loses against the opponent’s previous hand, you will win.
  6. Suggest a certain hand: This is a form of hypnosis where you suggest something to the opponent’s subconscious. To use this trick, pretend to go over the rules by saying “rock, paper, scissors” then play a certain hand. The opponent will likely play the hand that the subconscious last saw.
  7. If you keep drawing, use paper: This is the same as strategy 1.

Unfortunately, rock-paper-scissors has an equal probability of a win and a draw, meaning draws are rather common. Thus, a computer engineer called Samuel Kass devised a game where two additional hands are added: rock-paper-scissors-lizard-Spock. Lizard is played by making your hand into the shape of an animal’s head, while Spock is played using the Vulcan Salute from the science fiction show Star Trek, where you make a V-shape with two fingers on each side. The rules are as follows.

Scissors cut paper. Paper covers rock. Rock crushes lizard. Lizard poisons Spock. Spock smashes scissors. Scissors decapitate lizard. Lizard eats paper. Paper disproves Spock. Spock vaporizes rock. Rock crushes scissors.

As each hand has two ways of winning, the odds of winning is 10/25, or 2/5 and the odds of drawing is 5/25, or 1/5. As you can see, you have double the chance of winning compared to drawing, making the game much faster to play than the original game.