# 5-digit numbers

How many five-digit numbers are there that can be written with numbers $$1$$ and $$2$$ so that both numbers are distinct in at least two digits?

I know that the number of $$5$$-digits that can be written with numbers $$1$$ and $$2$$ is $$32$$. But how do we get numbers that are distinct in two digits? Please help.

• What do you mean with "distinct in two digits" ? This only makes sense for a pair of numbers, not for a single number. – Peter Mar 15 '19 at 13:34
• @Peter: For an arbitrary pair of numbers. – T. M Mar 15 '19 at 13:37
• OK, so you mean the largest set of such numbers such that every pair has the given property. – Peter Mar 15 '19 at 13:40
• @M.T you should clarify this by giving some examples of what fits and what doesn't. – Rhys Hughes Mar 15 '19 at 13:41
• @M.T This is so that everyone can be clear what you asking – Joseph Martin Mar 15 '19 at 13:50

We show by construction there is a maximum of $$\color{blue}{16}$$ five-digit numbers built from $$1$$ and $$2$$ so that each pair of these numbers are distinct in two or more digits.

Equivalently we consider an alphabet $$\{0,1\}$$ and show the maximum number of words of length $$5$$ with Hamming-distance $$2$$ is $$\color{blue}{16}$$.

We do so by starting wlog with $$00000$$ and skip all words with Hamming-distance $$1$$. As long we have not checked all $$2^5=32$$ words, we take the next word in size we have not considered up to this point and continue by skipping all words with hamming-distance $$1$$.

We obtain \begin{align*} 00000&\qquad\qquad0000\color{blue}{1}\quad000\color{blue}{1}0\quad00\color{blue}{1}00\quad0\color{blue}{1}000\quad\color{blue}{1}0000\\ 00011&\qquad\qquad\color{lightgrey}{0001\color{blue}{0}\quad000\color{blue}{0}1}\quad00\color{blue}{1}11\quad0\color{blue}{1}011\quad\color{blue}{1}0011\\ 00101&\qquad\qquad\color{lightgrey}{0010\color{blue}{0}\quad001\color{blue}{1}1\quad00\color{blue}{0}01}\quad0\color{blue}{1}101\quad\color{blue}{1}0101\\ 00110&\qquad\qquad\color{lightgrey}{0011\color{blue}{1}\quad001\color{blue}{0}0\quad00\color{blue}{0}10}\quad0\color{blue}{1}110\quad\color{blue}{1}0110\\ \\ 01001&\qquad\qquad\color{lightgrey}{0100\color{blue}{0}\quad010\color{blue}{1}1\quad01\color{blue}{1}01\quad0\color{blue}{0}001}\quad\color{blue}{1}1001\\ 01010&\qquad\qquad\color{lightgrey}{0101\color{blue}{1}\quad010\color{blue}{0}0\quad01\color{blue}{1}10\quad0\color{blue}{0}010}\quad\color{blue}{1}1010\\ 01100&\qquad\qquad\color{lightgrey}{0110\color{blue}{1}\quad011\color{blue}{1}0\quad01\color{blue}{0}00\quad00100}\quad\color{blue}{1}1100\\ 01111&\qquad\qquad\color{lightgrey}{0111\color{blue}{0}\quad011\color{blue}{0}1\quad01\color{blue}{0}11\quad0\color{blue}{0}111}\quad\color{blue}{1}1111\\ \\ 10001&\color{lightgrey}{\qquad\qquad1000\color{blue}{0}\quad100\color{blue}{1}1\quad10\color{blue}{1}01\quad1\color{blue}{1}001\quad\color{blue}{0}0001}\\ 10010&\qquad\qquad\color{lightgrey}{1001\color{blue}{1}\quad100\color{blue}{0}0\quad10\color{blue}{1}10\quad1\color{blue}{1}010\quad\color{blue}{0}0010}\\ 10100&\qquad\qquad\color{lightgrey}{1010\color{blue}{1}\quad101\color{blue}{1}0\quad10\color{blue}{0}00\quad1\color{blue}{1}100\quad\color{blue}{0}0100}\\ 10111&\qquad\qquad\color{lightgrey}{1011\color{blue}{0}\quad101\color{blue}{0}1\quad10\color{blue}{0}11\quad1\color{blue}{1}111\quad\color{blue}{0}0111}\\ \\ 11000&\qquad\qquad\color{lightgrey}{1100\color{blue}{1}\quad110\color{blue}{1}0\quad11\color{blue}{1}00\quad1\color{blue}{0}000\quad\color{blue}{0}1000}\\ 11011&\color{lightgrey}{\qquad\qquad1101\color{blue}{0}\quad110\color{blue}{0}1\quad11\color{blue}{1}11\quad10\color{blue}{0}11\quad\color{blue}{0}1011}\\ 11101&\qquad\qquad\color{lightgrey}{1110\color{blue}{0}\quad111\color{blue}{1}1\quad11\color{blue}{0}01\quad1\color{blue}{0}101\quad\color{blue}{0}1101}\\ 11110&\qquad\qquad\color{lightgrey}{1111\color{blue}{1}\quad111\color{blue}{0}0\quad11\color{blue}{0}10\quad1\color{blue}{0}110\quad\color{blue}{0}1110}\\ \end{align*}

The left-most column contains $$16$$ words with pair-wise Hamming-distances $$\geq 2$$.

The five column at the right show words which have been skipped, since they have Hamming-distance $$1$$ with the word in the left-most column.

• The blue marked digit indicates the different digit compared with the selected word in the left-most column.

• Words which have already been skipped in former rows have been greyed out.

The corresponding $$\color{blue}{16}$$ words from the alphabet $$\{1,2\}$$ are \begin{align*} \color{blue}{11111\quad12112\quad21112\quad22111}\\ \color{blue}{11122\quad12121\quad21121\quad22122}\\ \color{blue}{11212\quad12211\quad21211\quad22212}\\ \color{blue}{11221\quad12222\quad21222\quad22221}\\ \end{align*}

The following assumes that every pair of numbers must be different in exactly two digits. The original question required at least two as difference.

Without loss of generality $$11111$$ is one of the selected numbers, the other numbers must have three digits $$1$$ and two digits $$2$$.

The other numbers must be pairwise different in two digits. Therefore, they must have one of the $$2$$ digits in the same position, and the second $$2$$ in a different position.

This leads to a total of five numbers, one digit is needed for the all 2 position, while two digit pairs are needed to separate two numbers each:

1: 12112
2: 12121
3: 12211
4: 22111
5: 11111