26

There is a highway that starts in the city of Savage. You must must place distance marker signs on this highway for the outgoing traffic. According to highway code, there must be a distance marker sign at least every 20 km, and every distance marker sign must be labelled with its distance from the start (the city of Savage).

Normally this isn't a problem for you but there is a snag. Your sign printing machine is broken and your only back-up plan is to steal a pack of stickers from your daughter. This pack of stickers contains ten of each digit, 0 through 9 (that's 100 total stickers). As luck would have it, using these stickers isn't against code and you have plenty of blank signs to put them on.

What is the furthest distance marker sign you can place without breaking highway code?

Note: This isn't meant to be a lateral-thinking question. Use no more than 10 of each digit across all signs, no more than a gap of 20 between signs, the answer is the last sign you place. You do not need leading zeros, so "004" can just be "4".

I do not claim to have the optimal answer (but it's probably pretty good). I did not use a computer program, but they are allowed. I guess if you want to answer you should also list all of your signs? Assuming somebody beats me I'll give out the checkmark after a couple of days.

Skosh
  • 3,808
  • 14
  • 33
  • You mention that this isn't a lateral thinking problem; should I take that to mean that I can't use 6's as 9's and vice versa? (ditto for 2's and 5's, though depending on the font, that's a lot more of a stretch). – Ventifacts and Yardangs Jun 10 '19 at 20:29
  • 5
    @GiladM yeah, pretend it's a font where 6's and 9's look different – Skosh Jun 10 '19 at 21:38
  • Upside-down sixes will only get you 1km further. The big constraint here is the number of numbers, and that's difficult to circumvent with cheap tricks. – BlueHairedMeerkat Jun 11 '19 at 13:42
  • Cut the 8's in half to get two zeros? Cut the 7's in half to get two ones? How many times could you cut a 1 (the long way) before they become too thin to read? – Skosh Jun 11 '19 at 14:18

4 Answers4

14

Edit: my improved answer is

688 km

Stepping by 19 or 20 km gave me four solutions, all of which use 10 of each digit 0 - 9:

20 40 60 80 99 118 137 157 177 197 217 237 256 276 295 314 334 353 372 392 411 430 450 470 490 509 529 549 569 588 608 628 648 668 688

20 40 60 79 99 118 137 157 177 197 217 236 256 275 294 314 333 352 372 391 410 430 450 470 490 509 529 549 568 588 608 628 648 668 688

20 40 60 79 98 118 137 157 177 197 217 236 256 275 294 314 333 352 372 391 410 430 450 470 490 509 529 549 569 588 608 628 648 668 688

20 40 60 79 98 117 137 157 177 197 216 236 255 274 294 313 332 352 371 390 410 430 450 470 489 509 529 549 569 588 608 628 648 668 688

My (previous) answer is

488 km.

20 40 60 80 100 120 140 160 180 199 219 239 259 279 299 319 338 358 378 398 418 438 457 477 488

The signs go every 20km until I run out of 0s.
The next is after 19km, and again every 20 km until I run out of 9s.
The next is after 19km, and again every 20 km until I run out of 8s.
The next is after 19km, and again every 20 km until the furthest sign I can make within 20 km
— there are no 8s (48x) or 9s (49x) or 0s (50x) left.

Weather Vane
  • 14,420
  • 1
  • 22
  • 54
  • Yeah, sorry, fixed now, I think. Listen, counting is hard. :P – Ventifacts and Yardangs Jun 10 '19 at 22:28
  • 3
    The new solution is neat! It uses all 100 digits exactly! – Dr Xorile Jun 10 '19 at 22:57
  • Very nice! I didn't count the digits, but if it's valid, that one will be tough to beat! – Ventifacts and Yardangs Jun 10 '19 at 23:13
  • this seems optimal, confirmed by a code. – Oray Jun 11 '19 at 08:54
  • @Oray it's one of four similar solutions all to 688 km. – Weather Vane Jun 11 '19 at 08:59
  • "20 40 60 80 99 119 139 159 179 198 217 237 257 277 297 316 336 356 374 394 414 432 452 472 490 510 530 550 570 588 608 628 648 668 688" another one. – Oray Jun 11 '19 at 11:01
  • @Oray I posted my four solutions. I see your solution contains some signs at 18 km. I attempted to permute them too, but the difference between $2^{35}$ and $3^{35}$ permutations was not feasible to compute. The first took a few seconds, the second ran all night without finding any better than 688. – Weather Vane Jun 11 '19 at 11:30
  • @Oray ah, an improved algorithm found 107 new solutions in less than 1 minute using distances of 18, 19 and 20 km but still to 688 km. Too many to post. Edit: plus another 5 using 17 km. – Weather Vane Jun 11 '19 at 12:11
  • I had thought that 19's and 20's couldn't change the digits fast enough to be viable without a few smaller gaps thrown in, but I'm happy to be wrong. Did you get 688km before using a computer algorithm? I'm impressed either way (my answer was embarrassingly lower). – Skosh Jun 11 '19 at 15:15
  • 2
    @DarkThunder my first attempt was by hand, then by C program. Some don't like that, but it is not a matter of "throwing it at a computer". It takes some skill to craft a program that not only solves the problem, but efficiently. – Weather Vane Jun 11 '19 at 15:26
  • See The end of open-ended puzzles. This is really an optimization problem, for which the community has reached a consensus that "answers should come with justification of why they are optimal; an answer without this is not a full answer." Your answer should give some reasoning as to why it is indeed THE best answer, by showing it reaches the theoretical bound possible for any solution, or by showing why the theoretical bound is unattainable and why your answer comes as close as possible to it. – Rubio Jun 13 '19 at 08:43
  • (Other answers to this question should be very helpful in providing that reasoning.) – Rubio Jun 13 '19 at 08:43
  • @Rubio point taken thank you. Would a programmed solution (without the no-computer tag) be acceptable if the code was posted as the "reason" or "argument"? Interestingly, I tried to better Oray's solution to part 2 of this puzzle and found it fairly straightforward to reason with pencil and paper (and far quicker than my incorrect computer solution, both to write and to execute) that a sign in the 220s is the largest that can be made and my first shot was 1 km short of his total distance. – Weather Vane Jun 13 '19 at 18:13
  • A code solution is only as correct as its methodology is. I think you need to show that the code finds (say by exhaustive brute-force search) the best result - “the computer said so” isn’t proof in and of itself. Your comment here about your incorrect program is exactly why the proof a method works needs to come first, before implementing that method as code to find the solution. – Rubio Jun 14 '19 at 02:14
  • @Oray , " this seems optimal, confirmed by a code" . Did you use dynamic programming algorithm to solve this ? – Hemant Agarwal Dec 19 '22 at 14:32
  • @HemantAgarwal Dynamic programming using recursion. but it has been more than 3 years, cannot find the code if you are asking. though it is not hard to replicate it. – Oray Dec 19 '22 at 16:49
5

646 km

I'm not sure this is the best answer, but I think it's close, and at the very least some decent headway for someone who didn't feel like writing a script to solve it.

To start:

I came up with a hard limit: what if you could just put signs every 20 km without worrying which digits were repeated? Then you'd spend 10 digits getting up to 100 km, and another 15 for each 100 km past that. That gets us to 700 km at the very most. We know the answer's not getting past that. (Actually you could probably get to 710 or 720 with some shenanigans involving high numbers with 1 fewer digit, like 9 and 99, but I digress. My answer doesn't really care about off-by-one errors like that).

So now that we know that

we have no chance of using lots of 7's, 8's, 9's, and 0's in a row, we realize that these digits are a lot less valuable to us than the 1's through 5's that we'll need when we get a few hundred kilometers out.

Next,

I assumed the answer was close to optimal, so 600-something. I'll need 5, maybe 6 each of digits 1 through 5 just for hundreds places. If I'm climbing by just under 20 at a time, I'll need a bunch of odd digits for tens places, and then at some point I'll run out and need to switch to evens. Every switch is a loss of efficiency, so I'll try to only do it once. The rest of the digits will be used for the ones places. That's the game plan.

Following that plan, here's what I came up with:

20, 40, 60, 80, 100, 120, 133, 141, 159, 179, 199, 219, 239, 259, 279, 299, 317, 337, 357, 373, 388, 408, 428, 448, 468, 488, 507, 527, 547, 567, 586, 606, 626, 646.

I could keep rearranging things, but

given that all I have left after this sequence are two 5's, and we're pretty damn close to the fundamental maximum of 700, I think this is close enough. If this isn't the answer, I'm pretty sure that the real answer is ~670, but not much more than that.

Ventifacts and Yardangs
  • 331
  • 1
  • 7
2

Maximum distance (upper bound of solution) can be 699 by counted number of digit used and keeping distance 20 km as far as as possible

xx*5=10 digit (upto 99) + xxx*5*6 (from 99 to 699) =90 digit = 100 digit

Naresh Teli
  • 53
  • 3
1

688 is the best as it uses all 10 sets of 10 digits. I used an excel sheet with a count feature to ensure the correct number of digits. Column A had the values of the markers starting from A3. Columns B to K were used to hold the counts of each number from 0 to 9. Row 2 was used to count each column B to K to ensure each number did not exceed 10. B2 to K37 etc had the following formula added:

=LEN($A3)-LEN(SUBSTITUTE($A3,"0",""))
where $A3 referred to each marker and "0" was changed to reflect each number used so K37 reads:
=LEN($A37)-LEN(SUBSTITUTE($A37,"9",""))
Lonewolf
  • 11
  • 2