2
$\begingroup$

There is a plane P.100 lines are on P.Is it possible to arrange them in a way such that they intersect in exactly 2002 points given that no three of them are concurrent?

Problem is in starting the question as no specific conditions about lines being parallel are given.

Any help is highly appreciated.

$\endgroup$
6
  • 2
    $\begingroup$ It would be a great help if you could share your thinking on this. $\endgroup$ Aug 21, 2015 at 11:56
  • 1
    $\begingroup$ This smells a bit like an old contest question. Where did you see it? $\endgroup$ Aug 21, 2015 at 20:29
  • 1
    $\begingroup$ @JyrkiLahtonen-This is a question from a RMO sample practise paper. $\endgroup$
    – Soham
    Aug 22, 2015 at 8:24
  • 1
    $\begingroup$ Can't say I'm surprised! From year 2002? :-) $\endgroup$ Aug 22, 2015 at 17:33
  • $\begingroup$ @JyrkiLahtonen Yeah....INMO 2002-isical.ac.in/~rmo/papers/inmo/inmo-2002.pdf $\endgroup$
    – Soham
    Oct 27, 2016 at 15:52

3 Answers 3

5
$\begingroup$

Hint: If $a$ lines are parallel in one direction, the other $100-a$ lines which are in different directions create $a(100-a)$ intersections.

$\endgroup$
2
  • 1
    $\begingroup$ There are more than two possible directions, surely! $\endgroup$
    – Brian Tung
    Aug 21, 2015 at 18:37
  • $\begingroup$ @BrianTung - of course there are. This is a rather poorly asked question with no effort shown. This hint was just to show how to start counting the intersections - choose a direction and count $a$ parallel lines - each of the other lined makes a crossing with that set. So you need to add a term for each direction and then realise you have double-counted. This gives $\sum a(100-a) = 10000-\sum a^2 =4004$ (because $\sum a=100$) which is essentially Jyrki Lahtonen's solution. I've fixed a typo, where I had $n$ rather than $100$ which was possibly confusing, $\endgroup$ Aug 21, 2015 at 19:48
3
$\begingroup$

As others have pointed out, you need to start out by partitioning the lines into groups of parallel ones. Assume that the sizes of the groups are $n_1,n_2,\ldots, n_k$. In other words, there is a group of $n_1$ lines parallel to each other but non-parallel to the rest, another group of $n_2$ lines parallel to each other but non-parallel to the rest et cetera.

The number of points of intersections is then $$ 2002=\sum_{1\le i<j\le k}n_in_j. $$ Multiplying this by $2$ gives $$ \begin{aligned} 4004&=\sum_{1\le i\le k, 1\le j\le k, i\neq j}n_in_j\\ &=(\sum_{1\le i\le k}n_i)(\sum_{1\le j\le k}n_j)-\sum_{1\le i\le k}n_i^2\\ &=100^2-\sum_{i=1}^kn_i^2. \end{aligned} $$ Therefore to solve the problem you need to find natural numbers $k$ and $n_1,n_2,\ldots,n_k$ such that $$ \begin{cases}\sum_{i=1}^kn_i&=100,\\ \sum_{i=1}^kn_i^2&=5996. \end{cases} $$

There are solutions to this system: $$ \begin{aligned} n_1&=75, n_2=19, n_3=n_4=2, n_5=n_6=1,\qquad \text{(Brian Tung)}\\ n_1&=76, n_2=14, n_3=4, n_4=2, n_5=n_6=n_7=n_8=1,\\ n_1&=77, n_2=7, n_3=2, n_4=\cdots=n_{17}=1.\qquad \text{(JL)} \end{aligned} $$

$\endgroup$
4
  • 1
    $\begingroup$ I think this is the only entirely general approach given so far. $\endgroup$
    – Brian Tung
    Aug 21, 2015 at 18:38
  • 1
    $\begingroup$ And it admits of a solution! $75+19+2+2+1+1 = 100$, and $75^2+19^2+2^2+2^2+1^2+1^2 = 5996$. Just found it with trial and error, but I wonder if there's a more systematic approach to it. $\endgroup$
    – Brian Tung
    Aug 21, 2015 at 18:41
  • $\begingroup$ Well done @BrianTung! I just found the exact same solution. Essentially by trial-and-error, descending on the target 5996 from above. Gradually increasing the biggest number trying to get close enough so that further splitting the smaller numbers would get me there. $\endgroup$ Aug 21, 2015 at 18:46
  • 1
    $\begingroup$ Your approach provides $90$ percent of the work. I had the same idea about parallel classes, but I hadn't yet gotten as far as encoding the constraint (a total of $100$ lines) the way you did. Cleverly done! $\endgroup$
    – Brian Tung
    Aug 21, 2015 at 18:50
0
$\begingroup$

100 lines on a plane meeting your condition (that no three of them are parallel) are intersecting at least at 2400 points.

Suppose there are some lines on a plane such that no two of them are parallel. Take some line and rotate it in a way that it will be parallel to some other line. After rotation it still intersects with all the other lines except the one it is parallel to. Then it is clear that in order to minimise the number of total intersections you need to make as many pairs of parallel lines as possible.

Suppose now there are no lines on a plane and let $a_n$ denote number of added intersection points by adding $n$th line to an existing system of lines on a plane. If there are no lines on a plane $a_1 = 0$ of course. Now according to first paragraph we want to minimise the number of intersections so we let second line be parallel to first one. So $a_2 = 0$. Now the third line will intersect both of existing lines in 2 points and $a_3 = 2$. We can make fourth one parallel to third one in order to minimise number of intersection points, so $a_3 = 2$.

$$\vdots$$

By continuing this process you get sequence $a = (a_1, a_2, \dots, a_{99}, a_{100})$, where $a_{2k} = {2k}-2$ and $a_{2k - 1} = a_{2k}$ for all $k=1,2,\dots,50$. The sum of all $a_n$'s is then $$2 \cdot (0+2+4+\dots+48) = 2 \cdot \frac{0+48}{2} \cdot 50 = 2400.$$ And this is the least number of intersections given your conditions.

$\endgroup$
4
  • $\begingroup$ You can have 99 parallel lines and one other crossing them all. $\endgroup$ Aug 21, 2015 at 13:06
  • $\begingroup$ tatan stated that no three lines are parallel $\endgroup$ Aug 21, 2015 at 13:19
  • $\begingroup$ It says no three are concurrent, i.e. no three intersect at the same point. $\endgroup$
    – Dom
    Aug 21, 2015 at 13:25
  • 1
    $\begingroup$ I'm not familiar with word "concurrent", thought it meant parallel. $\endgroup$ Aug 21, 2015 at 14:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .