5
$\begingroup$

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).

Additionally, list the combinations in your solution.

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Ankoganit Sep 3 '16 at 4:53
  • $\begingroup$ a set of 3-digit combinations (and maximise its cardinality) $\endgroup$ – Jamal Senjaya Sep 3 '16 at 4:55
  • $\begingroup$ I think the edit I proposed should clarify the question. $\endgroup$ – greenturtle3141 Sep 3 '16 at 5:00
  • $\begingroup$ @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. $\endgroup$ – Jamal Senjaya Sep 3 '16 at 5:20
  • $\begingroup$ @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. $\endgroup$ – GentlePurpleRain Sep 3 '16 at 5:27
10
$\begingroup$

The answer is

$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:

enter image description here
(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$

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

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.