Running Out of Digits, level 2

Question

_{The challenge idea, and images are credited to Andrew.}

---

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

Now you start listing distinct non-negative numbers, and each time you say a number you must remove the digits required to make the number from your stockpile of digits. You may choose to skip numbers.

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

How many numbers is it possible to list without running out of numbers?

Answer 1

Clearly it is best to choose short numbers, numbers with few digits.

Zero is a valid 1-digit number, so there are $10$ 1-digit numbers, and $90$ 2-digit numbers. These can all be picked, and use up $190$ digits ($10$ zeroes, $20$ of each other digit).

You then have $810$ digits left ($90$ zeros, $80$ of all other digits). This can make $\frac{810}{3}=270$ 3-digit numbers. It is not difficult to choose them all distinct.

In total you therefore can list $10+90+270 = 370$ numbers, and no more.

If you won't allow picking zero, then it is only $369$, and you will be left with a single digit spare.

Here is a specific solution:

Pick all the 1- and 2-digit numbers $0$ to $99$.
From all the 3-digit numbers, pick all those that are multiples of $7, 11, 20, 31,$ or $79$. I chose these numbers with a bit of trial and error in such a way that they use up most of the digits. The list is as follows:

100, 105, 110, 112, 119, 120, 121, 124, 126, 132, 133, 140, 143, 147, 154, 155, 158, 160, 161, 165, 168, 175, 176, 180, 182, 186, 187, 189, 196, 198, 200, 203, 209, 210, 217, 220, 224, 231, 237, 238, 240, 242, 245, 248, 252, 253, 259, 260, 264, 266, 273, 275, 279, 280, 286, 287, 294, 297, 300, 301, 308, 310, 315, 316, 319, 320, 322, 329, 330, 336, 340, 341, 343, 350, 352, 357, 360, 363, 364, 371, 372, 374, 378, 380, 385, 392, 395, 396, 399, 400, 403, 406, 407, 413, 418, 420, 427, 429, 434, 440, 441, 448, 451, 455, 460, 462, 465, 469, 473, 474, 476, 480, 483, 484, 490, 495, 496, 497, 500, 504, 506, 511, 517, 518, 520, 525, 527, 528, 532, 539, 540, 546, 550, 553, 558, 560, 561, 567, 572, 574, 580, 581, 583, 588, 589, 594, 595, 600, 602, 605, 609, 616, 620, 623, 627, 630, 632, 637, 638, 640, 644, 649, 651, 658, 660, 665, 671, 672, 679, 680, 682, 686, 693, 700, 704, 707, 711, 713, 714, 715, 720, 721, 726, 728, 735, 737, 740, 742, 744, 748, 749, 756, 759, 760, 763, 770, 775, 777, 780, 781, 784, 790, 791, 792, 798, 800, 803, 805, 806, 812, 814, 819, 820, 825, 826, 833, 836, 837, 840, 847, 854, 858, 860, 861, 868, 869, 875, 880, 882, 889, 891, 896, 899, 900, 902, 903, 910, 913, 917, 920, 924, 930, 931, 935, 938, 940, 945, 946, 948, 952, 957, 959, 960, 961, 966, 968, 973, 979, 980, 987, 990, 992, 994

This leaves only 21 unused digits. The remaining count is:
0 1 2 3 4 5 6 7 8 9
3,4,1,4,0,4,1,2,0,2

These last few digits can be used up with the following additional numbers that hadn't been picked earlier:
101, 201, 303, 313, 556, 557, 799

Answer 2

Following on from @Jaap, here's a solution in:

$808$.

because:

This method uses a greedy algorithm on the high numbers.

We start by using 80 $1$'s, and so we don't use 11_ or 12_ (at first), and we don't use a $1$ in the unit place. Using 10_, 13_, 14_, 15_, 16_, 17_, 18_, 19_ (=72) and 120, 129, 128, 127, 126, 125, 124, 123:

 0   1   2   3   4   5   6   7   8   9
 72  0   64  62  62  62  62  62  62  62

For the $2$ hundred's, we don't use 21_ or 22_ (at the moment), and we don't finish with a $1$ or a $2$. We don't want to be left with high numbers for later, as these will hamper our low score. We can only use 64 $2$'s, so we use $0,4-9$ in the tens place (=8x8=64).

 0   1   2   3   4   5   6   7   8   9
 56  0   0   46  44  44  44  44  44  44

For the $3$ hundred's, we initially don't use 31_, 32_ or 33_, and we don't finish with a $1,2,3$. We exhaust 30_, 39_, 38_, 37_, 36_, 35_ (=6x7=42) and use 340, 349, 348, 347.

 0   1   2   3   4   5   6   7   8   9
 42  0   0   0   40  31  31  30  30  30

For the $4$ hundred's, we don't use 41_ , 42_, 43_ or 44_, and we don't finish with a $1,2,3,4$. Using 49_, 48_, 47_, 46_, 45_, 40_ (=36) and 440, 449.

 0   1   2   3   4   5   6   7   8   9
 29  0   0   0   0  19  19  18  18  17

For the $5$ hundred's, we don't use 51_, 52_, 53_, 54_ or 55_, and we don't finish with a $1,2,3,4,5$. Using 59_, 58_, 50_ (=15) and 560, 570, 580, 589, 590.

 0   1   2   3   4   5   6   7   8   9
 17  0   0   0   0   0  10   9   8   7

For the $6$ hundred's, we don't use 61_, 62_, 63_, 64_, 65_ or 66_, and we don't finish with a $1,2,3,4,5,6$. Using 69_, 60_ (=8) and 670, 680.

 0   1   2   3   4   5   6   7   8   9
 9   0   0   0   0   0   0   6   5   1

And finally 700, 709, 770, 780, 800, 807, 808.

Answer 3

I think the maximum is 1000 numbers. Clearly the best numbers to use would be 1 digit numbers, as I can list the most of these while using the least amount of digits (one digit for each number). I can list each one digit number 100 times. So I could for example use the following list of numbers, which consists of 1000 numbers and uses all the digits:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Answer 4

I used integer linear programming as follows. Let binary variable $x_i$ indicate whether number $i$ is selected. Let $c_{i,d}$ be the number of times $i$ contains digit $d$. The problem is to maximize $\sum_i x_i$ subject to linear constraints: $$\sum_i c_{i,d} x_i \le 100$$ for each $d$. Here's an optimal solution, with

370 numbers: $$\{0,1,...,102\} \cup \{106,108,109,110,117,120,123,124,125,128,132,142,146,149,152,158,160,164,177,180,182,185,189,190,193,194,195,198,201,206,209,210,213,214,218,231,234,238,239,241,243,246,248,251,256,258,260,264,265,281,283,285,287,289,290,293,294,296,300,303,305,306,307,312,321,324,328,329,335,342,345,347,350,354,360,364,368,370,374,375,377,382,386,389,391,392,398,406,412,416,419,421,423,426,429,432,435,436,437,438,453,456,457,460,461,462,463,465,467,469,473,475,476,487,491,492,496,500,503,506,507,508,511,518,519,521,526,528,530,534,537,543,546,547,550,560,562,564,569,570,573,574,575,577,580,581,582,589,591,598,600,601,603,604,605,606,608,609,610,614,620,624,625,630,634,638,640,641,642,643,647,649,650,652,654,674,677,680,683,690,694,700,703,705,707,708,717,730,734,735,743,745,746,750,753,754,755,764,767,770,771,772,775,776,777,779,780,789,797,798,801,803,805,806,807,809,810,812,815,819,821,823,825,830,836,839,850,851,852,859,860,863,870,879,890,891,893,895,897,900,901,902,906,908,909,910,914,918,919,920,923,924,932,938,941,942,960,962,977,978,980,981,982,983,985,987,990\}$$