Maths Olympiad Prep

Library / /120 of 120

Combinatorics Difficulty 7.9 National Olympiad, round 2 Prove it Croatia

In some country there are three cities AA, BB and CC. 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 XX and YY consists of a road that connects XX with a third city ZZ and a road that connects ZZ and YY.

It is known that there are altogether 43 road links between AA and BB, and altogether 29 road links between BB and CC. How many road links can there be between AA and CC altogether? (Sweden 2012)

Solution

Let aa, bb, and cc be the number of direct roads between AA and BB, BB and CC, and AA and CC, respectively. Let xx, yy, and zz be the number of roads from AA to BB, BB to CC, and AA to CC, respectively (so a=xa = x, b=yb = y, c=zc = z).

The total number of road links between AA and BB is the sum of direct roads and indirect roads via CC:

- Direct: aa
- Indirect: for each road from AA to CC and each road from CC to BB, we get an indirect link. So z×yz \times y.

Thus, a+zy=43a + z y = 43.

Similarly, the total number of road links between BB and CC is b+xz=29b + x z = 29.

The total number of road links between AA and CC is c+xyc + x y.

But since aa, bb, cc are the number of direct roads, and xx, yy, zz are the same, we can let x=ax = a, y=by = b, z=cz = c.

So:

- Road links between AA and BB: a+cb=43a + c b = 43
- Road links between BB and CC: b+ac=29b + a c = 29
- Road links between AA and CC: c+ab=?c + a b = ?

Let p=ap = a, q=bq = b, r=cr = c.

So:

p+rq=43p + r q = 43
q+pr=29q + p r = 29
r+pq=?r + p q = ?

We are to find the possible values of r+pqr + p q.

Let us solve for pp, qq, rr.

From the first equation:
p+rq=43p + r q = 43
From the second:
q+pr=29q + p r = 29

Let us try to find integer solutions with p,q,r1p, q, r \geq 1.

Let us try small values for rr.

Let r=1r = 1:

First equation: p+1q=43    p+q=43p + 1 \cdot q = 43 \implies p + q = 43
Second: q+p1=29    q+p=29q + p \cdot 1 = 29 \implies q + p = 29

Contradicts.

Try r=2r = 2:
First: p+2q=43p + 2q = 43
Second: q+2p=29q + 2p = 29

From first: p=432qp = 43 - 2q
Plug into second: q+2(432q)=29    q+864q=29    3q=57    q=19q + 2(43 - 2q) = 29 \implies q + 86 - 4q = 29 \implies -3q = -57 \implies q = 19
Then p=432×19=4338=5p = 43 - 2 \times 19 = 43 - 38 = 5

So p=5p = 5, q=19q = 19, r=2r = 2

Now, r+pq=2+5×19=2+95=97r + p q = 2 + 5 \times 19 = 2 + 95 = 97

Try r=3r = 3:
First: p+3q=43    p=433qp + 3q = 43 \implies p = 43 - 3q
Second: q+3p=29    q+3(433q)=29    q+1299q=29    8q=100    q=12.5q + 3p = 29 \implies q + 3(43 - 3q) = 29 \implies q + 129 - 9q = 29 \implies -8q = -100 \implies q = 12.5
Not integer.

Try r=4r = 4:
First: p+4q=43    p=434qp + 4q = 43 \implies p = 43 - 4q
Second: q+4p=29    q+4(434q)=29    q+17216q=29    15q=143    q=143/159.53q + 4p = 29 \implies q + 4(43 - 4q) = 29 \implies q + 172 - 16q = 29 \implies -15q = -143 \implies q = 143/15 \approx 9.53
Not integer.

Try r=5r = 5:
First: p+5q=43    p=435qp + 5q = 43 \implies p = 43 - 5q
Second: q+5p=29    q+5(435q)=29    q+21525q=29    24q=186    q=186/24=7.75q + 5p = 29 \implies q + 5(43 - 5q) = 29 \implies q + 215 - 25q = 29 \implies -24q = -186 \implies q = 186/24 = 7.75
Not integer.

Try r=6r = 6:
First: p+6q=43    p=436qp + 6q = 43 \implies p = 43 - 6q
Second: q+6p=29    q+6(436q)=29    q+25836q=29    35q=229    q=229/356.54q + 6p = 29 \implies q + 6(43 - 6q) = 29 \implies q + 258 - 36q = 29 \implies -35q = -229 \implies q = 229/35 \approx 6.54
Not integer.

Try r=7r = 7:
First: p+7q=43    p=437qp + 7q = 43 \implies p = 43 - 7q
Second: q+7p=29    q+7(437q)=29    q+30149q=29    48q=272    q=272/48=5.67q + 7p = 29 \implies q + 7(43 - 7q) = 29 \implies q + 301 - 49q = 29 \implies -48q = -272 \implies q = 272/48 = 5.67
Not integer.

Try r=19r = 19:
First: p+19q=43    p=4319qp + 19q = 43 \implies p = 43 - 19q
Second: q+19p=29    q+19(4319q)=29    q+817361q=29    360q=788    q=788/3602.19q + 19p = 29 \implies q + 19(43 - 19q) = 29 \implies q + 817 - 361q = 29 \implies -360q = -788 \implies q = 788/360 \approx 2.19
Not integer.

Try r=43r = 43:
First: p+43q=43    p=4343qp + 43q = 43 \implies p = 43 - 43q
Second: q+43p=29    q+43(4343q)=29    q+18491849q=29    1848q=1820    q=1820/18480.985q + 43p = 29 \implies q + 43(43 - 43q) = 29 \implies q + 1849 - 1849q = 29 \implies -1848q = -1820 \implies q = 1820/1848 \approx 0.985
Not integer.

Try r=1r = 1 again, but swap pp and qq.

Alternatively, try p=1p = 1:
First: 1+rq=43    rq=421 + r q = 43 \implies r q = 42
Second: q+r=29q + r = 29
So r=29qr = 29 - q
Plug into rq=42r q = 42:
(29q)q=42    29qq2=42    q229q+42=0(29 - q) q = 42 \implies 29q - q^2 = 42 \implies q^2 - 29q + 42 = 0
Solve quadratic:
q=29±2924422=29±8411682=29±6732q = \frac{29 \pm \sqrt{29^2 - 4 \cdot 42}}{2} = \frac{29 \pm \sqrt{841 - 168}}{2} = \frac{29 \pm \sqrt{673}}{2}
Not integer.

Try q=1q = 1:
First: p+r=43p + r = 43
Second: 1+pr=29    pr=281 + p r = 29 \implies p r = 28
So p+r=43p + r = 43, pr=28p r = 28
Try integer solutions:
p=1p = 1, r=42r = 42; pr=42p r = 42 (not 28)
p=2p = 2, r=41r = 41; pr=82p r = 82
p=4p = 4, r=39r = 39; pr=156p r = 156
p=7p = 7, r=36r = 36; pr=252p r = 252
p=14p = 14, r=29r = 29; pr=406p r = 406
p=28p = 28, r=15r = 15; pr=420p r = 420
No integer solution.

Try p=2p = 2:
First: 2+rq=43    rq=412 + r q = 43 \implies r q = 41
Second: q+2r=29    q=292rq + 2 r = 29 \implies q = 29 - 2 r
Plug into rq=41r q = 41:
r(292r)=41    29r2r2=41    2r229r+41=0r (29 - 2 r) = 41 \implies 29 r - 2 r^2 = 41 \implies 2 r^2 - 29 r + 41 = 0
Quadratic: r=29±8413284=29±5134r = \frac{29 \pm \sqrt{841 - 328}}{4} = \frac{29 \pm \sqrt{513}}{4}
Not integer.

Try p=3p = 3:
First: 3+rq=43    rq=403 + r q = 43 \implies r q = 40
Second: q+3r=29    q=293rq + 3 r = 29 \implies q = 29 - 3 r
Plug into rq=40r q = 40:
r(293r)=40    29r3r2=40    3r229r+40=0r (29 - 3 r) = 40 \implies 29 r - 3 r^2 = 40 \implies 3 r^2 - 29 r + 40 = 0
Quadratic: r=29±8414806=29±3616=29±196r = \frac{29 \pm \sqrt{841 - 480}}{6} = \frac{29 \pm \sqrt{361}}{6} = \frac{29 \pm 19}{6}
So r=486=8r = \frac{48}{6} = 8, r=106=5/3r = \frac{10}{6} = 5/3
So r=8r = 8
Then q=293×8=2924=5q = 29 - 3 \times 8 = 29 - 24 = 5
Then p=3p = 3

Now, r+pq=8+3×5=8+15=23r + p q = 8 + 3 \times 5 = 8 + 15 = 23

So possible values for r+pqr + p q are 9797 and 2323.

Check for other integer solutions.

Try p=5p = 5:
First: 5+rq=43    rq=385 + r q = 43 \implies r q = 38
Second: q+5r=29    q=295rq + 5 r = 29 \implies q = 29 - 5 r
Plug into rq=38r q = 38:
r(295r)=38    29r5r2=38    5r229r+38=0r (29 - 5 r) = 38 \implies 29 r - 5 r^2 = 38 \implies 5 r^2 - 29 r + 38 = 0
Quadratic: r=29±84176010=29±8110=29±910r = \frac{29 \pm \sqrt{841 - 760}}{10} = \frac{29 \pm \sqrt{81}}{10} = \frac{29 \pm 9}{10}
So r=3810=3.8r = \frac{38}{10} = 3.8, r=2010=2r = \frac{20}{10} = 2
So r=2r = 2
Then q=295×2=2910=19q = 29 - 5 \times 2 = 29 - 10 = 19
Then p=5p = 5

Already found above.

Try p=8p = 8:
First: 8+rq=43    rq=358 + r q = 43 \implies r q = 35
Second: q+8r=29    q=298rq + 8 r = 29 \implies q = 29 - 8 r
Plug into rq=35r q = 35:
r(298r)=35    29r8r2=35    8r229r+35=0r (29 - 8 r) = 35 \implies 29 r - 8 r^2 = 35 \implies 8 r^2 - 29 r + 35 = 0
Quadratic: r=29±841112016r = \frac{29 \pm \sqrt{841 - 1120}}{16}
8411120=279841 - 1120 = -279, so no real solution.

Try p=10p = 10:
First: 10+rq=43    rq=3310 + r q = 43 \implies r q = 33
Second: q+10r=29    q=2910rq + 10 r = 29 \implies q = 29 - 10 r
Plug into rq=33r q = 33:
r(2910r)=33    29r10r2=33    10r229r+33=0r (29 - 10 r) = 33 \implies 29 r - 10 r^2 = 33 \implies 10 r^2 - 29 r + 33 = 0
Quadratic: r=29±841132020r = \frac{29 \pm \sqrt{841 - 1320}}{20}
8411320=479841 - 1320 = -479, no real solution.

Try p=19p = 19:
First: 19+rq=43    rq=2419 + r q = 43 \implies r q = 24
Second: q+19r=29    q=2919rq + 19 r = 29 \implies q = 29 - 19 r
Plug into rq=24r q = 24:
r(2919r)=24    29r19r2=24    19r229r+24=0r (29 - 19 r) = 24 \implies 29 r - 19 r^2 = 24 \implies 19 r^2 - 29 r + 24 = 0
Quadratic: r=29±841182438r = \frac{29 \pm \sqrt{841 - 1824}}{38}
8411824=983841 - 1824 = -983, no real solution.

Try p=23p = 23:
First: 23+rq=43    rq=2023 + r q = 43 \implies r q = 20
Second: q+23r=29    q=2923rq + 23 r = 29 \implies q = 29 - 23 r
Plug into rq=20r q = 20:
r(2923r)=20    29r23r2=20    23r229r+20=0r (29 - 23 r) = 20 \implies 29 r - 23 r^2 = 20 \implies 23 r^2 - 29 r + 20 = 0
Quadratic: r=29±841184046r = \frac{29 \pm \sqrt{841 - 1840}}{46}
8411840=999841 - 1840 = -999, no real solution.

Try p=43p = 43:
First: 43+rq=43    rq=043 + r q = 43 \implies r q = 0
So r=0r = 0 or q=0q = 0, but must be at least 11.

Thus, the only integer solutions are (p,q,r)=(5,19,2)(p, q, r) = (5, 19, 2) and (3,5,8)(3, 5, 8), giving r+pq=97r + p q = 97 and 2323.

Therefore, the possible number of road links between AA and CC is 2323 or 9797.

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.