Competition problem — Combinatorics

Library / /10 of 31

Combinatorics Difficulty 6.2 National Olympiad Prove it Italy

Problem:

On a blackboard are written some integers, between 1 and 7. It is possible that not all the numbers from 1 to 7 are present, and it is also possible that one, some, or all the numbers are repeated, one or more times.

A move consists of choosing one or more numbers present on the blackboard, provided they are all different, erasing them, and writing in their place the numbers which, together with the erased ones, form the whole set $\{1,2,3,4,5,6,7\}$ .

For example, allowed moves are:
- erasing a 4 and a 5, and writing in their place the numbers 1, 2, 3, 6 and 7;
- erasing a 1, a 2, a 3, a 4, a 5, a 6 and a 7 without writing anything in their place.

Prove that, if it is possible to find a sequence of moves that, starting from the initial situation, leads to having on the blackboard a single number (written only once), then this number does not depend on the sequence of moves used.

Solution

Solution:

Let us call $n_{1}$ the number of digits 1 present at a certain moment on the blackboard, $n_{2}$ the number of digits 2, and so on up to $n_{7}$ .

Every time a move is made, each of these multiplicities changes by 1 (and therefore reverses its parity), because every number between 1 and 7 gets either written or erased. Suppose that after a sequence of $k$ moves a single number remains on the blackboard, say $x$ ; $n_{x}$ has changed parity $k$ times and is finally odd; all the other multiplicities, also changing parity $k$ times, end up equal to zero, and are therefore even.

Also in the initial situation, therefore, $n_{x}$ must have a different parity from every other multiplicity. There is therefore no sequence of moves that leads to having on the blackboard a single copy of a number $y$ different from $x$ : $n_{y}$ would have to start with a parity different from all the other multiplicities, but we have already established that it has the same parity as $n_{z}$ for all numbers $z$ different from $x$ .

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.