3
$\begingroup$

Let $n$ lines in the plane be given such that no two of them are parallel and no three of them have a common point. We want to choose the direction on every line so that the following holds: if we go along any line in its direction and put numbers from 1 to $n-1$ on the intersection points then no two equal numbers appear at the same point. For which numbers $n$ is it possible?

My guess is that, we cannot do it iff when $n$ is even. For the case $n$ is even, I think we should find a point $p$ of intersection of two lines which lies in the middle of two lines (for each of them half of the intersection points in one side of p and the others on the other side of p)

$\endgroup$
  • $\begingroup$ Do you mean, you want to put numbers from 1...n-1 in each line, in order each of the number per line do not get repeated at that line? $\endgroup$ – Brethlosze Jun 25 '17 at 19:36
  • $\begingroup$ @hyprfrco I am pretty sure the OP means: follow a line beginning at one 'end', and number the points of intersection in the order that you encounter them. $\endgroup$ – Bram28 Jun 25 '17 at 19:51
  • $\begingroup$ So is asking if that is possible? Or for a given setup of lines that numbering is possible? Or if there is ax example when that is always possible?? $\endgroup$ – Brethlosze Jun 25 '17 at 19:53
  • $\begingroup$ @hyprfrco That is indeed less clear ... I took it that the OP suspects that it can be done for any odd $n$ and for no even $n$, no matter how the lines are drawn .... And that the OP is asking for some help in proving or disproving that. In my answer I show how the Op's suggested proof that it cannot be done for any even $n$ is not going to work ... But that doesn't mean that there does not exist some other proof of course. $\endgroup$ – Bram28 Jun 25 '17 at 20:00
  • 1
    $\begingroup$ @ hyprfrco, each intersection point lies in exactly on two lines, so to each intersection point is assigned two numbers. The goal is that all the intersection point has two different numbers. but for assigning number you need first choose a direction and then put the numbers along a direction from $1$ to $n-1$. $\endgroup$ – MathFun Jun 26 '17 at 9:51
2
$\begingroup$

My guess is that, we cannot do it iff when n is even.

You could be right! But we'll need a proof ...

For the case n is even, I think we should find a point p of intersection of two lines which lies in the middle of two lines

No, that won't work as a proof, since it is false. Here is a counterexample:

enter image description here

The midpoint for line 1 is where it crosses with line 6

The midpoint for line 2 is where it crosses with line 6

The midpoint for line 3 is where it crosses with line 6

The midpoint for line 4 is where it crosses with line 9

The midpoint for line 5 is where it crosses with line 2

The midpoint for line 6 is where it crosses with line 4

The midpoint for line 7 is where it crosses with line 3

The midpoint for line 8 is where it crosses with line 3

The midpoint for line 9 is where it crosses with line 3

The midpoint for line 10 is where it crosses with line 6

Or, as a graph, where an arrow from $i$ to $j$ means that the midpoint of line $i$ is where it crosses with line $j$:

enter image description here

So: you see that no two lines share the same midpoint!

$\endgroup$
  • 1
    $\begingroup$ I don't understand the downvote ... The OP makes an assertion regarding the even $n$ claim that I demonstrate to be false ... I think that is pretty worthwhile, and without my counterexample, the OP might have spent a good bit of time trying to prove something in a way that I show does not work. $\endgroup$ – Bram28 Jun 25 '17 at 19:16
  • $\begingroup$ I haven't checked all points, but your explanation is definitely not a counterexample. Each intersection belongs to two lines and is hence assigned two number (one for each line, depending on the line's orientation). The OP asks when it's possible to choose orientations such that no intersection is assigned a repeated number. $\endgroup$ – Fimpellizieri Jun 25 '17 at 22:52
  • $\begingroup$ @Fimpellizieri My example is a counterexample to the claim that for even $n$ there will always be two lines that intersect and that have the same midpoint, i.e. that both assign $\frac{n+1}{2}$ to the intersection point that is the middle point of all their intersections. As I explain in my Answer: there are no two lines whose midpoints intersect. As far as the claim goes that the even $n$ cannot be solved: that I don;t know, and I didn't aim for this to be a counterexample for that .. it was merely a counterexample to the more specific claim that two midpoints would always intersect. $\endgroup$ – Bram28 Jun 25 '17 at 23:15
  • $\begingroup$ @Bram28, thank you very much for your time. yes it's a counterexample for the way I proposed how to prove my claim. $\endgroup$ – MathFun Jun 26 '17 at 9:44
  • $\begingroup$ @MathFun You're welcome! It looked like a plausible enough assertion about those midpoints (it seems to hold just fine for up to 8) that I tried to prove it for a while myself ... but wasn't able to :) $\endgroup$ – Bram28 Jun 26 '17 at 11:07
-2
$\begingroup$

In general, any $n$ random lines in the plane will be "almost surely" not crossing them in a common points with three lines.

This is because, $n$ lines have $2n$ variables (i.e. degrees of freedom, DOF), and having a common point shared with three lines imposes a constraint over 1 degree of freedom (for fixing the slope or crossing of just the third line), leaving you with $2n-1$ variables. Hence, the space of solutions of $2n-1$ DOFs in a space of $2n$ DOFs solution. This shows that the required case is not "so common".

Hence, a lot of simple counterexample can be found trivially. For example if we take the tangents to the segment of the unit circle:

  • Take a unit circle,
  • Divide the hemi-circle $(0,\frac\pi2]$ in $\frac{\pi}{2n}$ angle segments, $n$ points,
  • Draw a tangent $\mathscr{L}_i$ at every division point $i=1...n$,
  • The lines $\mathscr{L}_i$ are the requested lines.

Proof:

  • The lines are: $$ \mathscr{L}_i:\frac{y-\sin(\theta_i)}{x-\cos(\theta_i)}=\tan(\theta_i+\frac\pi2)\\ y=-\frac{x}{\tan(\theta_i)}+\frac{1}{\sin^2(\theta_i)} $$ which are all with different slope for any $i$ in $(0,\frac\pi2]$.
  • The crossing are given by: $$ y_{ij}=-\frac{x_{ij}}{\tan(\theta_i)}+\frac{1}{\sin^2(\theta_i)}=-\frac{x_{ij}}{\tan(\theta_j)}+\frac{1}{\sin^2(\theta_j)} $$ which are all different for any given pair of $i,j$. $$ \blacksquare $$
$\endgroup$
  • $\begingroup$ Thank you very much for your time. But, already in the problem assumed any three of them not have a common point!! $\endgroup$ – MathFun Jun 25 '17 at 17:24
  • $\begingroup$ Not any of them have a common point indeed. That requires fixing one DOF. You actually can take any set of lines, and in most of the cases, you will have ${n \choose 2}$ points, without crossing for 3 lines. $\endgroup$ – Brethlosze Jun 25 '17 at 18:08
  • $\begingroup$ We have already!! because in the problem assumed no two of them are parallel. $\endgroup$ – MathFun Jun 25 '17 at 18:22
  • $\begingroup$ I think your question should be rewritten.. i will reply with another answer. $\endgroup$ – Brethlosze Jun 25 '17 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.