We want to count all the $6$ digits numbers (including ones with $0$'s as digits) that are strictly greater than $123456$ (or even better, some general method of counting for some number $n$ of length not necessarily 6). However in the collection we are considering, no two numbers can have the same $n^{th}$ digit. For example, $123457$ $224344$ is not allowed since they both have a $2$ in the place of the second digit. We are looking for the largest collection of numbers that satisfy this property. (Note, I just made this question up and imagine the answer will have a small amount of members.)
A second question: the same problem but instead of the condition mentioned above, each number has no repeating digits. I.e. $133457$ is not allowed due to the repeating $3$.
$\endgroup$ 62 Answers
$\begingroup$Since our 6-digit numbers must be greater than $123456$, they must have a digit $d \geq 1$ as the digit on the far left. By the pigeonhole principle, we can have at most $9$ such six digit numbers. This provides an upper bound on our answer. As the list below shows, this upper bound can be attained:
$$199999 \\ 222222 \\ 333333 \\ 444444 \\ 555555 \\ 666666 \\ 777777 \\ 888888 \\ 911111$$
Now for the more general question you hinted at. Given an $x$-digit number $n$, what is the maximum number of $x$-digit numbers greater than $n$ such that none of these numbers have the $i$th digit in common? The answer is $10 - d$, where $d$ is the left-most digit of $n+1$. Since our numbers must all be greater than or equal to $n+1$, and since they must all have differing left-most digits, it follows from the pigeonhole principle that $10 - d$ is an upper bound on our answer.
Now we show that this upper bound can always be attained. Let the first number in our answer set be $n+1$, and let the remaining numbers have left-most digits $d+1, d+2,...,9$. Since these remaining numbers are guaranteed to be greater than $n$, we have complete freedom in choosing the rest of their digits. Since we have $10$ digits to work with and $10-d \leq 10$ numbers to place them in, we can easily fill in digits in a way that prevents the $i$th digit of any two numbers from being the same.
Now for your second question. How many 6-digit numbers greater than $123456$ contain no repeated digits? To compute this number, we compute the number of 6-digit numbers without repeated digits, and subtract those numbers that are less than or equal to $123456$.
The number of 6-digit numbers without repeated digits is $10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 = 151200$. Why? Assuming that a number beginning with $0$ is still considered 6-digit, we have ten options for the first digit, nine options for the second digit to avoid repetition, eight options for the third digit, etc.
Now we subtract from this all the numbers without repeated digits that are less than or equal to $123456$. These numbers and their counts are:
- Numbers beginning with $0$ ($9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 = 15120$)
- Numbers beginning with $10$ ($8 \cdot 7 \cdot 6 \cdot 5 = 1680$)
- Numbers beginning with $120$ ($7 \cdot 6 \cdot 5 = 210$)
- Numbers beginning with $1230$ ($6 \cdot 5 = 30$)
- Numbers beginning with $12340$ ($5$)
- The number $123450$ ($1$)
- The number $123456$ ($1$)
Therefore our answer is $151200 - 15120 - 1680 - 210 - 30 - 5 - 1 - 1 = 134153$.
$\endgroup$ $\begingroup$Clearly at most $9$ numbers are possible in either variant, because the first digits must be pairwise different and cannot be $0$. A list that achieves this maximum for both variants is$$ 123457,\\ 234568,\\ 345679,\\ 456780,\\ 567891,\\ 678902,\\ 789013,\\ 890124,\\ 901235 $$You start with $123457$, and the next number is found from the previous by increasing each digit by $1$, wrapping around from $9$ to $0$.
$\endgroup$
