1
$\begingroup$

The question is about combinatorics. I have no idea on how to start solving the problem. Please guide me.
$(a) 2mn+ {m \choose 2}$

$(b) \frac{1}{2}m(m-1)+n(2m+n-1)$

$(c) {m \choose 2}+2({n \choose 2})$

(d) none of these
I tried solving this question, but I couldn't even find a starting point??

$\endgroup$
  • $\begingroup$ This problem imho needs more context, for instance a trivial solution could be that all the circles are exactly in the same coordinates and size, and also all the lines are the same line, and that will provide the maximum points of intersection. Theoretically I would dare to say that it is a solution, trivial, but a solution, but is not the one you are looking for probably. $\endgroup$ – iadvd Apr 19 '15 at 8:37
  • $\begingroup$ The question just says GREATEST. And I would update the question, 1 sec. $\endgroup$ – Aditya Agarwal Apr 19 '15 at 8:39
  • 1
    $\begingroup$ Circles can intersect one another in at most two points, lines can intersect one another in at most one point. A circle and a line will intersect in at most two points. Given $n$ circles, we cannot have more than $2\binom n2$ circle-circle intersections. Given $m$ lines, we cannot have more than $\binom m2$ line-line intersections. Finally, we cannot have more than $2n\cdot m$ circle-line intersections. I doubt it will be able to construct setups where all of those intersections occur within the same setup, though. But when you add those figures, you get option (b). $\endgroup$ – String Apr 19 '15 at 8:49
  • $\begingroup$ Why $2{n \choose 2}$? And why $2n.m$. $\endgroup$ – Aditya Agarwal Apr 19 '15 at 8:55
  • 1
    $\begingroup$ @AdityaAgarwal: Two points makes a factor $2$, the number of pairs makes the factor $\binom n2$ or $n\cdot m$ respectively. An thinking it through, I believe this maximum is actually attainable. $\endgroup$ – String Apr 19 '15 at 9:05
3
$\begingroup$

Here are some examples of maximal number of points of intersection for $n,m\in\{1,2,3,4,5\}$:

enter image description here

  1. The number of ways you can choose a pair from $n$ circles is $\binom n2$. Each such pair intersect in at most two points.
  2. The number of ways you can choose a pair from $m$ lines is $\binom m2$. Each such pair intersect in at most one point.
  3. The number of ways you can choose one circle and one line from $n$ circles and $m$ lines is $n\cdot m$. Each such pair intersect in at most two points.

So as a total we have: $$ \begin{align} 2\binom n2+\binom m2+2n\cdot m&=n(n-1)+\frac{m(m-1)}{2}+2n\cdot m\\ &=\tfrac 12m(m-1)+n(2m+n-1) \end{align} $$ which leads directly to the correct answer.

$\endgroup$
  • 1
    $\begingroup$ Pretty slick. I like your approach to the problem. A minor point, your diagram does not match your description. When you have an odd number of lines (m is odd) you are drawing parallel lines which will never intersect. $\endgroup$ – Jason Boyd Apr 19 '15 at 12:57
  • $\begingroup$ @JasonBoyd: Whoops, you are quite right. Not hard to fix, thanks! $\endgroup$ – String Apr 19 '15 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.