FIRST PROBLEM: Set 102 straight lines on a plane, so they intersect in exactly 2002 points.

Draw 24 equally-spaced parallel lines, and cross them with 76 other
equally-spaced lines perpendicular to the first group, for 24*76 =
1824 crossings.  Draw the other two lines at a 45-degree angle to all
the others (and parallel to each other). Place one so that it crosses 11 of the intersections of the first two groups of lines. It makes new intersections with the other 78 lines.  Place the other line so that it crosses all 100 of the original lines.  1824 + 178 = 2002.


As it is, it's quite difficult to solve -- I guess the professor made a typo when he wrote the problem, so here is a... SECOND PROBLEM: What number would have made that a reasonable High School level problem?

102 points crossing in 2001 intersections -- a problem he may have given the year before.  This works with 26 parallel lines crossed by 75 parallel lines (1900 intersections) plus one additional line which makes new intersections with each of the first 101 lines.

Joseph DeVincentis
---------------------------------------------------------------
Hi Ed,

"Set 102 straight lines on a plane, so they intersect in exactly 2002
points. As it is, it's quite difficult to solve -- I guess the professor
made a typo when he wrote the problem"

The problem is extremely simple to solve using a program.
One has to draw 5 groups of lines, the lines is each group being parallel to
each other but not to the lines in the other groups. The number of lines in
each group is 2,5,7,9 and 79.

Here's the C++ program:

#include <iostream>
using namespace std;
#define MAX_LEVEL 5
int n[MAX_LEVEL];

void search(int level, int prev, int remainder) {
  if (level==(MAX_LEVEL-1)) {
    n[MAX_LEVEL-1] = remainder;
    int sum = 0;
    for (int i=0;i<MAX_LEVEL-1;i++)
      for (int j=i+1;j<MAX_LEVEL;j++)
        sum += n[i] * n[j];
    if (sum==2002) {
      for (int i=0;i<MAX_LEVEL;i++)
        cout << n[i] << ' ';
      cout << endl;
    }
    return;
  }

  for (int i=prev+1;i<remainder-level-MAX_LEVEL+1;i++) {
    n[level] = i;
    search(level+1, i, remainder-i);
  }
}
int main(void) {
  search(0, 0, 102);
  return 0;
}


Greetings from Belgium,

Luc Kumps
------------------------------------------------------
Hi! Ed,

Federico Kereki's ploblem is as follows:

[FIRST PROBLEM]
Set the 5 sets of parallel lines on a plane as follows.
The numbers of lines of each set are...
Answer1: 1, 1, 5, 17, 78
Answer2: 2, 5, 7, 9, 79
Answer3: 3, 5, 5, 10, 79

(I don't check yet these are all or not.) 

[SECOND PROBLEM]
For example: change 102 to 113.

If assume 2 sets of parallel lines, this problem is ... 

Find the value of integer a, b.
a+b=113
a*b=2002

x*x-113x+2002=0
(x-91)(x-22)=0
x=91 or 22


--Koshi Arai
------------------------------------------------------
Hi,

PART 1:
If nothing unusual happens (parallel lines, or 3+ lines intersecting at
a point), then the 102 lines will have a total of 5151 intersections.

If several lines are parallel to each other, then we will miss all their
intersections with each other.  That will be a triangular number.

If several lines intersect in a single point, then we will have one
intersection instead of a (larger) triangular number of intersections.

We actually want 2002 intersections, so the general case has 3149 too
many intersections.  We want to represent 3149 as a sum of triangles and
near-triangles.  Using a greedy aproach, it is easy to find that 3149 is
3081+66+3 -1.  3081 results from something involving 79 lines, 66 from
12 lines, and 3 from 3 lines.  Twe of these involves sets of parallel
lines and one involves several lines intersecting in a single point.

So, start with 3 lines that intersect in a single point.  Add 78 lines
parallel to one of them, and 11 lines parallel to another one of them.
That uses 92 of the 102 lines.  Add the last 10 lines avoiding any more
parallel lines or multiple intersections.

PART 2:
There are several numbers that could easily be mis-typed as 102 and have
simpler answers.
120: pick 2 points A and B.  have 20 lines pass through A and 100 lines
through B.  Avoid parallel lines and the line AB.  This give 2002
intersections: A, B, and the 2000 intersections of a line passing
through A with a line passing through B.
1002: Use 1000, 2 instead of 100, 20.
103: pick 2 directions.  Use 26 parallel lines in 1 direction and 77
parallel lines in the other direction.  26 X 77 = 2002.

-jim boyce
-----------------------------------------------------------
Ed,

Let us separate the 102 lines into two bundles.
Within each bundle, the lines can be parallel or not.
However, if they are not parallel, they must intersect
at the first line in the bundle.  Creating one point at
that spot.

Solution 1        Solution 2
    25                100   Bundle A
    77                  2   Bundle B
    24                 24   Non-Parallel lines in Bundle A
    75                  1   Non-Parallel lines in Bundle B

This problem could have been easier if the teacher had said
"line segments" instead of  "lines."

Dick Saunders Jr.
----------------------------------------------------------------

I will do the easier part 2 first, since it sheds light on part 1.

Part 2:   Simple High School Problem:

The intended problem most likely had 103 lines intersecting in exactly 2002 
points.

Simply choose 2 sets of parallel lines not parallel to each other.
The sets have A lines and B lines respectively.
Then the total number of lines is  A+B = 103
And the total number of points is  A*B = 2002
Solving these 2 equations we get  A = 77 and B = 26

Note: using this same parallel scheme with different line totals we get 8 
different solutions.
The 8 line totals are 103, 113, 157, 167, 193, 293, 1003, 2003.
103 is the smallest and the closest to 102.

------------------------------------------------------------------
Part 1:  Find 102 lines intersecting in exactly 2002 points.

Among the numerous possible schemes and solutions I like the following the 
best: 

Choose 3 sets of equally-spaced parallel lines, having A, B, C lines 
respectively, with A largest and C smallest. Let sets A and B have the same equal spacing 
and at right angles to one-another. Set C lies at a 45 degree angle to A and B, 
with no 3 lines concurrent (i.e, no line of C passes through any intersection 
of A and B). 

Now the number of lines is  A + B + C = 102.
And the number of intersections is  A*B + A*C + B*C = X.

Now X does not equal 2002 for any integral A,B,C. However, there are 5 
solutions with X greater than 2002, namely 2007, 2009, 2012, 2015, 2024 with the 
smallest being 2007. 
For X=2007 we have A = 78, B = 15, C = 9. This solution has 5 more 
intersections than desired. Now we move one of the lines of set C parallel to itself  until 
it passes through intesections of  lines of sets A and B. The number of 
intersections it can pass through can be any number from 1 to B = 15. So we choose the 
position where it passes through exactly 5 intesections. Thus the number of 
distinct intersections this line makes with all lines of A and B has been reduced 
by 5 from A+B to A+B-5, bringing the total down from 2007 to 2002.

Bob Kraus


Ed,

Here is an addendum to my previous solution to Part 1:

102 lines intersect in exactly 2002 points. If you don't want any more than 2 lines passing through any point of intersection, then the following solution works:

Choose 5 sets of parallel lines none of which are parallel to the lines in any other set, and arrange them so that no line passes through the intersection of any 2 other lines. If the number of lines in the 5 sets are A, B, C, D, E, in descending order, then
A+B+C+D+E=102
A*B+A*C+A*D+A*E+B*C+B*D+B*E+C*D+C*E+D*E=2002
and there are exactly 3 solutions:
  78, 17, 5, 1, 1
  79, 9, 7, 5, 2
  79, 10, 5, 5, 3
And there are no solutions for less than 5 sets.

Bob Kraus 
-----------------------------------------------------------------
I'm sure that by finding the problem as late as I have, I'm probably not the 
first, but it requires a minimum of five set of parallel lines, 
(78,17,5,1,1) being the count of lines in each set, though (79,10,5,5,3) 
works as well.  I'm not sure what number the fellow was looking for, but 
2000, 2001, and 2003 can all be made in multiple ways with fewer sets of 
lines, with 2001's (76,25,1) combination particularly easy to find.  Thanks 
as always for maintaining quite the spiffy page.

Andy Juell
---------------------------------------------------
From Federico Kereki: This problem comes "from real life" -- it was proposed to my nephew in High School, and he couldn't solve it. FIRST PROBLEM: Set 102 straight lines on a plane, so they intersect in exactly 2002 points. As it is, it's quite difficult to solve -- I guess the professor made a typo when he wrote the problem, so here is a... SECOND PROBLEM: What number would have made that a reasonable High School level problem?

 

The change required is 102 to 103 . Find two factors of 2002 which will add to 103 ( 77 and 26 )

 
Regards
 
Eswaran Narasimhan
------------------------------------------------------
Hi Ed,

I enjoyed the puzzle of the 102 straight lines intersecting in exactly 2002 points.

Answer to part 2 (what would have been a reasonable number). 103 straight lines.
I assume the teacher was looking for two sets of parallel lines and intersecting the
two sets.  Then

A + B = 102 and
A * B = 2002

since the prime factorization of 2002 is 2*7*11*13 the only answer that makes
sense is

26 + 77 = 103 and
26 * 77 = 2002

Answer to part 1.  Lets assume that there are three intersecting sets of parallel lines
and that any point is only the intersection of two lines, then:

A + B + C = 102 and
A*B + B*C + A*C = 2002

This doesn't quite do it as the closest solution for 102 lines is

1 + 25 + 76 = 102 and
1*25 + 25*76 + 1*76 = 2001 points.

However if you move a line so that is passes through existing points then for every
existing point the line passes through it will remove 2 points from the total.  So a 
solution is:

10 + 14 + 78 = 102 and
10*14 + 14*78 + 10*78 = 2012

then moving one line so that is passes though 5 existing points reduces the total to 2002.

Here's a similar puzzle that has a simple solution.  How do you place 90 lines in a plane
so that they intersect in exactly 2002 points.

Regards,

Herb Savage
------------------------------------------------
Hiya...

I'm off by one, I'm afraid; I've got 102 lines forming 2001 intersections.  
It doesn't even qualify as a "suitably difficult" alternate question, I 
fear, but here goes anyway:  Draw 76 parallel lines, then cross them with 25 
lines that are parallel with each other, but perpendicular to the first set. 
  This makes 1900 intersections, with one line left to draw.  If you place 
this last line in any diagonal direction (taking care that it doesn't cross 
at any of the existing intersections), you will create an additional 101 
intersections for a total of 2001.  So what IS the solution for 2002, 
anyway?  My head is killing me.

Thanks for your indulgence, and for continuing to maintain a great Web site.

Inexplicably,
Adam Fromm
----------------------------------------------------
The problem from last week, where 102 lines intersect at 2002 points, was a
neat one.

If it were 103 lines, then an easy answer is a set of 77 parallel lines
crossing a set of 26 parallel lines gives 77*26=2002 intersections.

With 105 lines, none of them parallel, 25 going through a single point and the
other 80 going through a different single point, there are also 80*25+2=2002
intersections.

To use exactly 102 lines, use a set of 25 lines going through a single point,
and a set of 76 parallel lines (not parallel to any of the others, not going
through the first intersection point), which gives 25*76+1 = 1901 intersections
with 25+76=101 lines. Now add a single line that intersects all the others
(i.e. non parallel, not through any previous intersection), to get 2002 points
using 102 lines.

There may be easier ways to do this, but I haven't looked much further.
Jaap Scherphuis
--------------------------------------------------------