5
$\begingroup$

The challenge idea is credited to HelloWorld1337.


You initially have x of each digit from 0 to 9. This means you have x * 10 digits in total. This count for each digit is shown in the table below.

Digit 0 1 2 3 4 5 6 7 8 9
# Remaining x x x x x x x x x x

Now start counting by ones, from 1. Each time you say a number you must remove the digits required to make the number from your stockpile of digits. For example, after you have counted from 1 to 13, the above table now looks like:

As an example, if you counted from 1 to 13 and didn't skip any numbers, the above table will look like:

Digit 0 1 2 3 4 5 6 7 8 9
# Remaining x-1 x-6 x-2 x-2 x-1 x-1 x-1 x-1 x-1 x-1

What is the largest number x you can count to without running out of the digits needed to form the number?

$\endgroup$
2
  • $\begingroup$ Welcome to Puzzling! It seems you have two definitions of x as a variable - lowercase "x" for the number of digits left, and uppercase "X" for the largest number created. I'd suggested changing one of those to a different letter to avoid confusion. $\endgroup$ – bobble Feb 5 at 19:46
  • 1
    $\begingroup$ Makes sense! Thank you. My intent is for those to be the same number; I've edited them accordingly. $\endgroup$ – 00Average Feb 5 at 20:01
1
$\begingroup$

I believe the answer is:

199,981. Mmm. Not this. You can add more and still work: 199,990

Details:

Short answer: I wrote a script. I know, I know.
Roughly, though, 1 in 10 of each digit is a 1. Consider 199,990. Take the last 5 digits of 199,990 and it gives you ~99,995 ones. To this add the 99,990 ones for the hundred-thousands place and you get ~199,985.
At this value, each additional number is adding 1 additional 1 (in the hundred-thousands place), so you can increase/decrease until you get a second 1 somewhere else. So this suggests that for $x\in [199,981;199,990]$ you use exactly $x$ 1s to write out the numbers from 1 to $x$.
When you go to 199,980 you will have 1 one left over. When you get to 199,991, you will be 1 one short.


Edit: Paul Panzer is correct. He should get the tick. Here's a justification:

If $x = k\times10^n-1$ then the number of ones needed is $kn10^{n-1}$ plus an additional $10^n$ if $k\geq2$.
This can be used to show that $1\times10^9<x<2\times10^9$.
With a bit of care, you can now add $2\times10^8$ and discover that $x$ is less than that. But you can add $1\times10^8$, so $x>1.1\times10^9$.
Continue with that process and you get 1,111,111,110 as the maximum $x$

$\endgroup$
4
  • $\begingroup$ Scripts are good! Long time lurker--always appreciate what the programming gang here comes up with to solve these kids of questions. I kind of figured someone would either have a script or some simple-but-elegant proof of why it is what it is. $\endgroup$ – 00Average Feb 8 at 14:20
  • $\begingroup$ I think if Paul Panzer's answer is correct, then it's clearly a larger number than mine. I haven't checked it, but it looks good. $\endgroup$ – Dr Xorile Feb 8 at 17:51
  • $\begingroup$ As per 00Average comments under his answer, seems like yours is correct, and Paul's answer corroborates your answer (visually). $\endgroup$ – justhalf Feb 9 at 8:31
  • $\begingroup$ I've been second-guessing myself, but you both show that your answer is correct. At each new order of magnitude, the count equalizes at all nines (evident on Paul's plot at each 10^n), but then each time we add a digit, the total count of digits is front-loaded with ones, (also visible in his diagram) increasing faster than y=x. It's this front-loading that stops the count before we reach 1,111,111,110. $\endgroup$ – 00Average Feb 9 at 16:15
1
$\begingroup$

I'm pretty sure it's:

1,111,111,110

No proof, though, but a few remarks and a suggestive plot:

the number of ones will never be smaller than that of any other digit
for x of the form 99...99 (k digits) the distribution of 1,2,3,... is even each having been used exactly k x 10^{k-1} times; zeros will have occurred 11...12 (k digits) times less often.
for x of the form 11...10 (k digits) the number of ones used is k x 11...11 (k-1 digits)
enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ It looks like your plot validates Dr. X's answer, unless I'm missing something... Isn't the 1's count kissing (and ostensibly crossing) the line of y=x/total#ofdigits=number right around 200,000? It feels like this plot answered the question too, and I just needed to phrase it better. $\endgroup$ – 00Average Feb 8 at 16:26

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.