Problem 171 Solution

This solution was submitted by Shawn Stackhouse. My original solution follows his, however I feel Shawn's is better.

Let's define the number of direct routes from A to B as x.
Let's define the number of direct routes from B to C as y.
Let's define the number of direct routes from A to C as z.

From the information given we know:
x + yz = 82
y + xz = 62

Adding them we get:
x + xz + y + yz = 144
(x + y) * (z + 1) = 144

and subtract them to get:
x - xz - y + yz = 20
(y - x) * (z - 1) = 20

The factors of 20 are {1, 2, 4, 5, 10, 20}. So (z - 1) is one of {1, 2, 4, 5, 10, 20}. then (z + 1) is one of {3, 4, 6, 7, 12, 22}.

The factors of 144 are: {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144}. So (z + 1) must be one of these factors.

Common possible (z + 1) values are {1, 2, 3, 4, 6, 12}. Given (x + y) * (z + 1) = 144, possible values of (x + y) are: {144, 64, 48, 36, 24, 12}.
Possible values of (z - 1) are: {-1, 0, 1, 2, 4, 10}.
Concurrently since (y - x) * (z - 1) = 20, then possible values of (y - x) are: {20, 10, 5, 2, -20}.

This leads to five possible solutions. Note that x+y=64 is not listed because then z would be 1 and (y-x)*(z-1) could not equal 20 for any values of x and y.

  1. If x+y=144 then z=0, y-x=-20, y=62, x=82
  2. If x+y=48 then z=2, y-x=20, y=34, x=14.
  3. If x+y=36 then z=3, y-x=10, y=23, x=13.
  4. If x+y=24 then z=5, y-x=5, y=14.5, x=9.5.
  5. if x+y=12 then z=11, y-x=2, y=7, x=5

The fourth solutions is not possible because there can not be half a path. The problem limits us to z+xy<300, so that eliminates the first three. Thus the fifth solution is the correct one. If x=5, y=7, and z=11 then the final answer is z+xy=11+5*7=46.

Alternative Solution

Here is my original solution.

Let's define the distance from A to B as x.
Let's define the distance from B to C as y.
Let's define the distance from A to C as z.

The information given tells us that:

x+yz=82
y+xz=62
z+xy<300

Combining the first two equations and solving for z we get:

z=(82-x)/y, and z=(62-y)/x

Equating the two we get x/y = (62-y)/(82-x)

Unfortunately trial and error seems the only solution from here. The way I did it was to create a spreadsheet with values of x along one axis and values of y along the other. In the body of the spreadsheet I had the following formula (62-y)/(82-x) - (x/y). Then I simply looked for a zero.

If your ranges for x and y are small then the values x=5 and y=7 should pop out, which lead to the correct solution. However other values that work are (x,y)=(13,23), (14,28), (14,34), (12,42), (5,55).

The problem tell us that z+xy<300. Multiplying x and y easily eliminates all possible values except (5,7) and (13,23). If x=23 and y=23 then z is easily solved as 3. In this case the total paths from A to C would be 3+13*23=302, which is too many.

So x=5 and y=7. Simple algebra tells us that z=11. So 11+5*7 = 46.

Michael Shackleford, A.S.A.