2
$\begingroup$

Consider the following set of points in the $x-y$ plane:

$$A=\{ (a,b)|a,b \in \mathbb{Z} \ and \ |a|+|b|\le 2\}$$

How to find the number of straight lines which pass through at least 2 points in $A$? One line is determined by 2 distinct points. To find the number of lines one is to choose any 2 points and find the possible combinations. The counting is easy if any 3 points are non-collinear, or only small number of points are collinear and the collinear points are non-collinear to the others. But there are a total of 13 points in the set, which gets complicated(at least for me) when there are different subsets of $A$ which consist of collinear points. Considering separate cases don't help much either.

Is there any way to count the number of lines determined by the points in the set above? And how should one find the number of lines determined when given larger size of set of points? Can anyone provide any hint and guidance? Thanks in advance.

The answer is 40 lines.

$\endgroup$
7
  • $\begingroup$ I feel like an algorithm for an arbitrary set $A$ of points is not possible. $\endgroup$
    – DanZimm
    Jun 8 '14 at 13:54
  • $\begingroup$ How about the set above? Why an algorithm for an arbitrary set of points is not possible? $\endgroup$ Jun 8 '14 at 15:20
  • 1
    $\begingroup$ For the set above the best algorithm I can come up with is ranging the slope through $n/m$ with $n,m \in \{0,1,2\}$ and counting the number of possible lines with these slopes. A general set can have an uncountable number of points so we cannot necessarily enumerate the points thus we cannot necessarily algorithmically count the number of lines. For certain sets you'll be able to count the number of lines (even with an uncountable number of elements) but this will definitely depend on the properties of the set. $\endgroup$
    – DanZimm
    Jun 8 '14 at 15:23
  • 1
    $\begingroup$ @DanZimm, wouldn't you need $n,m\in\{-3,-2,-1,0,1,2,3\}$ to cover the line from $(-2,0)$ to $(1,1)$? $\endgroup$
    – Empy2
    Jun 8 '14 at 15:30
  • $\begingroup$ @Michael ah right, I meant to have the $\pm$ and forgot the $3$'s, my apologies $\endgroup$
    – DanZimm
    Jun 8 '14 at 15:32
1
$\begingroup$

Let's consider the following grid (which represents your set $A$):

         *

     *   *   *

*    *   *   *   *

     *   *   *

         *

Now note we have $3$ vertical lines, $3$ horizontal lines, $5$ lines with slope $1$ and $5$ lines with slope $-1$. Together this is $16$ lines. Lets now iterate through other slopes. Note that if we can find the line for a positive slope, then there will also be the line for the negative slope because of symmetry. So to count our lines with positive slope lets start with the smallest possible slope and work upwards. To begin we have $2$ lines with slope $1 / 3$, next $4$ lines with slope $1 / 2$. Now if you notice theres another symmetry that allows us to deduce that there are $4$ lines with slope $2$ and $2$ lines with slope $3$. Adding these up we get $12$ lines, and then we get our $12$ negative slope lines and our originally $16$ lines. All together this is $40$ lines.

Hope this helps! Symmetry was the key factor to make this easy for me!

$\endgroup$
3
  • $\begingroup$ Nice answer! But I got other answer from a member of AoPS which is more simple. Yours help nonetheless, I will post his answer here too. $\endgroup$ Jun 9 '14 at 8:13
  • $\begingroup$ @DaveClifford ok, no problem, glad to help! Curious about the better answer! $\endgroup$
    – DanZimm
    Jun 9 '14 at 8:17
  • $\begingroup$ answer posted below! $\endgroup$ Jun 9 '14 at 8:22
0
$\begingroup$

There are $13$ points in total which consists of $2$ subsets of $5$ collinear points and $10$ subsets of $3$ collinear points.

Number of ways choosing any $2$ from $13$ points $={13 \choose 2}$

Number of extra lines in the 2 subsets of $5$ collinear points $= 2({5 \choose 2}-1)$

Number of extra lines in the 10 subsets of $10$ collinear points $= 10({3 \choose 2}-1)$

Thus the number of lines are ${13 \choose 2}-2({5 \choose 2}-1)-10({3 \choose 2}-1)=40$

All credits to AoPS member $mavropnevma$

$\endgroup$
2
  • $\begingroup$ Ah very elegant indeed! I do like this :D $\endgroup$
    – DanZimm
    Jun 9 '14 at 8:55
  • $\begingroup$ can't agree more! $\endgroup$ Jun 9 '14 at 9:08

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.