Close the Loop

Alex and Bob are playing a game. They are taking turns drawing arrows over the segments of an infinite grid. Alex wins if he manages to create a closed loop, Bob wins if Alex does not win within the first 1000 moves. Who has a winning strategy if:

a) Alex starts first (easy)
b) Bob starts first (hard)

Remark: The loop can include arrows drawn both by Alex and Bob.

In both cases, Bob wins. An easy strategy for part a) is the following:

Every time Alex draws an arrow, Bob draws an arrow in such a way, that the two arrows form an L-shaped piece and either point towards or away from each other. Since every closed loop must contain a bottom left corner, Alex cannot win.

For part b), Bob should use a modification of his strategy in part a). First, he draws a horizontal arrow. Then, he splits the remaining edges into pairs, as shown on the image below. If Alex draws one arrow on the grid, then Bob draws its paired arrow, such that the two arrows point either towards or away from each other. The only place where a loop can have a bottom left corner is where Bob drew the first arrow. However, if a loop has a bottom left corner in this positio, then it must have at least one more bottom left corner, which is impossible. 

One to One Hundred

99 unique numbers between 1 and 100 are listed one by one, with 5 seconds pause between every two consecutive numbers. If you are not allowed to take any notes, what is the best way to figure out which is the missing number?

Keep up adding the given numbers and remember only the last two digits of the sum. In the end, if the result is less than 50, subtract it from 50. If the result is larger than 50, subtract it from 150. This method works because the sum of all numbers from 1 to 100 is 5050, so if you know the sum of all the listed numbers, you will know the missing number as well.

Handshakes at a Party

100 guests go to a party and some of them shake hands with each other. Show that there are two guests who handshake the same number of people.

Each of the people at the party has shaken hands between 0 and 99 times. However, if someone has shaken hands 0 times (with nobody), it is impossible that another one has shaken hands 99 times (with everybody). Therefore there are at most 98 different options for the number of handshakes at the party, and thus two of the guests have shaken hands the same number of times.

The Twelve Matchsticks

With 12 matches you can easily create a shape with area 9 and a shape with area 5, as shown on the picture below. Can you rearrange the 12 matchsticks, so that they encompass an area of 4?

Remark: You should have only one resulting shape and no matches should be unused.

First, create a Pythagorean triangle with sides 3, 4, 5, and area 6. Then simply flip its right angle inwards, so that the area decreases by 2.

Programmers and Coins

One programmer draws on a sheet of paper several circles in a line, representing coins, and puts his thumb on the first circle, covering the rest with his hand. Then he asks another programmer to guess how many different head-tail combinations are possible if someone flips all the (imaginary) coins on the paper. The second programmer, without knowing the number of circles, takes the pen and writes down a number. Then the first programmer lifts his hand and sees that the correct answer is written on the paper. How did the second programmer manage to do this?

The second programmer wrote down “1” in front of the first circle. When the second programmer lifted his hand, he saw the number “10…00”, which is exactly the number of possible head-tail combinations in binary system.

The Pasta Puzzle

You have 10 strings of pasta left on your plate. You randomly start tying up their ends, until there are no loose ends anymore. What is the average number of loops which are created?

The expected (average) number of loops at the end of the procedure is equal to the expected number of loops created after the first tying, plus the expected number of loops created after the second tying, etc. After each tying, the number of non-loop strings decreases by 1, and then the probabilities to create a new loop are 1/19, 1/17, 1/15, etc. Therefore, the answer is the sum 1/19 + 1/17 + 1/15 + … + 1/3 + 1/1 ~ 2.1.

The Missing Digit

The number 229 has 9 digits, all different. Which digit is missing?

Bonus: Is the number 9991 prime?

Let the missing digit be m. Every number and the sum of its digits give the same remainder when divided by 9. The number 229 = 32 * 644 gives remainder 5 when divided by 9, and therefore 9 divides (0 + 1 + 2 + … + 9) – 5 – m = 40 – m. Thus, the missing digit is 4.

Bonus: 9991 = 10000 – 9 = 1002 – 32 = (100 – 3)(100 + 3) = 97 * 103. Therefore the number 9991 is not prime.

Cover the Table

100 coins are placed on a rectangular table, such that no more coins can be added without overlapping. Show that you can cover the entire table with 400 coins (overlapping allowed).

Since we can not place any more coins on the table, each point of it is at distance at most 2r from the center of some coin, where r is the radius of the coin. Now shrink the entire table twice in width and length, then replace every shrunk coin with a full sized one. This way the small table will be completely covered because every point of it will be at distance at most r from the center of some coin. Add three more of these smaller tables, covered with coins, to create a covering of the big table.

Borromean Rings

Borromean rings are rings in the 3-dimensional space, linked in such a way that if you cut any of the three rings, all of them will be unlinked (see the image below). Show that rigid circular Borromean rings cannot exist.

Assume the opposite. Imagine the rings have zero thickness and reposition them in such a way, that two of them, say ring 1 and ring 2, touch each other in two points. These two rings lie either on a sphere or a plane which ring 3 must intersect in four points. However, this is impossible.

Securing the Box

There are 5 people who possess a box. You are allowed to secure the box with as many different locks as you like and distribute any combination of keys for these locks to any people among the 5. Find the least number of locks needed, so that no 2 people can open the box, but any cannot people can open it.

For every subset of 2 people you pick among the 5, there should be a lock which none of the 2 can unlock, and each of the remaining 3 people can unlock. Clearly, the lock in question cannot be the same for any two different subsets of 2 people you choose. Therefore the number of locks you need is at least the number of different 2-element subsets of a 5-element set, which is 5!/(2!3!)=10. This number is sufficient as well – just give keys to a different group of 3 people for every lock.