Autostrada
Dwa duże miasta położone przy autostradzie dzieli odległość x. Między nimi przy tej samej autostradzie leży n-2 mniejszych miast. Odległości między wszystkimi n miastami są takie, że jeśli podamy jedną z nich, to będzie wiadomo, o jakie miasta chodzi.
Dla n=5 najmniejsze x=11, a miasta rozmieszczone są tak:
lub tak
Ten drugi układ spełnia jako jedyny następujący warunek: liczba L(n), którą tworzą odległości między kolejnymi miastami, jest najmniejszą z możliwych dla pięciu miast – równą 1352.
Jaka jest najmniejsza wartość L(n) dla siedmiu miast?
Komentarze
Wyszło mi 1-2-4-5-8-10. Ale nie jestem pewien co do tego czy jest to najmniejsza wartość L(n).
Zakładam, że wartość L(n) należy wyznaczyć dla najmniejszej możliwej wartości x.
Oto rozwiązania dla kolejnych wartości n:
3 12: 1 2
4 132: 1 3 2
5 1352: 1 3 5 2
6 13625: 1 3 6 2 5
7 136852: 1 3 6 8 5 2
8 13567102: 1 3 5 6 7 10 2
9 147132863: 1 4 7 13 2 8 6 3
10 15413387122: 1 5 4 13 3 8 7 12 2
11 1391551471062: 1 3 9 15 5 14 7 10 6 2
n = 4, x = 8, L(n) = 125 [8 rozwiązań]
n = 5, x = 11, L(n) = 1352 [4 rozwiązania]
n = 6, x = 17, L(n) = 13625 [8 rozwiązań]
n = 7, x = 25, L(n) = 136852 [10 rozwiązań]
n = 8, x = 34, L(n) = 13567{10}2 [2 rozwiązania, w tym z „cyfrą” 10]
n = 9, x = 44, L(n) = 147{13}(12}863 [2 rozwiązania, z „cyframi” 12 i 13]
Dla kolejnych wartości n mamy:
12 241851131213719: 2 4 18 5 11 3 12 13 7 1 9
13 23201261611154917: 2 3 20 12 6 16 11 15 4 9 1 7
Ujawnienie rozwiązania Mateusza skłoniło do poszukiwania rozwiązań z wszystkimi liczbami jednocyfrowymi, i to jest 128497. Nieco niższe x uzyskujemy dla 132879.
OK, ale chodzi o najmniejsze L(n) dla najmniejszego x przy danym n.
mp
Wygląda mi, że L(7) = 125946.
Natomiast wbrew przykładowi L(5) = 1245.
Po wyjaśnieniu, że x też należy minimalizować:
L(7) = 136852 dla x = 25
natomiast L(5) jak w przykładzie.