## Game of Coins

Kuku and Pipi decide to play a game. They arrange 50 coins in a line on the table, with various nominations. Then, alternating, each player takes on their turn one of the two coins at the ends of the line and keeps it. Kuku and Pipi continue doing this, until after the 50th move all coins are taken. Prove that whoever starts first can always collect coins with at least as much value as their opponent.

Remark: On the first turn, Kuku can pick either coin #1 or coin #50. If Kuku picks coin #1, then Pipi can pick on her turn either coin #2 or coin #50. If Kuku picks coin #50, then Pipi can pick on her turn either coin #1 or coin #49.

Let’s assume Kuku starts first. In the beginning, he calculates the total value of the coins placed on odd positions in the line and compares it with the total value of the coins placed on even positions in the line. If the former has a bigger total value, then on every turn he takes the end coin which was placed on odd position initially. If the latter has bigger value, then on every turn he takes the end coin which was placed on even position initially. It is easy to see that he can always do this because after each of Pipi’s turns there will be one “odd” coin and one “even” coin at the ends of the line.

## Monochrome Isosceles Triangle

All points on a circle are colored in blue and red colors. Show that you can inscribe inside the circle an isosceles triangle whose vertices have the same color.

Inscribe a regular pentagon inside the circle. Three of its five vertices must have the same color, and they form an isosceles triangle.

## 10 Dots, 10 Coins

If you have 10 dots on the ground, can you always cover them with 10 pennies without the coins overlapping?

Assume the dots lie in a plane and the radius of a penny is 1. Make an infinite grid of circles with radii 1, as shown on the picture, and place it randomly in the plane.

If we choose any point in the plane, the probability that it will end up inside some circle of the grid is equal to S(C)/S(H), where S(C) is the area of a coin and S(H) is the area of a regular hexagon circumscribed around it. A simple calculation shows that this ratio is larger than 90%. Therefore, the probability that some chosen point in the plane will not end up inside any circle is less than 10%. If we have 10 points, the probability that neither of them will end up inside a circle is less than 100%. Therefore, we can place the grid in the plane in such a way that every dot ends up in some circle. Now, just place the given coins where these circles are.

## Coins on a Chessboard

There is a room with a chessboard inside. On each of its 64 squares, there is placed a coin, either heads up or heads down. You enter the room and a person inside points towards one special square on the chessboard and gives you the chance to flip one of the coins (whichever you choose). Then you leave the room, your friend enters and has to guess which was the special square on the chessboard. If you two could devise a plan before entering the room, how would you make sure your friend always guesses correctly which is the special square?

First, you must enumerate the coins with numbers from 1 to 64, locate the mystery coin, and calculate the binary representation of its number, padded with zeros on the left to 6 digits length. For example, if the mystery coin is the 5th one on the 4th row, its number would be 29 and will have a binary representation 011101. Then, consider the following sets of coins:

A1 = {row 1, row 2, row 3, row 4}
A2 = {row 1, row 2, row 5, row 6}
A3 = {row 1, row 3, row 5, row 7}
A4 = {column 1, column 2, column 3, column 4}
A5 = {column 1, column 2, column 5, column 6}
A6 = {column 1, column 3, column 5, column 7}

Now, the strategy is to flip the coin which makes the parity of heads in set Ai odd if and only if the i-th digit in the binary representation of the mystery coin is 1. It is easy to check that this is always a possible thing to do.

## 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

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