Drawing Blanks

Here is a simple problem that requires an approach somewhat similar to what we used to solve the crocodile problem here http://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.