2

I'm having trouble doing basic competition-level problems and I'm not too sure why. It's mostly the kind of problems that stem from probability, counting, and recurrence relations word problems. For example, let's take the question below as an example.

Lines $L_1$, $L_2$, $L_3$, $L_4$, $\ldots$, $L_{50}$ are distinct. All lines $L_{4n}$, where $n$ are positive integers, are parallel to each other. All lines $L_{4n-3}$, where $n$ are positive integers, pass through a given point $A$. What is the maximum number of points of intersection of pairs of lines from the complete set $\{L_{1},\space L_2,\space\ldots,\space L_{50}\}$?

I'm having lots of trouble with these kinds of problems because I'm not sure where to start and how to tackle it. Do I first draw a diagram? Should I consider simpler cases first? I'm not sure what I'm supposed to do with these kinds of counting/probability problems.

Crescendo
  • 4,089
  • 1
    Of course, draw a diagram. And yes, if you don't see an immediate resolution for unknown $n$, resolve the problem for small values of $n$, and/or for other "easy" values of n, and look for a pattern. If you find a pattern, see if you figure out why it perhaps holds in general. Induction is always an option. – quasi Apr 15 '18 at 01:47
  • A really excellent book, which I've recommended in the past is $$$$ $\qquad$Patrick -- Intermediate Counting and Probability (2007) $$$$ The goal of the book is to develop the student's skills for competition problems. – quasi Apr 15 '18 at 01:52
  • Check out artofproblemsolving.com. – littleO Apr 15 '18 at 01:56
  • I second @quasi in both recommendations: Try it out for small numbers of lines, and once you see a pattern (if you see a recognizable pattern), try to use induction to see how it extends to larger numbers of lines. Notice that roughly half of the lines are arbitrary (those with indices that are equal to $2$ or $3$ modulo $4$). – Brian Tung Apr 15 '18 at 01:57
  • Also keep in mind that there is an intersection point between any two lines that aren't parallel (or coincident), and that intersection points are likely not going to coincide (that is to say, there isn't any condition on the lines that makes it likely for three or more lines to intersect in the same point). – Brian Tung Apr 15 '18 at 01:57
  • Hint: Does it matter that all lines whose indices are equal to $1$ modulo $4$ go through point $A$? – Brian Tung Apr 15 '18 at 01:58
  • @quasi The first five cases are $0,1,3,6,10$ so the general rule is$$L_n=\binom {n-1}{1}+\binom {n-1}2$$? – Crescendo Apr 15 '18 at 02:05
  • @Crescendo: If so, that would be an odd way of writing $\binom{n}{2}$. :-) – Brian Tung Apr 15 '18 at 02:08
  • So, part of the skill in examining this kind of problem is knowing how large a small version of the problem has to be before it's large "enough." Do you think that looking at five lines is enough of a "sample size"? – Brian Tung Apr 15 '18 at 02:09
  • @BrianTung No, probably not. But if I go higher for $n=6,7,\ldots$, it'll be more difficult to draw the diagrams... i.e muddled intersections – Crescendo Apr 15 '18 at 02:10
  • If you're interested in solving this particular problem, maybe overgeneralizing it might help. Suppose you have $m$ parallel lines, $n$ lines that all go through point $A$, and $p$ arbitrary lines. Which ones can intersect which others? – Brian Tung Apr 15 '18 at 02:13
  • @BrianTung The parallel lines won’t intersect and there are $m$ parallel lines so then $\binom m2$ because for every two lines, there is only one point of intersection. And since we have a total of $\binom {m+n+p}2$, then it’s $\binom {m+n+p}{2}-\binom m2$? – Crescendo Apr 15 '18 at 02:16
  • Let us continue this discussion in chat. – Crescendo Apr 15 '18 at 02:17

2 Answers2

3

I've posted my thoughts on the example problem in the comments.

But in regards to the broader question of how to improve on these problems, there isn't any cookbook approach. Here are some ideas:

  • As littleO mentioned in the comments, check out the artofproblemsolving.com web site.
  • I also like Martin Gardner's Mathematical Games column, which I grew up with; it's an entertaining source of recreational mathematics, much of which contest problems are drawn from.
  • Problems are often simple questions with complex clothing; it's the reduction to that simple question that's the meat of the original problem. Sometimes, these reductions can be seen by sketching the situation, and seeing that there are more constraints than it seems at first glance.
  • I'm a fan of guessing for many problems. It's often easier to confirm or deny a guess than it is to work the other way from the problem to a solution.
  • Find a community of people with whom to work. This doesn't have to be online, although online communities are often easier to find and hook up with. But if you're at a school, seek out resources in the mathematics department. Socializing a problem is a great way to figure out approaches.

Not at all an exhaustive list. Just some thoughts to get the ball rolling.

Brian Tung
  • 34,160
2

For this problem, if you have $n$ lines in general position you have $n \choose 2$ intersection points. The conditions they give you reduce this number. Parallel lines don't intersect and there are $12$ lines that are parallel. This is $12 \choose 2$ points that are missing. The $13$ lines that go through a common point give you one point instead of $13 \choose 2$, so the maximum number of points is ${50 \choose 2}-{12\choose 2}-{13 \choose 2}+1$

Ross Millikan
  • 374,822