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.