# Check digit number : Find the maximum number of distinct ways

Find the maximum number of elements in a set containing combinations of three digits (from 0 through 9) with the following rules:

1. Each digit can be used more than once.
2. Any two combinations in the set can have at most 1 digit in the same place.

Example:

• 922, 433, and 055 can co-exist in the set.
• 922, 432 and 425 is ok as well, since each pair of combinations only have one number in common in the same place.
• However, 123, 124 cannot both be in the set, because they share two numbers in the same place (1, and 2).

• Do we need to make a set of 3-digit combinations (and maximise its cardinality) or a single 6-digit combination (and find the number of ways to do so)? Sep 3 '16 at 4:53
• a set of 3-digit combinations (and maximise its cardinality) Sep 3 '16 at 4:55
• I think the edit I proposed should clarify the question. Sep 3 '16 at 5:00
• @gentlePurpleRain. I think this is not math problem, you can not answer the question using math (addition, subtraction, multiplication, etc), you have to use logic to find the maximum numbers. Sep 3 '16 at 5:20
• @JamalSenjaya It seems like basic combinatorics to me. If you disagree, you're welcome to bring it up in Puzzling Meta and see what others think. If the community disagrees with me, we can certainly give the question another shot. Sep 3 '16 at 5:27

$100$.

## Mathematical construction and proof:

Take the first two digits arbitrarily, say $a$ and $b$, and make the third digit $a+b \pmod{10}$. Do it for all possible ordered pairs of $a$ and $b$. There are obviously $10^2=100$ such pairs, and hence we get $100$ such combinations. Clearly, if some two combinations match in two places, they must match in the third place as well, which means they are actually the same combination.

## Explicit list:

(For a text version, please see the revision history.)

## Proof that we can't do better:

There are only $10^2=100$ possible combinations for the first two digits, so if someone can conjure up a set with more than $100$ elements, some two must have the same pair of first two digits by Pigeonhole Principle. So contradiction. $\blacksquare$

• As the question says, list the numbers ! Sep 3 '16 at 5:57
• @JamalSenjaya OK, did that. If anyone wants to put that in a spoiler-block, feel free to do so. Sep 3 '16 at 6:07
• Not sure why it's exactly necessary to list all the numbers... O_o Sep 3 '16 at 6:17
• OK, I have put the list in an image and spoiler-blocked it. Sep 3 '16 at 6:27