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