Thursday 6 August 2015

mathematics - Savage Road Signs (Part 3)


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:


enter image description here


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



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.



No comments:

Post a Comment

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...