Track / Stage 6 / 51 of 400 #1051 of 1964

Problem 1051

National olympiad, first round

Combinatorics Difficulty 6.0 Prove it

5. Let $M$ be the set of all positive integers that satisfy the following conditions: in their decimal representation, there are $n$ ones and $n$ twos, and no other digits. Let $N$ be the set of all positive integers that satisfy the following conditions: in their decimal representation, they are composed only of the digits 1, 2, 3, and 4, and the number of 1s is equal to the number of 2s, and they are $n$ -digit numbers. Prove that $|M|=|N|$ .

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

5. We prove this by establishing a one-to-one correspondence between $M$ and $N$ .

For every $x \in M$ , consider $x$ as a permutation of $11, 12, 21, 22$ from left to right. Replace all pairs of 11 with 1, 22 with 2, 12 with 3, and 21 with 4. This results in a positive integer $y$ consisting of $n$ digits. Since the number of 12 and 21 pairs in $x$ contains the same number of 1s and 2s, the number of 11 pairs must equal the number of 22 pairs in this process. Thus, we have $y \in \mathrm{N}$ , which defines a mapping $f: x \rightarrow y$ from $M$ to $N$ .

Now, for every $y \in N$ , from left to right, replace 1 with 11, 2 with 22, 3 with 12, and 4 with 21. This results in a positive integer belonging to $M$ (since the number of 1s and 2s in the representation of $y$ is equal), indicating that $f$ is a one-to-one correspondence.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.