Zbiór zadań, (zadania różne)
Zadanie 286
Na odcinku długości $2013$ rozmieszczono równomiernie $2014$ punktów. Rozpoczynając z dowolnego punktu, poruszając się wzdłuż prostej, należy odwiedzić wszystkie punkty (każdy dokładnie jeden raz) tak, aby przebyta droga była jak najdłuższa. Jaka jest długość najdłuższej drogi?
Rozwiązanie
Przyjmijmy, że $y_0y_1y_2\ldots y_n$ jest najdłuższą drogą złożoną ze wszystkich punktów. Aby droga $d$ była najdłuższą, potrzeba, aby zawsze dwa kolejne odcinki tej drogi miały zwroty przeciwne.
Wówczas, jeśli liczba punktów jest parzysta to
$d = |y_0y_1| - |y_1y_2| + |y_2y_3| - |y_3y_4| + \ldots - |y_{n-2}y_{n-1}| + |y_{n-1}y_n|$
, a jeśli liczba punktów jest nieparzysta to
$d = |y_0y_1| - |y_1y_2| + |y_2y_3| - |y_3y_4| + \ldots + |y_{n-2}y_{n-1}| - |y_{n-1}y_n|$
Oznaczmy przez $x_i$ współrzędną punktu $y_i$
Musi zachodzić warunek: $x_0 < x_1, x_1 > x_2, x_2 < x_3, x_3 > x_4, \ldots$
Ponieważ odległości między punktami są jednakowe można przyjąć że ciąg $x_0, x_1, x_2, \ldots, x_n$ jest pewną permutacją liczb $0, 1, 2, \ldots, n$
Wówczas z
$|y_0y_1| = x_1-x_0, |y_1y_2| = x_2-x_1, |y_2y_3| = x_3-x_2, \ldots $
$x_0 + x_1 + x_2 + \ldots + x_n = \frac{n(n+1)}{2}$
otrzymujemy
$d = n(n+1) - 4(x_2 + x_4 + x_6 + \ldots + x_{n-2}) - 3(x_0+x_n)$
albo
$d = n(n+1) - 4(x_2 + x_4 + x_6 + \ldots + x_{n-1}) - 3(x_0+x_n)$
w zależności od tego, czy $n$ jest parzyste, czy też nie.
Jeśli liczba punktów jest parzysta to $n$ jest nieparzyste.
Oznaczmy dowolną permutację liczb $0, 1, 2, \ldots \frac{n-3}{2}$, przez $x_2, x_4, x_6, \ldots x_{n-1}$
oraz dowolną permutację liczb $\frac{n+3}{2}, \frac{n+5}{2}, \frac{n+7}{2}, \ldots, n$ przez $x_1, x_3, x_5, \ldots x_{n-2}$
i przyjmijmy $x_0 = \frac{n-1}{2}, x_n = \frac{n+1}{2}$.
Wówczas otrzymujemy $d= n(n-1) - 4 \cdot \frac{\frac{n-3}{2}(\frac{n-3}{2}+1)}{2} -3(\frac{n-1}{2} + \frac{n+1}{2}) = \frac{n^2+2n-1}{2}$.
Podstawiając za $n=2013$, otrzymujemy że szukana długość wynosi $2028097$.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>