The streets of the city are a square grid that extends infinitely in all directions. One of the streets has a police officer stationed every 100 blocks and there is a robber is somewhere in the city.

Can you devise a strategy that guarantees the robber will be spotted by a police officer at some point, no matter how he tries to avoid them?

Note: The officers can see infinitely far, but their running speeds are lower than the speed of the robber.

SOLUTION

Let the police officers are located at points with coordinates (100N, 0) for N = 0, ±1, ±2… First, we fix the positions of all officers stationed at points (±200N, 0), then repeatedly perform the following procedure, step by step:

On step M, we let the non-fixed officers who are closest to the center move to the free points with coordinates (K, 0) and (0, K) for K = 0, ±1, ±2, … ±M. Then we fix their positions.

Since there are fixed officers at points (200N, 0) at all times, the robber is contained within some vertical strip the entire time. Therefore, at some point there will be two fixed officers that will restrict the robber within a horizontal segment of size 1, at coordinates (x, T) for x ∈ (S, S+1) and some T. Finally, at some point an officer will move to the point (0, T) and will spot the robber.

We have written the numbers from 1 to 12 on the faces of a regular dodecahedron. Then, we have written on each vertex the sum of the five numbers on the faces incident with it. Is it possible that 16 of these 20 sums are the same?

SOLUTION

We color the vertices in five colors as shown in the image below, such that each face of the dodecahedron has 1 vertex of each color. Then, the sum of the four numbers from each color must be equal to the sum of all numbers written on the faces: 1 + 2 + … + 12 = 78.

If 16 of the vertices have the same number written on them, then by the pigeonhole principle there will be 4 vertices with identical colors and identical numbers. Since 78 is not divisible by 4, we conclude that this is impossible.

Can you find a triple of three-digit numbers that sum up to 999 and collectively contain all digits from 1 to 9 exactly once? How many such triples are there? What if the sum was 1000?

SOLUTION

There are exactly 180 such triples that sum up to 999 and none that sum up to 1000.

In order to see that, notice that the sum of the first digits of the numbers can be no more than 9. Since the sum of all digits is 45, the sum of the middle and the sum of the last digits should be both no more than 9+8+7=24, and no less than 45-9-24=12. We then see that the sum of the last digits should be exactly 19 and the sum of the middle digits should be exactly 18. The sum of the first digits should be 45-19-18=8.

There are 2 ways to get 8 using unique digits from 1 to 9: 1+2+5 and 1+3+4.

If the first digits are {1, 2, 5}, the options for the middle digits are {3, 6, 9}, {3, 7, 8}, and {4, 6, 8}. The last digits end up {4, 7, 8}, {4, 6, 9}, and {3, 7, 9} respectively.

If the first digits are {1, 3, 4}, the options for the middle digits are {2, 7, 9} and {5, 6, 7}. The last digits end up {5, 6, 8} and {2, 8, 9} respectively.

Since the set of the first digits, the set of the middle digits, and the set of the last digits of the numbers can be permuted in 6 ways each, we get a total of 5×6×6×6=1080 solutions, or 180 up to permutation of the 3 three-digit numbers.

In order to see that we cannot get a sum of 1000, we note that since the sum of the digits from 1 to 9 is divisible by 9, then the sum of the 3 three-digit numbers should be divisible by 9 as well. Since 1000 is not divisible by 9, the statement follows.

There are N points on a circle. If we draw all the chords connecting these points and no three of them intersect at the same point, in how many parts will the interior of the circle get broken?

For example, when N is equal to 1, 2, 3, 4, and 5, we get 1, 2, 4, 8, and 16 parts respectively.

SOLUTION

The answer, somewhat surprisingly, is not 2ᴺ⁻¹, but 1 + N(N-1)/2 + N(N-1)(N-2)(N-3)/24.

In order to see that, we start with a single sector, the interior of the circle, and keep successively drawing chords. Every time we draw a new chord, we increase the number of parts by 1 and then add 1 extra part for each intersection with previously drawn chords.

Therefore, the total number of parts at the end will be:

1 + the number of the chords + the number of the intersections of the chords

Each chord is determined by its 2 endpoints and therefore the number of chords is N(N-1)/2.

Each intersection is determined by the 4 endpoints of the two intersecting chords and therefore the number of intersections is N(N-1)(N-2)(N-3)/4!.

You pick a number between 1 and 6 and keep throwing a die until you get it. Does it matter which number you pick for maximizing the total sum of the numbers in the resulting sequence?

In the example below, the picked number is 6 and the total sum of the numbers in the resulting sequence is 35.

SOLUTION

No matter what number you pick, the expected value of each throw is the average of the numbers from 1 to 6 which is 3.5. The choice of the number also does not affect the odds for the number of throws until the game ends, which is 6. Therefore, the total sum is always 3.5 × 6 = 21 on average, regardless of the chosen number.

You split 1000 coins into two piles and count the number of coins in each pile. If there are X coins in pile one and Y coins in pile two, you multiple the two numbers to get XY. Then you split both piles further, repeating the same counting and multiplication process, and adding the new multiplication results to the first one. The process ends when you end up with 1000 single-coin piles. Prove that you will always get the same final result, no matter how the piles have been divided during the splitting process.

For example, if you start with 5 coins and split them into a pile of 2 and a pile of 3, you get the number 2×3=6. Then, if you split the pile of 3 into a pile of 1 and a pile of 2, you will add 1×2=2 more to the 6 and get 8. Finally, if you split the two piles of 2 into single-coin piles, you will end up with 8+1+1=10.

SOLUTION

Consider the sum of the squares of the numbers of coins in each pile, plus twice the sum of the products. On each step, if you split a pile of X+Y coins into a pile of X coins and a pile of Y coins, the sum of the squares will get reduced by 2XY, exactly the amount the sum of the products will increase by. Therefore, that number remains constant throughout the entire process and ends up exactly (1000²-1000)/2=499500.

There are 100 rooms in a row in a building and inside each room there is a lamp that is turned off. One person enters each room and switches the lamp inside. Then, a second person enters every second room (2, 4, 6, etc.) and switches the lamp inside. A third person switches the lamp in every third room and so on and so far, until person #100 switches the lamp in room 100. How many lamps are turned on at the end?

SOLUTION

We can see that the only switches that have been switched an odd number of times are the ones in rooms with perfect square numbers.

Indeed, if person N has switched the switch in room M, then person M/N has done that as well. Since person N and M/N coincide only when M=N², the claim above follows.

We conclude that the number of lamps that are turned at the end is equal to the number of perfect squares less than or equal to 100; that is exactly 10 rooms.