Library / /41 of 43

, 2006

Combinatorics Difficulty 6.8 National Olympiad Prove it Italy

Problem:

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?

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$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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