Three towns - Ambridge, Bordertown, and Capeside are each connected by a network of roads. There are 82 ways to get from Ambridge to Bordertown, including those routes that pass through Capeside. There are 62 ways to get from Bordertown to Capeside, including those routes that pass through Ambridge. The number of ways to get from Ambridge to Capeside, including those ways passing through Bordertown, is less than 300.
How many ways are there to get from Ambridge to Capeside, including those routes that pass through Bordertown?
Starting with Larry's, equations:
(a) x + yz = 82
(b) y + xz = 62
substituting for y in the first equation gives
(c) x + z(62-xz) = 82
solving for x gives
(d) x = (62z - 82)/(z*z - 1)
multiplying by (z + 1) gives
(e) x(z+1) = (62z -82)/(z-1) = 82 - (20/(z-1))
Since the left hand side is integral, z-1 must divide 20 evenly
So, z-1 can only be 1, 2, 4, 5, 10 or 20
and z can only be 2, 3, 5, 6, 11, or 21
And multiplying (d) by (z-1) gives
(f) x(z-1) = (62z-82)/(z+1) = 62 - (144/(z+1)) so (z+1) must divide 144 evenly
z is narrowed down to 2, 3, 5 or 11
Substituting back into (d) and (b) gives
z x y z+xy
-- -- -- -----
2 14 34 > 300
3 13 23 > 300
5 14.5 <<-- x not integral
11 5 7 46
So the only solution to Larry's equations is in fact (5,7,11).
This is presumably the desired answer, but I am not quite satisfied.
(a) The problem does not rule out routes that go start at A and End at C and pass through B multiple times. Of course, there are an infinite number of these, unless we assume that the same road cannot be travelled twice, in which case a solution different from (5,7,11) could potentially be found.
(b) Or, if we are not allowed to pass through the same point twice, then we can envision x routes from A to B and y routes from B to C where some of the x routes and some of the y routes go through a common city (let's call it Rome). In this case, the routes from A to C via B are less than x*y. In the extreme case, if all roads lead through Rome, and if we are not allowed to go through a city more than once, then there are no routes that go from A to C via B, and the total number of routes from A to C without going through B can be any number between 1 and 299.
Am I overthinking the problem? That is why it's a good thing that this lowly apprentice is not allowed to review problems while they are in the queue!
Uniqueness and complications
