Leave No Squares

How many matchsticks do you need to remove so that no squares of any size remain?

Nine matchsticks are enough, as seen from the solution below.

To see that eight matchsticks are not enough, notice that removing an inner matchstick reduces the number of 1×1 squares at most by 2. Since there are 16 such small squares, in order to get rid of them all, we need to remove only inner matchsticks. However, in this case, the large 4×4 square will remain.

Circular Racetrack

Suppose you are on a one-way circular racetrack. There are 100 gas cans randomly placed on different locations of the track and the total amount of gas in the cans is enough for your car to complete an entire circle. Assume that your car has no gas initially, but you can place it at any location on the track, then pick up the gas cans along the way and use them to fill the tank. Show that you can always choose a starting position so that you can complete an entire circle.

Imagine you put your car at any location, but instead with an empty tank, you start with enough gas to complete the circle. Then, simply track the amount of gas you have and locate the point on the track where it is the lowest. If you choose that location as a starting point, you will be able to complete the track.

12 Balls, 1 Defective

You have 12 balls, 11 of which have the same weight. The remaining one is defective and either heavier or lighter than the rest. You can use a balance scale to compare weights in order to find which is the defective ball and whether it is heavier or lighter. How many measurement do you need so that will be surely able to do it?

It is easy to see that if we have more than 9 balls, we need at least 3 measurements. We will prove that 3 measurements are enough for 12 balls.

We place 4 balls on each side of the scale. Let balls 1, 2, 3, 4 be on the right side, and balls 5, 6, 7, 8 on the left side.

CASE 1. The scale does not tip to any side. For the second measurement we place on the left side balls 1, 2, 3, 9 and on the right side balls 4, 5, 10, 11.

If the scale again does not tip to any side, then the defective ball is number 12 and we can check whether it is heavier or lighter with our last measurement.

If the scale tips to the left side, then either the defective ball is number 9 and is heavier, or it is number 10/11 and is lighter. We measure up balls 10 and 11 against each other and if one of them is lighter than the other, then it is the defective one. If they have the same weight, then ball 9 is the defective one.

If the scale tips to the right side, the procedure is similar.

CASE 2. Let the scale tip to the left side during the first measurement. This means that either one of the balls 1, 2, 3, 4 is defective and it is heavier, or one of the balls 5, 6, 7, 8 is defective and it is lighter. Clearly, balls 9, 10, 11, 12 are all genuine. Next we place balls 1, 2, 5, 6 on one side and balls 3, 7, 9, 10 on the other side.

If the scale tips to the left, then either one of the balls 1, 2 is defective and it is heavier, or ball 8 is defective and lighter. We just measure up balls 1 and 2 against each other and find out which among the three is the defective one.

If the scale tips to the right, the procedure is similar.

If the scale does not tip to any side, then either the defective ball is 4 and it is heavier, or the defective ball is 8 and it is lighter. We just measure up balls 1 and 4 against each other and easily find the defective ball.

Not Twins

A teacher enters the classroom and sees on the first row two students sitting next to each other, looking completely identical. She asks them if they are twins, but the students simultaneously reply that they are not. After checking in the records, the teacher furthermore discovers that the two children have the same mother and father. What is the explanation?

The students are three of a triplet.

Chessboard Madness

You have unlimited number of knights, bishops, rooks and kings. What is the biggest number of pieces (any combination) you can place on a chessboard, so that no piece is attacked by another one?

If we put 32 knights on all black squares, then no two pieces will attack each other. Now let’s see that if we have more than 32 pieces, then there will be two which attack each other. Split the chessboard in 8 rectangular sectors of size 2×4. It is not hard to see that if we have more than 4 pieces in the same 2×4 sector, then 2 of them will attack each other. Therefore we can place at most 4 × 8 = 32 pieces on the chessboard.

FEATURED

Shark Attack

A man stands in the center of a circular field which is encompassed by a narrow ring of water. In the water there is a shark which is swimming four times as fast as the man is running. Can the man escape the field and get past the water to safety?

Yes, he can. Let the radius of the field is R and its center I. First the man should start running along a circle with center I and radius R/4. His angular speed will be bigger than the angular speed of the shark, so he can keep running until gets opposite to it with respect to I. Then he should dash away (in a straight line) towards the water. Since he will need to cover approximately 3R/4 distance and the shark will have to cover approximately 3.14R distance, the man will have enough time to escape.

Pinned Men

The following game is played under very specific rules – no pinned piece checks the opposite king. How can White mate Black in 2 moves?

First, White plays f3 and threatens mate with Qxe2. Indeed, blocking with the black rook on d4 will not help, because it will become pinned, which means that the rook on d6 will become unpinned, which will make the bishop on b6 pinned, and that will unpin the knight on c7, resulting in a mate. Below are listed all variations of the game.

1. … Rd5 2. Qxe2#
2. … Bxa5 2. Kc8#
3. … Bxc7 2. Nxc7#
4. … Bxe8 2. Kxe8#
5. … Qxe7+ 2. Kxe7#
6. … Rd2 2. Bxd2#
7. … Rxd6+ 2. Qxd6#

Ants on a Stick

On the ground there is a stick and 10 ants standing on top of it. All ants have the same constant speed and each of them can travel along the entire stick in exactly 1 minute (if it is left alone). The ants start moving simultaneously straightforward, either towards the left or the right end of the stick. When two ants collide with each other, they both turn around and continue moving in the opposite directions. How much time at most would it take until all ants fall off the stick?

Imagine the ants are just dots moving along the stick. Now it looks looks like all dots keep moving in their initially chosen directions and just occasionally pass by each other. Therefore it will take no more than a minute until they fall off the stick. If any of them starts at one end of the stick and moves towards the other end, then the time it will take for it to fall off will be exactly 1 minute.

FEATURED

Prisoners and a Bulb

There are 100 prisoners in solitary cells. There is a central living room with one light bulb in it, which can be either on or off initially. No prisoner can see the light bulb from his or her own cell. Every day, the warden picks a prisoner at random and that prisoner visits the living room. While there, the prisoner can toggle the light bulb if he wishes to do so. Also, at any time, every prisoner has the option of asserting that all 100 prisoners have already been in the living room. If this assertion is false, all 100 prisoners will be executed. If it is correct, all prisoners will be set free.

The prisoners are allowed to get together one night in the courtyard and come up with a plan. What plan should they agree on, so that eventually someone will make a correct assertion and will set everyone free, assuming the warden will bring each of them an infinite number of times to the central living room?

First, the prisoners should elect one of them to be a leader and the rest – followers. The first two times a follower visits the living room and sees that the light bulb is turned off, he should turn it on; after that he shouldn’t touch it anymore. Every time the leader visits the living room and sees that the light bulb is turned on, he should turn it off. After the leader turns off the lightbulb 199 times, this will mean that all followers have already visited the room. Then he can make the assertion and set everyone free.

Battleship

A battleship starts moving at 12 PM from an integer point on the real line with constant speed, landing on every hour again on an integer point. Every day at midnight you can shoot at an arbitrary point on the real plane, trying to destroy the battleship. Can you find a strategy with which you will eventually succeed to do this?

If we know the starting point of the battleship and its speed, then we can determine its position at any time after 12 PM.

There are countably many combinations (X, Y) of starting point and speed. We can order them in the following way:

(0, 0) – starting point 0, speed 0;
(0, 1) – starting point 0, speed +1;
(1, 0) – starting point 1, speed 0;
(0, -1) – starting point 0, speed -1;
(1, 1) – starting point 1, speed +1;
(-1, 0) – starting point -1, speed 0;
(0, 2) – starting point 0, speed +2;
(1, -1) – starting point 1, speed -1;
(-1, 1) – starting point -1, speed 1;
(2, 0)- starting point 2, speed 0,
and so on. Of course, we can choose the ordering in many different ways.

Now we can start exhausting all possibilities one after another. First we assume the combination is (0, 0), calculate where the battleship would be at midnight during the first day and shoot there. Then we assume the combination is (0, 1), calculate where the battleship would be at midnight during the second day and shoot there. If we continue like this, eventually we will hit the battleship.