Dividing A Set Of Lines
Find the smallest positive integer N that has the following property.
Suppose we have a set of 2 0 1 4 lines in 3 dimensions that pass through the origin, and no plane contains more than three lines. Then we can divide the lines into N groups, so that every line is perpendicular to at most one line in its group.
Details and assumptions
The statement has to be true for any set of 2 0 1 4 lines, and not just a particular set that you chose.
The answer is 2.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
4 solutions
So the other parts of the question are all red herrings . What you need to look at is that there are 3 lines per plane , and In 1 plane , logically , only 2 lines can be perpendicular . Hence answer is 2 .
In any plane, there is infinitely many unique pairs of perpendicular lines that pass through the origin. I think you should develop a more concrete a solution. Also I think this question needs to be more specific. One can find a way of pairing the lines up in more than 2 groups or even 1 group to satisfy the given conditions. Those who found the answer to be 2 seem to have so through insufficient reasoning/guess-work. If one can show that even by the given conditions, there is only 2 such groups or if my claim is wrong, then please do.
I second the perspective that 1 is a sufficient answer. All the lines can be in one group (with each one only being perpendicular to a single other line). I don't see a need to have more than 1 group.
Log in to reply
One collective group could have 3 perpendicular trios (Example : The axes of a 3d graph) . Because of this , we cannot look to 1 as a solution, because the question asks for the lines to be at most perpendicular to 1 other line .
Muhammad , but he did say that provided each plane only has three lines , and also that it has to be perpendicular to something in its own plane
Yeah , but in only one group , 3 lines can be perpendicular to each other .(EG: Axes of a 3 dimensional graph) . Hence 1 cannot be a viable solution as the question asks for a line to be perpendicular to at most 1 line in group .
I do not understand what you are trying to say. Why does that imply that we can split the set of lines into 2 groups, such that each line is perpendicular to at most one line in its group?
Log in to reply
Oh wow, was quite baffled at the question, but yes, here is why 2 is correct: Say you have 2 groups s1, s2 start adding lines to s1 until you find a line is perpendicular to more than 1 line in the set. If so add this line to set s2. s2 will not contain 2 lines which are perpendicular to this newly added line, because then we would have a line which is perpendicular to 4 lines, which would mean that there are more than 3 lines on one plane, which in untrue (by definition). Very nice problem indeed!
Because we eliminated the fact that is we had one group of lines , then lines can be parallel to more than on other line ( 3 dimensional axes for example , are perpendicular to each other ) Hence , we would have to look to the next smallest whole number , which is 2 .
Log in to reply
Precisely, you have not answered the question of why 2 groups will always suffice.
How do you know that given any set of 2014 lines, we can always split them into 2 groups, such that for any line l within group A, it is perpendicular to at most 1 other line in group A? E.g. If 3 of the lines were the coordinate axis, then they can't be in the same group. How do we know that moving one of these lines into the other group doesn't result in other issues?
Log in to reply
@Calvin Lin – Wait , I thought the groups were not subject to change , and that we were looking for the least amount of groups needed to fullfil the question .
Log in to reply
@Aditya Pandey – The groups are not subject to change. You have not provided any description on how to form the groups, and I was playing devil's advocate.
All that you said was "in a plane, only 2 lines can be perpendicular . Hence answer is 2 ." and I don't understand how this constitutes a proof.
Answer is 672.N has to represent minimum number of planes required to achieve the given condition. Question says each palne has to have a maximum of three lines . A particular line can not be perpendicular to more than one line.so we can devide 2014lines into (3x671+1x1) or (3x670+2x2).both are equal to 672.
Log in to reply
Actually , a line can be perpendicular to 2 other lines ( Eg: Look at the axes of a 3 dimensional graph , in which x,y and z are perpendicular . )
Log in to reply
But in a plane(2d) no three lines are perpendicular to each other.
Log in to reply
@Tumuluri V Datta Vamshi – The question is planar , or of many planes , hence it is based in 3d not 2d , He further says that it is in space, which is 3d graph
Log in to reply
@Aditya Pandey – A line in particular group can be perpendicular a line from some other group.
Log in to reply
@Tumuluri V Datta Vamshi – But it has to be perpendicular to one in its own group (Read the question )
Log in to reply
@Aditya Pandey – Lines in different groups can be perpendicular to with no restriction.
A line does not have to be perpendicular to one in its own group. The question says "at most one", not "exactly one".
That's what I first got - 672. But as I got more in to this problem, I found that there exist groupings that may yield additional answers in order to satisfy the conditions of the question. And by conditions I mean: "...and no plane contains more than three lines.." and "...so that every line is perpendicular to at most one line in its group." These conditions imply that a line can be perpendicular to either 0 or 1 line in its group as well as that a plane may have 0, 1, 2, or 3 lines. This yields more than 1 possible case hence various ways of grouping the lines.
Note that the lines in a group do not need to be in the same plane.
N is not the minimum number of planes, but the number of groups.
It is trivially obvious that one group does not suffice since we can easily construct a counterexample. In addition, we will claim that 2 groups will suffice.
Construct a set of 3 axes that are mutually perpendicular and pass through the origin, and rotate them such that none of those axes lie on any of the 2014 lines currently present.
Fill in the plane defined by each pair of axes, 3 planes in total, which will divide the space into 8 "sectors". Notice that, within each sector, no line will be perpendicular to any other, since any angles between the lines must be less than 90 degrees. Notice also that if a line passes through a sector, it will pass through the diametrically opposite sector.
To divide the lines into 2 groups satisfying such requirements, take any two adjacent sectors and their diametrically opposite sectors. These 4 sectors will form one group, and the remaining four sectors the other. (you need to visualise for this part.) Within each group, a line will pass through exactly two of the sectors. It can be perpendicular to only one other line in the group, which will run through the other two sectors. All other possible lines perpendicular to it must be in the other group.
this concludes our proof that N=2 is the minimum.
I like the spatial imagination element of this solution however something seems amiss in the following claim
"It can be perpendicular to only one other line in the group, which will run through the other two sectors. All other possible lines perpendicular to it must be in the other group."
Let's begin with a line L which is in a particular sector S. Now, in your argument you say that this line can be perpendicular to only one more line within the group (where the grouping has been done exactly as you defined it). As you say, L is perpendicular to another line (call it Lp) where Lp lies in the adjacent sector (call it S'). Now, to me it seems that it is possible to have another line (Lp') which is also perpendicular to the initial line L. To see that, visualise the plane perpendicular to L (the initial chosen line). Lp must lie in this plane. Now, there is nothing stopping from another line Lp' to be in this very plane AS WELL AS in the same group (since the plane itself lies in the space of this group). For example, just imagine another line in the plane that makes a small angle epsilon with Lp.
Pretend the 2014 lines form a circle in space. Then there will only be 2 lines on any plane that goes through them. Then I guessed that there should be 2 lines that are perpendicular to each other on the other side of the circle. Therefore, there should be 2 groups that should cut the circle of lines in half.
(The last part is crap. Please comment if you have a better idea to how this should be done.)
I think you meant to say that 2014 lines form a 'sphere' in space...
Log in to reply
If you're viewing from the center of the lines then it looks like a circle. From the side it will look like it is spreading out from the origin.
You may not assume that the set of lines have a special configuration to them. The statement is true for any set of lines.
Otherwise, with your interpretation, it is easy to find a set of 2014 lines, no two of which are perpendicular, and hence they can all fall into the same group.
Log in to reply
consider a particular line.call the lines perpendicular to it as its enemies. a line can have at most three enemies.divide the lines in any two groups.let H denote the total no. of enemies of all lines.suppose on dividing in to groups a particular line has more than one enemy in its group. then transfer it to the other group.it must have at most one enemy there..thus we can reduce the number H all times which is our ultimate problem.
The question is not properly written. Its very difficult to understand what is being asked.
The other (older) solutions that are posted are wrong, because they misinterpret the question.
Let’s recall another famous problem from the Russian Olympiad: Suppose that there are N politicians, each have which have at most 3 enemies. Prove that we can divide the politicians into 2 groups, such that within each group, any politician in that group has at most 1 enemy in that group.
We ignore the proof of this for now, but will relate it to the problem at hand. Let the politicians be our lines, and enemies be pairs of lines that are perpendicular. Since “no plane contains more than 3 lines”, this shows that a line is perpendicular to at most 3 other lines (remember that all the lines pass through the origin). Hence, the conditions of the question are satisfied, and the conclusion is that we can split the lines into 2 groups, such that every line is perpendicular to at most one line in its group.
Proof of Russian Problem: Consider all possible splitting of politicians into 2 groups. Take the splitting which minimizes the total number of enemy pairs within both group. I claim that this will work.
Suppose it doesn’t. This means that there is a politician who has at least 2 enemies in that group. If we move him over to the other group, then we reduce the number of enemy pairs by 2 in the first group, but increase it by 1 in the second group. Thus, this decreases the number of enemy pairs overall, which contradicts the assumption that the number of enemy pairs is a minimum.