Savage Road Signs (Part 3)

Question

You only need to have read Part 1 to understand this question, reading Part 2 will only help understanding the epic storyline.

Your daughter refuses to talk to you even though you have (once more) replaced the numbered stickers you took from her. Another outgoing highway is being built, leading out from the city of Savage. This time you were prepared. You outsourced the production of the signs to another company whose sign-printing machine was functional. The shipment of signs arrived the same day you were required to place them, but when you opened the crates you saw this:

All of the zeros hadn't actually been printed! This can be fixed, however! We only need to steal the stickers again and surely we can figure something out. You run into your daughter's room to find her laughing like mad while throwing the pages of stickers into a trash can with flames coming out of it. You spill out the contents of the burning can and stamp out the fire. From the ashes you have recovered only some of the stickers... we now only have three of each digit!

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

This problem isn't open-ended but per @Rubio your answer should give a reasonable explanation as to why it can't be improved upon. Doesn't have to be a math proof, just convince me.

Answers should also identify which digits are stickers. I suggest using bold for the stickers like this: 148

Clarifications:

You only have the 25 signs shown above (missing zeros)

You have 30 total stickers (3 of each digit) that can be added to these signs. As before, 6's are different from 9's (no funny business)

Code requires 20km maximum difference between signs

As my chart hopefully implies, the signs are only big enough to fit 4 digits, and you can only add a sticker to a blank spot

Right now, the first sign in the list would read as 2. Adding a 5 in front of it would make 52. Then, adding a 6 you could make it 652 or even 526. The fact that the 2 was originally intended for the tens place means nothing. Beyond that idea, there shouldn't be any other "lateral-thinking" in this problem

This question has nothing to do with Part 2. Signs are single-sided and show the distance from Savage, just like in Part 1.

Answer 1

Postscript: in hindsight I was able to run an exhaustive search with the minimum distance between signs set to 17 km and no restriction on the first sign.

I found solutions for 484 km, here is one of them

$\color{blue}{1}$4 32 5$\color{blue}{2}$ $\color{blue}{7}$2 $\color{blue}{9}$2 $\color{blue}{1}$12 1$\color{blue}{31}$ 14$\color{blue}{9}$ 16$\color{blue}{9}$ 18$\color{blue}{8}$ $\color{blue}{20}$8 22$\color{blue}{8}$ 24$\color{blue}{8}$ 26$\color{blue}{7}$ 28$\color{blue}{7}$ $\color{blue}{30}$6 3$\color{blue}{26}$ 34$\color{blue}{6}$ 36$\color{blue}{6}$ 38$\color{blue}{5}$ 4$\color{blue}{05}$ 42$\color{blue}{5}$ $\color{blue}{4}$44 46$\color{blue}{4}$ 48$\color{blue}{4}$

None of the 136 solutions uses all the digits.

Edit: a revised solution

482 km is the furthest sign I can make.

$\color{blue}{1}$8
$\color{blue}{3}$6
$\color{blue}{5}$5
$\color{blue}{7}$4
$\color{blue}{9}$2
1$\color{blue}{11}$
12$\color{blue}{9}$
14$\color{blue}{9}$
16$\color{blue}{8}$
18$\color{blue}{8}$
2$\color{blue}{08}$
22$\color{blue}{7}$
24$\color{blue}{7}$
26$\color{blue}{6}$
28$\color{blue}{6}$
3$\color{blue}{06}$
32$\color{blue}{5}$
34$\color{blue}{5}$
36$\color{blue}{4}$
38$\color{blue}{4}$
4$\color{blue}{04}$
42$\color{blue}{3}$
44$\color{blue}{3}$
46$\color{blue}{2}$
48$\color{blue}{2}$

I stepped down by 20 or 19, saving a $\color{blue}{1}$, $\color{blue}{3}$, $\color{blue}{5}$, $\color{blue}{7}$, and $\color{blue}{9}$ for the bottom end.
There is one $\color{blue}{2}$ unused.

Some reasoning:

There can't be more than two consecutive 20 km steps, because it uses 3 same digits.
If the steps are
20 20 19 20 20 19 20 20 19 20 20 19 20 20 19 20 20 19 20 20 19 20 20 19 20 km
then 8 x 19 km steps means it must be at least 8 km short of the maximum 500 km.
This puts the max at 492 km.

My sequence has 5 signs in every 100 km band which is the minimum and optimal spacing. To reach a distance of 490, 491 or 492 km there would either be a 26th sign, or the sequence would need to run through the 400s using odd numbers in the "tens" position, and there are no spare odd digits to make up the signs. Even if there were, the signs x42x, x44x, x46x and x48x remain which can only be used where the "tens" digit is even, which mostly already exist. So there would be a knock-on effect of displacing signs which can't all be used to good effect.

I used the zeros for 20x, 30x and 40x, because otherwise there would need to be 21x, 31x and 41x above, with 19x, 29x and 39x below. The base signs for these do not exist, requiring them to be made from single-digit signs (if enough are available), and it would leave spare the base signs 18, 22, 28, 32, 38, 42. These are too close to be used as they are because their spacing is not optimal.

I didn't use a zero in the 100 region, because the first sign must be less than 20 (it seems obvious that a precious zero won't be wasted on that). So below 100 I stepped using odd tens, and this jumped past the 10x numbers right to 111 (which could have been 112 instead).

Stepping from 111 to 129 conveniently allows the sequence to continue in steps of 19 or 20.

My first solution

462 km is the furthest sign I can make.

$\color{blue}{1}$8
2$\color{blue}{8}$
48
5$\color{blue}{6}$
$\color{blue}{7}$6
$\color{blue}{9}$4
1$\color{blue}{11}$
12$\color{blue}{9}$
14$\color{blue}{9}$
16$\color{blue}{8}$
18$\color{blue}{8}$
2$\color{blue}{07}$
22$\color{blue}{7}$
24$\color{blue}{6}$
26$\color{blue}{6}$
28$\color{blue}{5}$
3$\color{blue}{05}$
32$\color{blue}{5}$
34$\color{blue}{4}$
36$\color{blue}{4}$
38$\color{blue}{4}$
4$\color{blue}{03}$
42$\color{blue}{3}$
44$\color{blue}{3}$
46$\color{blue}{2}$

I started by brute-forcing but could not prune the search enough to make it viable.
By inspection, I could see that the ideal step of 20 km can only be done twice in a row.
Then, the last digit has been used 3 times.
So by pencil and paper, I started at various target distances and worked downwards.
I dropped by 20 twice, then by 19, then by 20 twice, etc.
The problem was making the bottom end work, which I did by saving some digits.
This was by starting with 20 - 20 - 19 etc, then alternating 20 - 19 - 20 - 19.
That way, I kept a spare $\color{blue}{6}$, $\color{blue}{7}$, $\color{blue}{8}$ and $\color{blue}{9}$ for the bottom, as well as the unused x48x sign.

I have not proved that this is the optimal solution.
There are two $\color{blue}{2}$s unused.

Answer 2

Edit:

The maximum distance marker I have managed to construct is

444 km

Using the following placement of stickers (in bold as suggested).

8, 26, 46, 66, 85, 94, 114, 129, 148, 163, 183, 193, 212, 228, 248, 267, 287, 307, 326, 345, 365, 385, 404, 424, 444

Progression on the upper bound

Combining the digits we have on the existing signs with the digits we have from the stickers gives us a total of 71 digits to work with.
Since we cannot proceed 20, 40, 60, 80,... at the beginning (not enough zeroes) it follows that the signs marked less than 100 will take up at least 9 of these digits. This leaves 62 digits for the 3-digit signs which means that we will be able to produce, at most, 20 signs with 3-digit distances. This gives an absolute upper bound of 499km (in theory our first 3-digit sign could be 119 given what I've said so far).

Original

I had originally thought I had a solution with distance

468 km

Using the following signs

5, 25, 45, 48, 67, 87, 107, 126, 146, 166, 185, 204, 224, 244, 263, 283,
302, 322, 342, 361, 381, 399, 419, 428, 448, 468

But as Weather Vane correctly pointed out in the comments, I had constructed a new sign using only stickers (399) which is not permitted.