In some country there are three cities A, B and C. Between each of the two cities there are several roads (at least one) and all the roads are two-way. Apart from the direct road links between two cities, there are also indirect road links. An indirect road link between X and Y consists of a road that connects X with a third city Z and a road that connects Z and Y.
It is known that there are altogether 43 road links between A and B, and altogether 29 road links between B and C. How many road links can there be between A and C altogether? (Sweden 2012)
Solution
Let a, b, and c be the number of direct roads between A and B, B and C, and A and C, respectively. Let x, y, and z be the number of roads from A to B, B to C, and A to C, respectively (so a=x, b=y, c=z).
The total number of road links between A and B is the sum of direct roads and indirect roads via C:
- Direct: a - Indirect: for each road from A to C and each road from C to B, we get an indirect link. So z×y.
Thus, a+zy=43.
Similarly, the total number of road links between B and C is b+xz=29.
The total number of road links between A and C is c+xy.
But since a, b, c are the number of direct roads, and x, y, z are the same, we can let x=a, y=b, z=c.
So:
- Road links between A and B: a+cb=43 - Road links between B and C: b+ac=29 - Road links between A and C: c+ab=?
Let p=a, q=b, r=c.
So:
p+rq=43 q+pr=29 r+pq=?
We are to find the possible values of r+pq.
Let us solve for p, q, r.
From the first equation: p+rq=43 From the second: q+pr=29
Let us try to find integer solutions with p,q,r≥1.
Let us try small values for r.
Let r=1:
First equation: p+1⋅q=43⟹p+q=43 Second: q+p⋅1=29⟹q+p=29
Contradicts.
Try r=2: First: p+2q=43 Second: q+2p=29
From first: p=43−2q Plug into second: q+2(43−2q)=29⟹q+86−4q=29⟹−3q=−57⟹q=19 Then p=43−2×19=43−38=5
So p=5, q=19, r=2
Now, r+pq=2+5×19=2+95=97
Try r=3: First: p+3q=43⟹p=43−3q Second: q+3p=29⟹q+3(43−3q)=29⟹q+129−9q=29⟹−8q=−100⟹q=12.5 Not integer.
Try r=4: First: p+4q=43⟹p=43−4q Second: q+4p=29⟹q+4(43−4q)=29⟹q+172−16q=29⟹−15q=−143⟹q=143/15≈9.53 Not integer.
Try r=5: First: p+5q=43⟹p=43−5q Second: q+5p=29⟹q+5(43−5q)=29⟹q+215−25q=29⟹−24q=−186⟹q=186/24=7.75 Not integer.
Try r=6: First: p+6q=43⟹p=43−6q Second: q+6p=29⟹q+6(43−6q)=29⟹q+258−36q=29⟹−35q=−229⟹q=229/35≈6.54 Not integer.
Try r=7: First: p+7q=43⟹p=43−7q Second: q+7p=29⟹q+7(43−7q)=29⟹q+301−49q=29⟹−48q=−272⟹q=272/48=5.67 Not integer.
Try r=19: First: p+19q=43⟹p=43−19q Second: q+19p=29⟹q+19(43−19q)=29⟹q+817−361q=29⟹−360q=−788⟹q=788/360≈2.19 Not integer.
Try r=43: First: p+43q=43⟹p=43−43q Second: q+43p=29⟹q+43(43−43q)=29⟹q+1849−1849q=29⟹−1848q=−1820⟹q=1820/1848≈0.985 Not integer.
Try r=1 again, but swap p and q.
Alternatively, try p=1: First: 1+rq=43⟹rq=42 Second: q+r=29 So r=29−q Plug into rq=42: (29−q)q=42⟹29q−q2=42⟹q2−29q+42=0 Solve quadratic: q=229±292−4⋅42=229±841−168=229±673 Not integer.
Try p=2: First: 2+rq=43⟹rq=41 Second: q+2r=29⟹q=29−2r Plug into rq=41: r(29−2r)=41⟹29r−2r2=41⟹2r2−29r+41=0 Quadratic: r=429±841−328=429±513 Not integer.
Try p=3: First: 3+rq=43⟹rq=40 Second: q+3r=29⟹q=29−3r Plug into rq=40: r(29−3r)=40⟹29r−3r2=40⟹3r2−29r+40=0 Quadratic: r=629±841−480=629±361=629±19 So r=648=8, r=610=5/3 So r=8 Then q=29−3×8=29−24=5 Then p=3
Now, r+pq=8+3×5=8+15=23
So possible values for r+pq are 97 and 23.
Check for other integer solutions.
Try p=5: First: 5+rq=43⟹rq=38 Second: q+5r=29⟹q=29−5r Plug into rq=38: r(29−5r)=38⟹29r−5r2=38⟹5r2−29r+38=0 Quadratic: r=1029±841−760=1029±81=1029±9 So r=1038=3.8, r=1020=2 So r=2 Then q=29−5×2=29−10=19 Then p=5
Already found above.
Try p=8: First: 8+rq=43⟹rq=35 Second: q+8r=29⟹q=29−8r Plug into rq=35: r(29−8r)=35⟹29r−8r2=35⟹8r2−29r+35=0 Quadratic: r=1629±841−1120 841−1120=−279, so no real solution.
Try p=10: First: 10+rq=43⟹rq=33 Second: q+10r=29⟹q=29−10r Plug into rq=33: r(29−10r)=33⟹29r−10r2=33⟹10r2−29r+33=0 Quadratic: r=2029±841−1320 841−1320=−479, no real solution.
Try p=19: First: 19+rq=43⟹rq=24 Second: q+19r=29⟹q=29−19r Plug into rq=24: r(29−19r)=24⟹29r−19r2=24⟹19r2−29r+24=0 Quadratic: r=3829±841−1824 841−1824=−983, no real solution.
Try p=23: First: 23+rq=43⟹rq=20 Second: q+23r=29⟹q=29−23r Plug into rq=20: r(29−23r)=20⟹29r−23r2=20⟹23r2−29r+20=0 Quadratic: r=4629±841−1840 841−1840=−999, no real solution.
Try p=43: First: 43+rq=43⟹rq=0 So r=0 or q=0, but must be at least 1.
Thus, the only integer solutions are (p,q,r)=(5,19,2) and (3,5,8), giving r+pq=97 and 23.
Therefore, the possible number of road links between A and C is 23 or 97.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.