## Crossing lines

Here is a simple problem that requires an approach somewhat similar to what we used to solve the crocodile problem here https://bbzippo.wordpress.com/2010/01/08/applied-type-theory/

**There are n straight lines on the plane. Each of them intersects with exactly 101 other lines. How many lines are there?**

Solution:

Answer: n = 102 or n = 202.

If there are no parallel lines among them, then n=102 because each line crosses all other lines.

If some line is parallel to exactly k other lines, then every line is parallel to exactly k other lines. Otherwise there would exist two lines that cross a different number of other lines.

So all our lines are grouped into classes by their direction, each class containing k+1 lines. Let the total number of classes (directions) be p. Then n = (k+1)p. Then the number of lines that each line intersects is

n – k –1 = (k+1)p – k –1 = (k+1)p – (k+1) = (k+1)(p-1) – we factorized it, this is the biggest trick in this whole problem 🙂

101 = (k+1)(p-1)

But 101 is prime. So either k+1=1 and p=102 which means there are no parallels, or p-1=1 and k+1=101 and n = 202.

[…] a comment » The problem from the previous post https://bbzippo.wordpress.com/2010/02/14/crossing-lines/ has obviously nothing to do with geometry. All we needed to know about lines on the plane is that […]

Alternative theme for counting equivalence classes « Drawing Blanks02/15/2010 at 8:10 am