Track / Stage 6 / 324 of 400 #1804 of 2444

Problem 1804

National Olympiad, first round

Combinatorics Difficulty 6.8 Prove it Progetto Olimpiadi di Matematica GARA di SECONDO LIVELLO · Italy · 2006

On the blackboard there is written a 17-digit number made up only of 1s and 2s. Paolo comes in and rewrites the number in reverse order, lining it up under the previous one. Gianni comes in and writes under each column the maximum digit that appears in that column. Alberto comes in and writes under each column the minimum digit that appears in that column, then erases the first two rows. Carla comes in and finds written the numbers 12212212221221221 and 11211111211111211, and is told what Paolo, Gianni, and Alberto did. How many different numbers could have been written on the blackboard as the first number?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:

The answer is $16$ . Before Alberto erases the first two rows, in column $k$ ( $k=1, \ldots, 17$ ) there appear the digit in position $k$ , the digit in the symmetric position $17-(k-1)$ , the maximum between the two, the minimum between the two. When the maximum and the minimum coincide, the digit in position $k$ and the digit in the symmetric position $17-(k-1)$ are equal. This happens in columns $1, 3, 4, 7$ , necessarily in column $9$ , then symmetrically in positions $11, 14, 15, 17$ . In these positions the digits are certainly $1, 2, 1, 1, 2, 1, 1, 2, 1$ , respectively. In the other pairs of symmetric positions, they are $1$ in one and $2$ in the other. Therefore the numbers that could have given rise to the two rows that Carla finds on the blackboard were $2^{4}=16$ .

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty, ordering) added by this project.