Maths Olympiad Prep

Library / /25 of 48

Geometry Difficulty 7.5 National olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

Determine all pairs (h,s)(h, s) of positive integers with the following property: If one draws hh horizontal lines and another ss lines which satisfy
(i) they are not horizontal,
(ii) no two of them are parallel,
(iii) no three of the h+sh+s lines are concurrent,
then the number of regions formed by these h+sh+s lines is 19921992.

Answer: (995,1),(176,10)(995,1),(176,10), and (80,21)(80,21).

Solution

Let ah,sa_{h, s} be the number of regions formed by hh horizontal lines and ss other lines as described in the problem. Let Fh,s\mathcal{F}_{h, s} be the union of the h+sh+s lines and pick any line \ell. If it intersects the other lines in nn (distinct!) points then \ell is partitioned into n1n-1 line segments and 22 rays, which delimit regions. Therefore if we remove \ell the number of regions decreases by exactly n1+2=n+1n-1+2=n+1.

Then a0,0=1a_{0,0}=1 (no lines means there is only one region), and since every one of the ss lines intersects the other s1s-1 lines, a0,s=a0,s1+sa_{0, s}=a_{0, s-1}+s for s0s \geq 0. Summing yields

a0,s=s+(s1)++1+a0,0=s2+s+22. a_{0, s}=s+(s-1)+\cdots+1+a_{0,0}=\frac{s^{2}+s+2}{2} .

Each horizontal line only intersects the ss non-horizontal lines, so ah,s=ah1,s+s+1a_{h, s}=a_{h-1, s}+s+1, which implies
ah,s=a0,s+h(s+1)=s2+s+22+h(s+1). a_{h, s}=a_{0, s}+h(s+1)=\frac{s^{2}+s+2}{2}+h(s+1) .

Our final task is solving

ah,s=1992s2+s+22+h(s+1)=1992(s+1)(s+2h)=21991=211181. a_{h, s}=1992 \Longleftrightarrow \frac{s^{2}+s+2}{2}+h(s+1)=1992 \Longleftrightarrow (s+1)(s+2 h)=2 \cdot 1991=2 \cdot 11 \cdot 181 .

The divisors of 219912 \cdot 1991 are 1,2,11,22,181,362,1991,39821,2,11,22,181,362,1991,3982. Since s,h>0,2s+1<s+2hs, h>0,2 \leq s+1<s+2 h, so the possibilities for s+1s+1 can only be 2,112,11 and 2222, yielding the following possibilities for (h,s)(h, s) :
(995,1),(176,10), and (80,21). (995,1), \quad(176,10), \quad \text{ and } \quad(80,21) .

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 and solution reproduced as published; topic and difficulty added by this site.