Only 1 and 2

Number Theory Level pending

A positive integer with $20$ digits is a interesting number if it only has the digits $1$ and $2$ . (For example, the $1222212212112121112$ is an interesting number.

Find the maximum value of $k$ , such that there exist $k$ interesting numbers where every pair of them differ in at least 3 places.

For example we cannot write both $111\dots1112$ and $1111\dots1222$ , but we can write down $121212\dots121212$ and $212121\dots212121$ .

The answer is 49932.

1 solution

Áron Bán-Szabó
Jun 7, 2017

From the written numbers we can get new numbers. From each number we can get $20$ new numbers following the next instruction:

In each number we change one digit, from $1$ to $2$ , or from $2$ to $1$ .

From that we couldn't get a number which was written or a number which was got by an other number. (Since each pair of written numbers are different in minimum three place.) If there was $m$ numbers in the beginning, then we could get maximum $m(20+1)=21m$ numbers together. $21m\leq 2^{20}$ , because there are $2^{20}$ interesting numbers. So $m\leq \frac{2^{20}}{21}=49932,190\dots$ . The answer is $\boxed{49932}$ .

Remember that to prove something is a maximum, we have to show that

It is an upper bound.
It is the least upper bound.

You have demonstrated 1, but not 2.

Can you show that there are indeed 49932 numbers which satisfy the conditions?

Calvin Lin Staff - 4 years ago

Only 1 and 2

The answer is 49932.

1 solution

0 pending reports