0
$\begingroup$

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$
  • $\begingroup$ Please clarify the question. Exactly which numbers do you want to count? There will be many different sets of numbers with the property that no two can have the same $n$'th digit. Which one do you want to count? $\endgroup$ – Robert Israel May 2 at 16:52
  • $\begingroup$ I have edited accordingly. I meant the largest set of $6$ digit numbers s.t. every member is greater than $123456$ (or better, for some $n$) and no two members have a common digit, i.e. $123457$ and $234567$ are not allowed. $\endgroup$ – kam May 2 at 16:56
  • $\begingroup$ Isn't the answer obviously $1$? Two different six-digit (decimal) numbers must have a common digit. The interesting question would be how many six-digit numbers are there without repeated digits that exceed $123456$. $\endgroup$ – Robert Shore May 2 at 17:16
  • 1
    $\begingroup$ Unless I am missing something, how about this for a counter example: $123457, 777778$. Both numbers are 6 digits long and are greater than $123456$ yet they do not share a common digit at a particular position. $\endgroup$ – kam May 2 at 17:39
  • $\begingroup$ For numbers not of length $6$, is there a different cut-off point? Shorter numbers are all less than $123456$; longer numbers are all greater than $123456$. $\endgroup$ – nickgard May 2 at 17:49
1
$\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$
1
$\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$

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.