Drawing Blanks

Premature Optimization is a Prerequisite for Success

Crossing lines

with one comment

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.

lines

Advertisements

Written by bbzippo

02/14/2010 at 1:21 am

Posted in math

One Response

Subscribe to comments with RSS.

  1. […] 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 […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: