Knights and Coins

Bob and Jane are taking turns, placing knights and coins respectively on a chessboard. If Bob is allowed to place a knight only on an empty square which is not attacked by another knight, how many pieces at most can he place before running out of moves? Assume that Jane starts second and plays optimally, trying to prevent Bob from placing knights on the board.

Bob can place at most 16 knights. One way to do this is to keep placing knights only on the 32 white squares. In order to see that Jane can prevent Bob from placing more than 16 knights, split the board in four 4×4 grids. Then, group the squares in each grid in pairs, as shown on the image below. If Bob places a knight on any square, then Jane will place a coin on its paired square. This way Bob can place at most one knight on each of the four red squares, one knight on each of the four green squares, one knight on each of the four brown squares, and one knight on each of the four blue squares. Therefore, he can not place more than 64/4 = 16 knights on the board.

Light Bulbs in the Attic

There are three light bulbs in your attic. All of them are turned off and their switches are installed downstairs. You can play with the switches as much as you want and after that, you can visit the attic above just once. How can you find out which switch to which bulb corresponds?

You turn the first switch on, then wait for 30 minutes and turn the second switch on. After that go upstairs and examine the bulbs. The one which is turned off corresponds to the third switch. The one which is turned on and is still cold corresponds to the second switch. The one which is turned on and is hot corresponds to the first switch.

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.

Saavedra Position

White to play. Is this game a win for White, Black, or a draw?

This game is a win for White.

1. c7 Rd6+
2. Kb5 Rd5+
3. Kb4 Rd4+
4. Kb3 Rd3+
5. Kc2! Rd4!
6. c8=R! Ra4
7. Kb3

Now Black will either lose the rook, or get mated in one. If White promoted a Queen instead of a Rook, then 6… Rc4+ would lead to 7. Qxc4, which is a stalemate.

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.

Relabeling Dices

Can you relabel two 6-sided dices, so that every face has a positive number of dots, and also their sum has the same probability distribution?

Yes, you can do this. The easiest way is to use generating functions. Using simple polynomial algebra, you can see that

(x + x2 + x3 + x4 + x5 + x6)2 = (x + 2x2 + 2x3 + x4)(x + x3 + x4 + x5 + x6 + x8).

Therefore, if you take a dice with spots {1, 2, 2, 3, 3, 4}, and a dice with spots {1, 3, 4, 5, 6, 8}, their sum will have the same probability distribution.

The Lion and the Zebras

The lion plays a deadly game against a group of 100 zebras that takes place in the steppe (an infinite plane). The lion starts in the origin with coordinates (0,0), while the 100 zebras may arbitrarily pick their 100 starting positions. The lion and the group of zebras move alternately:

  • In a lion move, the lion moves from its current position to a position at most 100 meters away.
  • In a zebra move, one of the 100 zebras moves from its current position to a position at most 100 meters away.
  • The lion wins the game as soon as he manages to catch one of the zebras.

Will the lion always win the game after a finite number of moves? Or is there a strategy for the zebras that lets them to survive forever?

Source: Puzzling StackExchange

The zebras can survive forever. They choose 100 parallel strips with width 300m each, then start on points on their mid-lines. If the lion lands on some zebra’s strip, the zebra simply jumps 100m away from the lion, along its mid-line.