8
$\begingroup$

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.

enter image description here

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:

enter image description here

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

|improve this question
$\endgroup$
  • 2
    $\begingroup$ You may want to change it to "how many distinct numbers", if that's what you intended $\endgroup$ – Avi Feb 14 at 14:37
9
$\begingroup$

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

|improve this answer
$\endgroup$
  • $\begingroup$ You might want to reverse the last two digits of 979 as it was picked earlier. $\endgroup$ – Jens Feb 14 at 13:25
  • $\begingroup$ @Jens Thanks, I fixed it. $\endgroup$ – Jaap Scherphuis Feb 14 at 13:29
  • $\begingroup$ Just as the restriction for numbers to be distinct isn't mentioned clearly, I see no restriction on negative numbers anywhere, so if we kept the distinct you imagined and allowed negative "twins", you could bump your count up a bit (right around 400, I think?) $\endgroup$ – Code Jockey Feb 14 at 19:59
  • $\begingroup$ @CodeJockey We are given the digit symbols to build our numbers from, but aren't given any minus signs, so I would say that negative numbers are not allowed. But maybe I'm only thinking that because of the Savage Road Signs puzzle from a while ago that is slightly similar. $\endgroup$ – Jaap Scherphuis Feb 14 at 20:31
  • $\begingroup$ I added non-negative to the puzzle to avoid confusion. $\endgroup$ – CG. Feb 14 at 22:37
1
$\begingroup$

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.

|improve this answer
$\endgroup$
1
$\begingroup$

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

|improve this answer
$\endgroup$
  • $\begingroup$ @JMP thanks for fixing the spoiler. I was already thinking it doesn't seem right. But what was wrong? I can't see the difference in the edit history even if I look at the source. $\endgroup$ – findusl Feb 14 at 16:19
  • 1
    $\begingroup$ The SE editor doesn't like gaps between >! lines. Two spaces at the end of a line adds a newline character. $\endgroup$ – JMP Feb 14 at 16:27
0
$\begingroup$

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\}$$

|improve this answer
$\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.