The Majority Name

In a long list of names, one of the names appears more than half of the time. You will be read the names one at a time, without knowing how many they are, and without being able to write them down. If you have a very weak memory, how can you figure out which is the majority name?

Remember the first name and then keep track of whether it has been repeated more than half of the time. To do that, simply add 1 if you hear the name or subtract one when you hear another name. If the list finishes and your counter is positive, then the first name is the majority. If your counter drops to 0, simply restart the procedure with the next name you hear.

This algorithm, invented by R. Boyer and J. Moore, works, because if the counter ends up at 0, then each of the names up to that moment has been read at most half of the time. Therefore, the majority name appears more than half of the time in the remainder of the list.

Ambiguous Clock

The hands of my alarm clock are indistinguishable. How many times throughout the day their positioning is such that one cannot figure out which is the hour hand and which is the minute hand?

Remark: AM-PM is not important.

Imagine that you have a third hand which moves 12 times as fast as the minute hand. Then, at any time, if the hour hand moves to the location of the minute hand, the minute hand will move to the location of the imaginary hand. Therefore, our task is to find the number of times during the day when the hour hand and the imaginary hand are on top of each other, and the minute hand is not.

Since the imaginary hand moves 144 times faster than the hour hand, the two hands are on top of each other exactly 143 times between 12AM and 12PM. Out of these 143 times, 11 times all three arrows are on top of each other. Therefore, we have 2 × (143 – 11) = 264 times when we cannot figure out the exact time during the entire 24-hour cycle.

Vectors -1, 0, 1

Take all 1024 vectors in a 10-dimensional space with elements ±1. Show that if you change some of the elements of some of the vectors to 0, you can still choose a few vectors, such that their sum is equal to the 0-vector.

Denote the 1024 vectors with ui and their transformations with f(ui). Create a graph with 1024 nodes, labeled with ui. Then, for every node ui, create a directed edge from ui to ui-2f(ui). This is a valid construction, since the vector ui-2f(ui) has elements -1, 0, and 1 only. In the resulting graph, there is a cycle:

v1 ⇾ v2 ⇾ … ⇾ vk ⇾ v1.

Now, if we pick the (transformed) vectors from this cycle, their sum is the 0-vector:

f(v1) + f(v2) + … + f(vk) = (v2 – v1)/2 + (v3 – v2)/2 + … + (v1 – vk)/2 = 0.

Odd Rectangle

The sides of a rectangle have lengths which are odd numbers. The rectangle is split into smaller rectangles with sides which have integer lengths. Show that there is a small rectangle, such that all distances between its sides and the sides of the large rectangle have the same parity, i.e. they are all even or they are all odd.

Source: Shortlist IMO 2017

Split the large rectangle into small 1×1 squares and color it in black and white, chessboard-style, such that the four corner squares are black. Since the large rectangle has more black squares than white squares, one of the smaller rectangles also must have more black squares than white squares. Therefore, the four corners of that smaller rectangle are all black. Then, it is easy to see that all distances between its sides and the sides of the large rectangle have the same parity.

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. Now, if any two segments intersect, you can swap the two pairs among these four points and get a smaller total length.

Larger or Smaller

Alice secretly picks two different integers by an unknown process and puts them in two envelopes. Bob chooses one of the two envelopes randomly (with a fair coin toss) and shows you the number in that envelope. Now you must guess whether the number in the other, closed envelope is larger or smaller than the one you have seen.

Is there a strategy which gives you a better than 50% chance of guessing correctly, no matter what procedure Alice used to pick her numbers?

Choose any strictly decreasing function F on the set of all integers which takes values between 0 and 1. Now, if you see the number X in Bob’s envelope, guess with probability F(X) that this number is smaller. If the two numbers in the envelopes are A and B, then your probability of guessing correctly is equal to:

F(A) * 0.5 + (1 – F(B)) * 0.5 = 0.5 + 0.5 * (F(A) – F(B)) > 50%.

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.

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.