Diagonal in a Rectangle

A 1000 × 1004 rectangle is split into 1 × 1 squares. How many of these squares does the main diagonal of the large rectangle pass through?

Notice that the number of small squares the main diagonal passes through is equal to the number of horizontal and vertical lines it intersects. Indeed, every time the diagonal goes through the interior of one square to the interior of another, it must intersect one of these lines.

There are 1000 + 1004 = 2004 lines which are intersected by the main diagonal. However, on four occasions (which is the greatest common divisor of 1000 and 1004), the main diagonal intersects one horizontal and one vertical line at the same time, which results in double-counting., so we must subtract 4 from the answer.

Therefore, the answer is 1000 + 1004 – 4 = 2000.

Blue and Red Points

You have 100 blue and 100 red points in the plane, no three of which lie on one line. Prove that you can connect all points in pairs of different colors so that no two segments intersect each other.

Connect the points in pairs of different colors so that the total length of all segments is minimal. If any two segments intersect, you can swap the two pairs among these four points and get a smaller total length.

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.