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.

  • 4
    This is quite a nice problem. Where did you get it from? – TheSimpliFire Aug 17 at 16:34
  • 1
    @TheSimpliFire A mock test for the PRMO. – user585025 Aug 17 at 16:58
up vote 8 down vote accepted

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$$

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}$

  • 2
    How do you know that they have to be integers? – TheSimpliFire Aug 17 at 15:51
  • I didn't. I just started there cuz why not – Rushabh Mehta Aug 17 at 15:51
  • 3
    This suffices to show that if there is a unique solution that it would have to be $29$, however it has yet to be shown that there must be a unique solution. It is possible that there is a whole range of values that $\overline{BG}$ could take, leaving this answer as being incomplete. – JMoravitz Aug 17 at 15:52
  • Now you have to show that this is the only solution :) – TheSimpliFire Aug 17 at 15:52
  • 1
    @TheSimpliFire He didn't say prove it, so given that I presume this is competition math, this is sufficient – Rushabh Mehta Aug 17 at 15:53
          |____|____|____|____|____|____|____|____|____|____|
          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

  • 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. What does this mean? – user585025 Aug 17 at 16:00
  • @Buddha I concluded the above statement from the given question "A trip along two successive sections never exceeds 12 km. A trip along three successive sections is at least 17 km" – Key Flex Aug 17 at 16:06
  • 1
    And why is it that $AB$ is exactly $5$, instead of at most $5$ like $JK$? – user585025 Aug 17 at 16:10

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$$

  • There are possibilities where $d_5 \neq d_6$. Example: $5, 5, 7, 5, 5, 7, 5, 5, 7, 5$ – tehtmi Aug 18 at 2:58

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}. $$

  • 1
    Umm, this is a contest problem so I don't think this would be very useful? – TheSimpliFire Aug 17 at 15:53
  • @TheSimpliFire Useful to learn something new outside of the contest, which can probably be applied later... – user202729 Aug 18 at 16:16

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})$.

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

$\hspace{4cm}$enter image description here

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$.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.