1
$\begingroup$

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.

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

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*}

$\endgroup$
0
0
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.