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.

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

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:

Digit 0 1 2 3 4 5 6 7 8 9
# Remaining 99 94 98 98 99 99 99 99 99 99

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

Improve this question
$\endgroup$
0
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 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$
5
  • $\begingroup$ You might want to reverse the last two digits of 979 as it was picked earlier. $\endgroup$
    – Jens
    Feb 14 '20 at 13:25
  • $\begingroup$ @Jens Thanks, I fixed it. $\endgroup$
    – Jaap Scherphuis
    Feb 14 '20 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 '20 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 '20 at 20:31
  • $\begingroup$ I added non-negative to the puzzle to avoid confusion. $\endgroup$
    – CG.
    Feb 14 '20 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$
2
  • $\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 '20 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 '20 at 16:27
1
$\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$
0

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.