Problem 4

Determine all pairs

(h,s)

of positive integers with the following property: if one draws

h

horizontal lines and another

s

lines satisfying (i) they are not horizontal, (ii) no two are parallel, and (iii) no three of the

h+s

lines are concurrent, then the number of regions formed is

1992

Step 1 of 5: Count regions using only non-horizontal lines

Previous step Next step

a_{0,0}=1,\qquad a_{0,s}=a_{0,s-1}+s

Detailed analysis

When a new non-horizontal line is added to $s-1$ lines, it meets them in $s-1$ distinct points and is divided into $s$ pieces, each creating one new region. Starting with $a_{0,0}=1$ gives $a_{0,s}=1+1+\cdots+s=\frac{s^2+s+2}{2}$ .