Distance between two stations

Question

A railway line is divided into $10$ sections by the stations $A, B, C, D, E, F, G, H, I, J$ and $K$. The distance between $A$ and $K$ is $56$ km. A trip along two successive sections never exceeds $12$ km. A trip along three successive sections is at least $17$ km. What is the distance between $B$ and $G$?

---

I have no idea how to solve this question. I thought about taking the distance between each set of successive stations as a variable, but this gets too messy. And taking ${56\over10}=5.6$ doesn't work as well. The inequalities look like they're important, but I can not make use of them anywhere.

Please help.

Answer 1

Note that the the distance between $A$ and $D$ is at least $17$. On the other side the distance between $B$ and $D$ is at most $12$. This the distance between $A$ and $B$ is at least $5$. With similar reasoning we get that the length of each section is at least $5$.

So we get that the distance between $G$ and $K$ is at least $22$ (at least $17$ for three sections and at least $5$ for the final one). Thus the distance from $A$ to $G$ is at most $56-22=34$. On the other side there are $6$ sections between $A$ and $G$, so the distance is at least $34$ (we have two times three sections). Thus we conclude that the distance between $A$ and $G$ is $34$.

On the other side the distance between $B$ and $K$ is at least $51$, as it consists of nine sections. Thus the distance $AB$ is at most $56-51=5$. From this and the first paragraph we conclude that $AB=5$ and finally

$$BG = AG - AB = 34-5=29$$

Answer 2

Let $\{x_1,...,x_{10}\}$ represent the distances between each section, i.e., $x_1$ is the distance between $A$ and $B$.

Note that $x_1$ and $x_{10}$ are likely to be quite small, since they are on the edges, and only have to deal with the trip along three successive sections at least 17 km. As such, $x_3$ and $x_8$ are likely to be large in order to ensure the 17 property of $x_1,x_2,x_3$, and $x_8,x_9,x_{10}$. We also know by symmetry that $x_n=x_{11-n}$

Hence, after some guess and check, I came up with

$$\{x_1,...x_{10}\} = \{5, 5, 7, 5, 6, 6, 5, 7, 5, 5\}$$

So, $\overline{BG}=5+7+5+6+6=\textbf{29}$

Answer 3

This is a bruteforce solution, but one way to do this is to simply formulate it as a linear programming feasability problem. Let $x=(x_{1},\ldots,x_{10})$ be the length of the sections. Then, $x$ is a point in the polytope $\{ y \mid A y \leq b \}$ where $$ A=\begin{pmatrix}1 & 1\\ & \phantom{-}1 & \phantom{-}1\\ & & \phantom{-}1 & \phantom{-}1\\ & & & \ddots & \ddots\\ & & & & \phantom{-}1 & \phantom{-}1\\ -1 & -1 & -1\\ & -1 & -1 & -1\\ & & \ddots & \ddots & \ddots\\ & & & -1 & -1 & -1\\ \phantom{-}1 & \phantom{-}1 & \phantom{-}1 & \phantom{-}1 & \cdots & \phantom{-}1\\ -1 & -1 & -1 & -1 & \cdots & -1 \end{pmatrix} \qquad\text{and}\qquad b=\begin{pmatrix}\phantom{-}12\\ \phantom{-}12\\ \phantom{-}12\\ \phantom{-}\vdots\\ \phantom{-}12\\ -17\\ -17\\ \phantom{-}\vdots\\ -17\\ \phantom{-}56\\ -56 \end{pmatrix}. $$

Answer 4

          |____|____|____|____|____|____|____|____|____|____|
          A    B    C    D    E    F    G    H    I    J    K   

From the given information we can say that any single section can be taken as the difference of some $3$ successive sections and subset of $2$ successive sections. So, a single section should be atleast $5$ km long.

Also the section JK is the total line minus $3$ sets of three successive sections AD, DG, and GJ. These three successive sections should be at least length of $51$ km. The section JK can be at most $5$ km. By symmetry AB should also be exactly $5$ km. The lay out of the $3$ sets of successive sections so as to isolate the sections DE or GH, then the same argument as above can be used to conclude that each of them is exactly $5$ km. Since the $3$ sets of $2$ successive sections remaining, namely, BD, EG, and HJ they can sum up to at most $3\cdot12=36$ km and at the same time they must cover the remaining distance. So, $56-(4\cdot5)=36$. So, these three sets of two successive sections must be exactly $12$ km. So, the total length from B to G is exactly $12+5+12=29$ km

Answer 5

Here's a solution that requires the least English :)

Let the distance between $A$ and $B$ be $d_1$, that between $B$ and $C$ be $d_2$, and so on, so that the distance between $J$ and $K$ is $d_{10}$. By symmetry we need only consider $d_1$ to $d_5$. Note also that each section must be at least $5$ kilometres. We seek $$d_2+d_3+d_4+d_5+d_6=d_2+d_3+d_4+2d_5$$ due to symmetry.

Let's now create a list of inequalities:

$$d_1+d_2\le12\tag1$$$$d_1+d_2+d_3\ge17\tag2$$gives$$d_3\ge5\tag3$$ and $$d_2+d_3\le12\tag4$$$$d_2+d_3+d_4\ge17\tag5$$ gives$$d_4\ge5\tag6$$and put $(3)$ into $(5)$ to get $$d_2\le7\tag7$$ Now put $(6)$ into $(1)$ to get $$d_1\le5\implies d_1=5\tag8$$ Put $(7)$ into $(5)$ to give $$d_3+d_4\ge10\tag{9}$$ and $(3)$ gives$$d_4\le5\tag{10}$$ Equating $(6)$ and $(10)$ together gives $$d_4=5\tag{11}$$ Put $(11)$ into $(5)$ to get $$d_2+d_3\ge12\tag{12}$$ and equate with $(4)$ to get $$d_2+d_3=12\tag{13}$$ Finally, $$d_1+d_2+d_3+d_4+d_5=28$$ due to symmetry so $$d_5=28-d_1-d_4-(d_2+d_3)=6\tag{14}$$ Hence the required distance is $$(d_2+d_3)+d_4+2d_5=12+5+2\cdot6=29$$

Answer 6

Let the ten distances between adjacent stations be $x_1$ to $x_{10}$.

$$17 \leq x_1 + (x_2 + x_3) \leq x_1 + 12$$

So

$$x_1 \geq 5$$

And then

$$56 = x_1 + (x_2 + x_3 + x_4) + (x_5 + x_6 + x_7) + (x_8 + x_9 + x_{10}) \geq 5 + 17 + 17 + 17 = 56$$

There is no slack in this inequality, so in fact $x_1 = 5$ and $x_2 + x_3 + x_4 = x_5 + x_6 + x_7 = x_8 + x_9 + x_{10} = 17$.

We can similarly get the symmetric equations $x_{10} = 5$ and $x_1 + x_2 + x_3 = x_4 + x_5 + x_6 = x_7 + x_8 + x_9 = 17$.

Together, these give $x_1 = x_4 = x_7 = x_{10} = 5$ and $x_2 + x_3 = x_5 + x_6 = x_8 + x_9 = 12$.

The solution is then $(x_2 + x_3) + x_4 + (x_5 + x_6) = 12 + 5 + 12 = 29$.

Addendum 1: Multiple solutions to the full system are possible. E.g. $5, 6, 6, 5, 6, 6, 5, 6, 6, 5$ versus $5, 5, 7, 5, 5, 7, 5, 5, 7, 5$.

Addendum 2: As in Key Flex's answer, it is also possible to use splits like $(x_1 + x_2 + x_3) + x_4 + (x_5 + x_6 + x_7) + (x_8 + x_9 + x_{10})$.

Answer 7

Using algebraic method. Label the stations with $A$ through $K$:

$\hspace{4cm}$

The given conditions are: $$K-A=56 \ \ \text{and} \ \ \begin{cases} A-C\ge -12\\ B-D\ge -12\\ C-E\ge -12\\ D-F\ge -12\\ E-G\ge -12\\ F-H\ge -12\\ G-I\ge -12\\ H-J\ge -12\\ I-K\ge -12\\ \end{cases} \ \text{and} \ \begin{cases} D-A\ge 17\\ E-B\ge 17\\ F-C\ge 17\\ G-D\ge 17\\ H-E\ge 17\\ I-F\ge 17\\ J-G\ge 17\\ K-H\ge 17\\ \end{cases}$$ One the one hand: $$(D-A)+(G-D)=G-A\ge 34;$$ on the other hand: $$(K-H)+(H-J)=K-J\ge 5;\\ (K-J)+(J-G)=K-G\ge 22;\\ K-G=(56+A)-G\ge 22 \Rightarrow \\ G-A\le 34.$$ Hence: $\color{red}{G-A=34}$.

One the one hand: $$(B-D)+(D-A)=B-A\ge 5 \Rightarrow A-B\le -5;\\ $$ on the other hand: $$(E-B)+(H-E)=H-B=\ge 34;\\ (H-B)+(K-H)=K-B\ge 51;\\ K-B=(56+A)-B\ge 51 \Rightarrow \\ A-B\ge -5.$$ Hence: $\color{blue}{A-B=-5}$.

In conclusion: $(G-A)+(A-B)=G-B=34+(-5)=29$.