3
$\begingroup$

Consider the set of natural numbers from 0 to 999, inclusive. Suppose we select some subset of this set such that any pair of numbers from it share no more than one digit in the same positions. To clarify,

  • Pairs such as 123 and 456 are obviously allowed since they don't share any digits in common.
  • 123 and 321 are allowed together since, while they have the same exact digits, only the 2 is actually in the same position.
  • 812 and 212 would not be allowed since they both share the "12" at their end, which is two digits.
  • 206 and 246 are similarly not allowed; the shared digits don't need to be contiguous.
  • Leading zeroes matter, so 5 and 205 are a forbidden pair as well. (Think of 5 as "005".)

Remember this needs to hold for every pair of numbers in the subset. What is the largest (as in most elements) possible set which satisfies this condition? How about the set with the largest sum of elements?

(Puzzle inspired by a conversation with a friend regarding mistyping ID numbers. Apologies if this has already been asked here.)

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
13
$\begingroup$

For what it's worth, I have a neat visualization of why the answer is 100:
First imagine an easier case, where you have all the numbers 0-99 and you can't have any two numbers share any digit in the same place; we can draw a table of numbers like this: enter image description here
Note that every number in a row shares its first digit, and every number in a column shares its second digit. Therefore you must pick numbers such that no two share a row or column. It's pretty clear that the maximum amount of numbers you're going to be able to pick is 10. Here's one solution:
enter image description here
Now consider the case posed in the question. Get 10 of these 0..99 tables, except the second table has 100..199, the third 200..299, and so on. Then layer them one behind another to form a 10x10x10 grid from 0..999 (I have entered some of the numbers to give you the idea): enter image description here
Note that every number in any 'strip' of ten cubes (row or column) shares 2 digits in common. Therefore you need to pick numbers such that no number shares a 'strip'.

After thinking for a bit it is clear you will only be able to pick 100 such numbers.

Improve this answer
$\endgroup$
6
$\begingroup$

To add to PrisonMonkeys' answer, every set with 100 elements will have the same sum, which is 49950. For each place in the number, each digit can only appear in that place at most 10 times, because it cannot appear with the same value for another place twice. This means that each digit must appear in each place exactly 10 times, for there to be a total of 100 numbers in the set. Therefore we can sum each place separately to get 45000+4500+450=49950.

Improve this answer
$\endgroup$
5
$\begingroup$

I have a solution with 100 elements in the set. Generate each number as follows:

For element $0 \leq n \leq 99$, add ABC to the set where AB is $n$ (with a leading zero if $n < 10$) and C is A+B mod 10. So for $n=3$, AB is 03 and C is 0+3 mod 10=3, meaning ABC is 033.

There are no pairs of numbers in this set that violate the condition (as far as I know, that is). And there is no three-digit number ABC with a different AB part, since I covered all 100 possibilities. Which means that this is the largest possible set which satisfies the condition.

I have no solution for the second question yet.

Improve this answer
$\endgroup$
4
  • $\begingroup$ your explanation of the set seemed rather unclear. I tried to clean it up to make it easier to understand. Feel free to change it if you feel like I didn't capture what you were trying to say. $\endgroup$
    – Rob Watts
    Feb 9, 2015 at 21:26
  • $\begingroup$ @RobWatts Thank you, that is exactly what I was trying to say. It does seem easier to understand, although that's kind of hard to say, I already understood what I meant. $\endgroup$
    – PrisonMonkeys
    Feb 9, 2015 at 21:50
  • $\begingroup$ Hello. Can you add an exemple with n > 10 please ? $\endgroup$
    – Kalissar
    Feb 10, 2015 at 11:01
  • $\begingroup$ @Kalissar For instance $n=57$, then AB is 57 (A=5 and B=7), and C is 5+7 mod 10=2, so ABC is 572. $\endgroup$
    – PrisonMonkeys
    Feb 10, 2015 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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