Competition problem — Combinatorics

Library / /18 of 22

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

Call a positive integer one-full if it satisfies the following criteria:

a. Every digit is either $0$ , $1$ , or $2$ .

b. Out of every two consecutive digits, at least one of them is a $1$ .

For $n \geq 2$ , calculate the number of $n$ -digit one-full numbers. (Numbers beginning with the digit $0$ are not allowed.)

Solution

Solution:

The answer is $2^{n}$ . It is clear that there are four $2$ -digit one-full numbers: $10$ , $11$ , $12$ , and $21$ .

To prove that the required number is $2^{n}$ for all $n \geq 3$ , it is enough to show that there are twice as many $n$ -digit one-full numbers as $(n-1)$ -digit one-full numbers for every $n$ .

Given an $(n-1)$ -digit one-full number, we construct two different $n$ -digit one-full numbers via the following rules:

- If the first digit is $1$ , we replace it with $11$ and then with $21$ .
- If the first digit is $2$ , we replace it with $12$ and then with $10$ .

Since $2$ 's and $0$ 's have the same function in the middle of a number, the two numbers that we get using this process are both one-full. Moreover, since any $n$ -digit one-full number must begin with one of the four $2$ -digit one-full numbers, we can get all $n$ -digit one-full numbers in this way. Thus there are twice as many $n$ -digit one-full numbers as $(n-1)$ -digit ones.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.