Re: hard plane geometry problem
From: Alan Curry (pacman_at_manson.clss.net)
Date: 01/07/04
- Next message: gswork: "Re: Theodore Adorno, a prophet of data systems design"
- Previous message: Randy Howard: "Re: Which programming jobs will not be sent overseas?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 7 Jan 2004 08:03:35 GMT
I have a proof that this problem is unsolvable. I'm using the ideas in Dave
Rusin's post as a starting point, so I'll quote that most of that post first,
in case it's expired from some news servers (it has been a month...)
Warning: this proof is not elegant or enlightening. It's just long.
In article <br4vgi$asa$1@news.math.niu.edu>,
Dave Rusin <rusin@vesuvius.math.niu.edu> wrote:
>In article <bqofrt$62d$1@news.fas.harvard.edu>,
>Ian Andlewin <ia@nospamthanks.com> wrote:
>>I have a hard problem in what I suppose is plane geometry. It might
>>require some machine-assisted computation. Any help would be appreciated.
>
>I worked on this question a little more. I think it has no solution
>but I haven't got a proof. What I'm wondering about, now that I've
>looked at it, is how to phrase the problem and its obstruction elegantly.
>This seems to be a problem in Affine Geometry (or Projective Geometry)
>but I can't quite pinpoint the relevant classical configuration.
>
>Let me explain. You've given quite a few constraints, and asked us
>to draw a picture consistent with all of them. My claim is that the
>data are contradictory, and in fact a contradiction results from a
>rather smaller set of constraints.
>
>You asked us to draw 8 lines in the plane; that we can do. You add a
>tiny constraint that no two be parallel; no problem. That means that
>each pair of lines has a unique point of intersection, giving 28 points
>altogether.
>
>Now, if we label the lines A, B, C, D, E, F, G, H then on each line
>we find the seven points of intersection with the other lines, occurring
>in some order as we read from left to right (or bottom to top). The
>ordering data you provided specify unambiguously the sequence of
>the intersection points on each line. (Your partial order specifies
>more, in fact, but I believe there is already a contradiction from
>this more limited information.) If, as in some cases, we don't really
>care whether the points occur in one order or the reverse order, we can
>note the points of intersection in brackets as you do. Actually, I believe
>there is already a contradiction even if these more relaxed constraints
>are imposed.
>
>Let me illustrate first with two examples. If you wanted us to draw
>three lines A, B, C, then you would have to specify the orderings of
>the intersection points on each line. For example, on line A you might
>want B to be to the left of C, which we could write this way:
> A : B, C
>But if you aren't choosy about whether the points of intersection on
>any particular line show up left-to-right or right-to-left, you might
>write the constraint this way:
> A : [B, C]
>Of course, when there are only three lines, this means the only possible
>set of constraints of this form would be
> A : [B, C]
> B : [A, C]
> C : [A, B]
>and these constraints are satisfiable (e.g. by the lines x=0, y=0, x+y=1).
>
>Next consider an example with four lines. Can we draw lines with these
>incidence data?
> A : [D, B, C]
> B : [D, A, C]
> C : [A, B, D]
> D : [A, C, B]
>I claim not. If we could do this, we could translate the picture so that
>A & B meet at the origin. Applying a linear transformation, we could
>assume A and B are the x- and y- axes, respectively. Applying
>reflections as needed, we could assume C meets these lines above and
>to the right of the origin; applying scalings we could assume C is
>the line x + y = 1. And now where is the line D ? If it meets A at
>the point (x0, 0) and meets B at (0, y0), then the first two
>constraints imply that x0 < 0 and that y0 < 0, respectively. You can
>work out where C and D cross (hint: D is the line x/x0 + y/y0 = 1)
>but you'll find that under these conditions x y < 0, that is, the point
>of intersection is in the second or fourth quadrants; on the other hand
>a point between the other intersection points (x0,0) and (0, y0) would
>lie in the third quadrant. So the constraints on D are incompatible
>with the constraints on A and B . (And I haven't even used the
>constraints on C !)
>
>Note that I am using only the incidence relations of the lines, and
>invariance under the group of affine maps (linear maps and translations);
>that makes this a question of Affine Geometry. With the addition of a
>technical axiom or two, affine geometry really is coordinate geometry
>over some field (a very nice theorem!). We have used nothing else here,
>really, except the condition that the field be ordered. So there ought
>to be some more classical way of stating that there is a contradiction
>here. (It's not Desargues's configuration, nor Pappus's, nor ...
>Whose is it?)
>
>By the way, you can also ask whether the configuration can be constructed
>in Projective Geometry. There, lines have no "ends", so the incidence data
>can be read not only left-to-right or right-to-left, but also with any
>cyclic permutation. In that setting, any four-line problem is solvable
>but I suppose there is a corresponding five-line configuration which is not.
>
>
>After this very long preamble, I can state your problem in this language
>and make some suggestions as to how to prove it impossible. I think I
>would like to name the lines as follows:
> A = your points # 1, 2, 3, 4, 5, 6, 7
> B = 1, 9, 10, 8, 11, 12, 13
> C = 20, 22, 19, 21, 9, 14, 3
> D = 20, 16, 27, 26, 11, 5, 23
> E = 25, 28, 7, 13, 27, 18, 22
> F = 25, 23, 4, 15, 10, 24, 19
> G = 2, 14, 15, 8, 17, 18, 16
> H = 28, 6, 12, 26, 17, 24, 21
>(I've written them in the order they seem to appear in my sketches.)
>Reading either your (corrected) partial orders on the x-coordinates
>or on the y-coordinates, we then have these incidence constraints:
> A : [B, G, C, F, D, H, E]
> B : [A, C, F, G, D, H, E]
> C : [D, E, F, H, B, G, A]
> D : [C, G, E, H, B, A, F]
> E : [F, H, A, B, D, G, C]
> F : [E, D, A, G, B, H, C]
> G : [A, C, F, B, H, E, D]
> H : [E, A, B, D, G, F, C]
Here's where I'll take over... I'm going to use the same notation but I chose
to label the lines differently. My labels are:
A = your points # 1, 2, 3, 4, 5, 6, 7
B = 1, 9, 10, 8, 11, 12, 13
C = 2, 14, 15, 8, 17, 18, 16
D = 20, 22, 19, 21, 9, 14, 3
E = 25, 23, 4, 15, 10, 24, 19
F = 20, 16, 27, 26, 11, 5, 23
G = 28, 6, 12, 26, 17, 24, 21
H = 25, 28, 7, 13, 27, 18, 22
So my ordering constraints are:
A : [B, C, D, E, F, G, H]
B : [A, D, E, C, F, G, H]
C : [A, D, E, B, G, H, F]
D : [A, C, B, G, E, H, F]
E : [D, G, B, C, A, F, H]
F : [D, C, H, G, B, A, E]
G : [D, E, C, F, B, A, H]
H : [D, C, F, B, A, G, E]
Now for the proof...
Part I: Orientation
If there is a solution, it can be oriented through rotation and/or reflection
so that the following conditions are met:
1. Line A is horizontal.
2. Point AB is left of point AC.
3. Point BC is above line A.
(Notation: Point AB is the point where lines A and B intersect. I hope that's
easier to follow than referring to each point by their numbers from the
original post.)
Part II: Segments
Each line can be seen as a series of segments, with a ray on each end. For
example, given this crossing-order specification:
A : [B, C, D, E, F, G, H]
I label the components of line A like this:
A1 A2 A3 A4 A5 A6 A7 A8
<-------.-------.-------.-------.-------.-------.-------.------->
AB AC AD AE AF AG AH
A1 and A8 are rays. A2 through A7 are segments. A2 could also be called AB_AC
since it is the line segment whose endpoints are AB and AC. I'll switch back
and forth between these notations, so watch out...
A2+A3, also known as AB_AD, is also a segment, and segments of that sort are
useful too. It will be important to relate the lengths of segments, for
example:
AB_AF = AB_AE + AE_AF
I'll define two new terms here, to help me explain myself later:
Definition: A "simple segment" is a segment like AB_AC which does not
include any other crossing points in the middle.
Definition: A "compound segment" is a segment like AB_AF which includes more
than one simple segment. In the case of AB_AF, it is crossed by lines C, D,
and E at points AC, AD, and AE.
Part III: Halves
Line A divides the plane into a top half and a bottom half. It will be
important to know which points are in which half. I've already decided point
BC is in the top half. Take a look at line B:
<-------.-------.-------.-------.-------.-------.-------.------->
AB BD BE BC BF BG BH
The left-to-right order of the points on line A is given by one of the original
problem constraints:
B: [A,D,E,C,F,G,H]
Line A crosses line B at the point AB. The other points in that diagram (BD,
BE, BC, BF, BG, and BH) are all on the same side of line A. Since BC is among
them, that means BD, BE, BF, BG, and BH are in the top half of the plane.
Next, a similar look at line C:
<-------.-------.-------.-------.-------.-------.-------.------->
AC CD CE BC CG CH CF
proves that CD, CE, CG, CH, and CF are also on the same side of A as BC,
placing them in the top half of the plane too.
Line D looks like this:
<-------.-------.-------.-------.-------.-------.-------.------->
AD CD BD DG DE DH DF
which shows that DG, DE, DH, and DF are on the same side of A as CD - the top
half of the plane.
Line E looks like this:
<-------.-------.-------.-------.-------.-------.-------.------->
DE GE BE CE AE EF EH
and here you can finally see that there are some points on the other side of
line A. Points BE, CE, and DE were previously shown to be in the top half of
the plane. This line shows that GE is also in the top half, but EF and EH are
on the other side of line A, in the bottom half of the plane.
Line F looks like this:
<-------.-------.-------.-------.-------.-------.-------.------->
DF CF FH FG BF AF EF
The new information here is that FH and FG are on the same side of A as BF -
the top half.
Line G looks like this:
<-------.-------.-------.-------.-------.-------.-------.------->
DG EG CG FG BG AG GH
GH is on the opposite side of line A from BG, so GH must be in the bottom
half of the plane.
All the points have now been located in either the top half or the bottom
half, so there is no need to look at line H, except to check for
inconsistencies, of which there are none. (If you performed this "top half /
bottom half" analysis on Dave Rusin's impossible-to-satisfy 4-line system,
you would find an inconsistency.)
To summarize:
Above line A: BC BD BE BF BG BH CD CE CF CG CH DE DF DG DH EG FG FH
Below line A: EF EH GH
Part IV: Angles
Angles between the lines are central to this proof, so I need a way of naming
them unambiguously. "The angle between lines A and B" is ambiguous because
there are 2 potentially different angles there, and I don't always want the
smaller one.
The angles I want to start with are the ones involving line A.
Definition: angle_X (where X represents A, B, C, D, E, F, G, or H) is one of
the angles between line X and line A - specifically the angle between the ray
that extends rightward on line A from point AX, and the ray that extends
above line A on line X. In the sample below, angle_G is the larger of the 2
angles at point AG.
G
@@
@@
@@
@@ angle_G
@@
...................@@@@@@@@@@@@@@@@@ A
.
.
.
.
.
An equivalent definition: angle_X is the angle between 0 and pi whose tangent
equals the slope of line X. (Note this is not the same as the usual inverse
tangent function, which is defined to take values between -pi/2 and pi/2).
angle_A is 0 by definition.
The location of a point can be used to determine the order of the
angles of the lines that meet at the point. For example, point BC is above
line A, and AB is left of AC, so they form a triangle like this:
BC
/\
/ \
/ \
/ \
/ \
/ \
/ angle_B \ angle_C
.--------------------.--------
AB AC
>From the diagram you can see that angle_C must be greater than angle_B.
A similar diagram can be drawn for points below line A. The general rule is:
[angle rule] If AX is left of AY, and XY is above line A, then angle_Y is
greater than angle_X.
If AX is left of AY, and XY is below line A, then angle_X is
greater than angle_Y.
The full order of angles can be determined by application of this rule to
several points:
Point | Half | Base point order | Conclusion
---------------------------------------------------------
BC | top | AB is left of AC | angle_C > angle_B
CD | top | AC is left of AD | angle_D > angle_C
DF | top | AD is left of AF | angle_F > angle_D
FH | top | AF is left of AH | angle_H > angle_F
EH | bottom | AE is left of AH | angle_E > angle_H
EG | top | AE is left of AG | angle_G > angle_E
In summary:
0 < angle_B < angle_C < angle_D < angle_F < angle_H < angle_E < angle_G < pi
Applying the angle rule to other points would just generate redundant
information like angle_B < angle_D - you can check it for inconsistencies,
but again there are none.
All other angles can be expressed in terms of these "base angles". The angles
between lines X and Y are |X-Y| and pi-|X-Y|.
Part V: Triangles
Choose any 3 lines and they will form a triangle. There are combine(8,3)=56
triangles available. Applying the Law of Sines to a single triangle gives 2
equations, so there are 112 potentially useful equations there.
It turns out I don't need all of them. Just using the triangles that involve
line A, along with the "segment-summing" relationships from Part II, is
enough to express all of the segment lengths in terms of the base angles and
the lengths of the "base segments" (the simple segments on line A). I won't
show all of them here (there are 6 simple segments on every line, for a total
of 42 not including the base segments), but I do need 8 of them to complete
my proof.
1. Triangle ABE:
Since BE is above line A, and AB is left of BE, the triangle looks like this:
BE
/\
/ x \
/ \
Line B / \ Line E
/ \
/ \
/ angle_B y \ angle_E
.--------------------.--------
AB Line A AE
Angle x, the angle between lines B and E, is equal to angle_E - angle_B.
(Proof: angle_E+y = pi = angle_B+x+y)
The Sine Law applied to this triangle says:
AB_AE AB_BE AE_BE
--------------------- = ---------------- = ----------
sin (angle_E-angle_B) sin (pi-angle_E) sin angleB
In general, sin(pi-x) = sin(x). The equation therefore simplifies to:
AB_AE AB_BE
--------------------- = -----------
sin (angle_E-angle_B) sin angle_E
(I have dropped the part about AE_BE because I won't need it.)
Now if I assume for a moment that the angles and the segments on line A were
known, and isolate the remaining variable, it becomes:
AB_BE = AB_AE * sin angle_E / sin (angle_E-angle_B)
>From here on, I'll abbreviate angle_X as just X in formulas like that one, so
it'll look like:
AB_BE = AB_AE * sin E / sin (E-B)
That's the key piece of information to be obtained from triangle ABE.
2. Triangle ABC:
The Sine Law applied to triangle ABC yields this:
AB_BC = AB_AC * sin C / sin (C-B)
Now from the order of points on line B:
<-------.-------.-------.-------.-------.-------.-------.------->
AB BD BE BC BF BG BH
you can see that the distance from AB to BC is greater than the distance from
AB to BE, which means:
AB_BC > AB_BE:
[constraint 1] AB_AC * sin C / sin (C-B) > AB_AE * sin E / sin (E-B)
3. Triangle ABF:
The Sine Law applied to triangle ABF yields this:
AB_BF = AB_AF * sin F / sin (F-B)
AB_BF > AB_BC:
[constraint 2] AB_AF * sin F / sin (F-B) > AB_AC * sin C / sin (C-B)
4. Triangle ABG:
Sine Law:
AB_BG = AB_AG * sin G / sin (G-B)
AB_BG > AB_BF:
[constraint 3] AB_AG * sin G / sin (G-B) > AB_AF * sin F / sin (F-B)
5. Triangle ACH:
Sine Law:
AC_CH = AC_AH * sin H / sin (H-C)
6. Triangle ACF:
Sine Law:
AC_CF = AC_AF * sin F / sin (F-C)
>From line C:
AC_CF > AC_CH
[constraint 4] AC_AF * sin F / sin (F-C) > AC_AH * sin H / sin (H-C)
7. Triangle ADG:
Sine Law:
AD_DG = AD_AG * sin G / sin (G-D)
8. Triangle ADG:
Sine Law:
AD_DE = AD_AE * sin E / sin (E-D)
>From line D:
AD_DE > AD_DG
[constraint 5] AD_AE * sin E / sin (E-D) > AD_AG * sin G / sin (G-D)
Part VI: Putting the pieces together
The constraints established so far are:
[constraint 1] AB_AC * sin C / sin (C-B) > AB_AE * sin E / sin (E-B)
[constraint 2] AB_AF * sin F / sin (F-B) > AB_AC * sin C / sin (C-B)
[constraint 3] AB_AG * sin G / sin (G-B) > AB_AF * sin F / sin (F-B)
[constraint 4] AC_AF * sin F / sin (F-C) > AC_AH * sin H / sin (H-C)
[constraint 5] AD_AE * sin E / sin (E-D) > AD_AG * sin G / sin (G-D)
I want to rewrite them in terms of simple segments, so from the diagram of
line A in Part II:
AB_AC = A2
AB_AE = A2+A3+A4
AB_AF = A2+A3+A4+A5
AB_AG = A2+A3+A4+A5+A6
AC_AF = A3+A4+A5
AC_AH = A3+A4+A5+A6+A7
AD_AE = A4
AD_AG = A4+A5+A6
Here are the 5 constraints, rewritten... along with the angle ordering result
from Part IV and some "obvious" observations. This system of inequalities must
be solved if the original problem can be solved, and in fact it has no
solution.
[c1] A2 * sin C / sin (C-B) > (A2+A3+A4) * sin E / sin (E-B)
[c2] (A2+A3+A4+A5) * sin F / sin (F-B) > A2 * sin C / sin (C-B)
[c3] (A2+A3+A4+A5+A6) * sin G / sin (G-B) > (A2+A3+A4+A5) * sin F / sin (F-B)
[c4] (A3+A4+A5) * sin F / sin (F-C) > (A3+A4+A5+A6+A7) * sin H / sin (H-C)
[c5] A4 * sin E / sin (E-D) > (A4+A5+A6) * sin G / sin (G-D)
[c6] 0 < B < C < D < F < H < E < G < pi
[c7] A2 > 0
[c8] A3 > 0
[c9] A4 > 0
[c10] A5 > 0
[c11] A6 > 0
[c12] A7 > 0
Part VII: Tedium
The rest of this proof uses a lot of tedious algebraic manipulations
to prove that the system c1 through c12 has no solution. There is really
nothing exciting here, so if you're beginning to get bored, this is a good
place to quit reading.
The following trigonometric identities will be useful:
[*] sin a sin (b-c) - sin b sin (a-c) = sin c sin (b-a)
[**] sin (a-b) sin (c-d) - sin (a-d) sin (c-b) = sin (a-c) sin (b-d)
[***] sin (a-b) = - sin (b-a)
The first is a special case of the second with d=0, and they all can be
easily verified by using the standard formula for sine of a difference.
Step 1.
In c1, A2 appears twice. I'd like to have it in there only once.
[c1] A2 * sin C / sin (C-B) > (A2+A3+A4) * sin E / sin (E-B)
A2 * sin C / sin (C-B) > A2 * sin E / sin (E-B) + (A3+A4) * sin E / sin (E-B)
A2 * sin C / sin (C-B) - A2 * sin E / sin (E-B) > (A3+A4) * sin E / sin (E-B)
A2 * [sin C / sin (C-B) - sin E / sin (E-B)] > (A3+A4) * sin E / sin (E-B)
The part in brackets on the left can be simplified put putting the fractions
over a common denominator, then applying the [*] identity.
sin C sin E sin C sin (E-B) - sin E sin (C-B)
--------- - --------- = --------------------------------
sin (C-B) sin (E-B) sin (C-B) sin (E-B)
sin B sin (E-C)
= -------------------
sin (C-B) sin (E-B)
Putting that back in where the brackets were:
A2 * sin B sin (E-C) / (sin (C-B) sin (E-B)) > (A3+A4) * sin E / sin (E-B)
Both sides of that inequality can be divided by sin(E-B). You have to be
careful multiplying or dividing both sides of an inequality by
something -- if that something is negative, the inequality is reversed.
(If a > b and c < 0, then ac < bc). In this case, though, E and B are both
between 0 and pi and E > B, so E-B is also between 0 and pi, which means its
sine is positive. (There will be lots more instances like this where you need
to know whether a sine is positive or negative - I won't go into detail on
all of them. They are all easily determined by the same logic just used. In
most cases when a negative sign shows up, I'll use the [***] identity to
get back to a form with only negatives sines.)
Anyway, the fully simplified c1 looks like this:
[c1] A2 * sin B sin (E-C) / sin (C-B) > (A3+A4) * sin E
I want to do the same thing to c2 through c5 (combine instances of variables
that appear twice). The transformations are all very similar, so I won't
write them all out. They all involve a substitution of this form:
sin a / sin (a-c) - sin b / sin (b-c) = sin c sin (b-a) / (sin (a-c) sin (b-c))
The results are:
[c1] A2 * sin B sin (E-C) / sin (C-B) > (A3+A4) * sin E
[c2] (A3+A4+A5) * sin F > A2 * sin B sin (F-C) / sin (C-B)
[c3] A6 * sin G > (A2+A3+A4+A5) * sin B sin (G-F) / sin (F-B)
[c4] (A3+A4+A5) * sin C sin (H-F) / sin (F-C) > (A6+A7) * sin H
[c5] A4 * sin D sin (G-E) / sin (E-D) > (A5+A6) * sin G
[c12] A7 > 0
Step 2.
Notice that in Part I, the orientation of the lines was decided, but the
scale was not mentioned. I will define the scale so that A2=1 (all lengths
are measured as multiples of the distance between AB and AC).
With A2=1, the constraints become:
[c1] sin B sin (E-C) / sin (C-B) > (A3+A4) * sin E
[c2] (A3+A4+A5) * sin F > sin B sin (F-C) / sin (C-B)
[c3] A6 * sin G > (1+A3+A4+A5) * sin B sin (G-F) / sin (F-B)
[c4] (A3+A4+A5) * sin C sin (H-F) / sin (F-C) > (A6+A7) * sin H
[c5] A4 * sin D sin (G-E) / sin (E-D) > (A5+A6) * sin G
[c12] A7 > 0
Step 3.
I will now do a series of "isolate and combine" transformations. The general
procedure is: choose 2 inequalities from the list, and choose a variable that
appears in both of them. Isolate that variable in both, so you have:
x < (something)
x > (another thing)
Then combine those to reveal:
(another thing) < (something)
After each step I'll show all inequalities again as a group, excluding the
ones that I won't be using.
I'll start with several "isolations". Isolate A4 in c1; A5 in c2 and c3; A6
in c4 and c5; and make another copy of c3, label it c13, and isolate A6
there.
[c1] sin B sin (E-C) / sin E sin (C-B) - A3 > A4
[c2] A5 > sin B sin (F-C) / sin F sin (C-B) - (A3+A4)
[c3] A6 * sin G sin (F-B) / sin B sin (G-F) - (1+A3+A4) > A5
[c4] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C) - A7 > A6
[c5] A4 * sin D sin (G-E) / sin G sin (E-D) - A5 > A6
[c8] A3 > 0
[c12] A7 > 0
[c13] A6 > (1+A3+A4+A5) * sin B sin (G-F) / sin G sin (F-B)
Next combine c2 with c3 to get the new c2:
[c1] sin B sin (E-C) / sin E sin (C-B) - A3 > A4
[c2] A6 * sin G sin (F-B) / sin B sin (G-F) - (1+A3+A4) >
sin B sin (F-C) / sin F sin (C-B) - (A3+A4)
[c3] A6 * sin G sin (F-B) / sin B sin (G-F) - (1+A3+A4) > A5
[c4] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C) - A7 > A6
[c5] A4 * sin D sin (G-E) / sin G sin (E-D) - A5 > A6
[c8] A3 > 0
[c12] A7 > 0
[c13] A6 > (1+A3+A4+A5) * sin B sin (G-F) / sin G sin (F-B)
And isolate A6 in c2. The A3's and A4's cancel out nicely.
[c1] sin B sin (E-C) / sin E sin (C-B) - A3 > A4
[c2] A6 >
(sin B sin (F-C) / sin F sin (C-B) + 1) * sin B sin (G-F) / sin G sin (F-B)
[c3] A6 * sin G sin (F-B) / sin B sin (G-F) - (1+A3+A4) > A5
[c4] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C) - A7 > A6
[c5] A4 * sin D sin (G-E) / sin G sin (E-D) - A5 > A6
[c8] A3 > 0
[c12] A7 > 0
[c13] A6 > (1+A3+A4+A5) * sin B sin (G-F) / sin G sin (F-B)
The right side of c2 can be simplified by this method:
sin B sin (F-C) sin B sin (F-C) + sin F sin (C-B)
--------------- + 1 = ---------------------------------
sin F sin (C-B) sin F sin (C-B)
(apply the [*] identity to the numerator)
sin B sin (F-C) sin C sin (F-B)
--------------- + 1 = ---------------
sin F sin (C-B) sin F sin (C-B)
When the result is substituted in c2, there are 2 instances of sin(F-B) which
cancel out, leaving c2 fairly simple.
[c1] sin B sin (E-C) / sin E sin (C-B) - A3 > A4
[c2] A6 > sin C sin B sin (G-F) / sin G sin F sin (C-B)
[c3] A6 * sin G sin (F-B) / sin B sin (G-F) - (1+A3+A4) > A5
[c4] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C) - A7 > A6
[c5] A4 * sin D sin (G-E) / sin G sin (E-D) - A5 > A6
[c8] A3 > 0
[c12] A7 > 0
[c13] A6 > (1+A3+A4+A5) * sin B sin (G-F) / sin G sin (F-B)
Now combine c5 with c13, to get the new c5:
[c1] sin B sin (E-C) / sin E sin (C-B) - A3 > A4
[c2] A6 > sin C sin B sin (G-F) / sin G sin F sin (C-B)
[c3] A6 * sin G sin (F-B) / sin B sin (G-F) - (1+A3+A4) > A5
[c4] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C) - A7 > A6
[c5] A4 * sin D sin (G-E) / sin G sin (E-D) - A5 >
(1+A3+A4+A5) * sin B sin (G-F) / sin G sin (F-B)
[c8] A3 > 0
[c12] A7 > 0
Isolate A5 in c5 (here's where it starts to get really ugly. I'm not going to
show all the small steps from here on; there are just too many. Mostly it
consists of applying the [*] identity or those that were derived from it, and
paying close attention to the signs of the sines: sin(B-F), for example, is
negative.)
A4 * sin D sin (G-E) / sin (E-D) - A5 * sin G >
(1+A3+A4+A5) * sin B sin (G-F) / sin (F-B)
A4 * (sin D sin (G-E) / sin (E-D) - sin B sin (G-F) / sin (F-B))
- (1+A3) * sin B sin (G-F) / sin (F-B) > A5 * sin F sin (G-B) / sin (F-B)
A4 * (sin D sin (G-E) / sin (E-D) - sin B sin (G-F) / sin (F-B))
- (1+A3) * sin B sin (G-F) / sin (F-B) > A5 * sin F sin (G-B) / sin (F-B)
A4 * ( sin D sin (G-E) sin (F-B) / sin F sin (G-B) sin (E-D)
- sin B sin (G-F) / sin F sin (G-B) )
- (1+A3) * sin B sin (G-F) / sin F sin (G-B) > A5
[c1] sin B sin (E-C) / sin E sin (C-B) - A3 > A4
[c2] A6 > sin C sin B sin (G-F) / sin G sin F sin (C-B)
[c3] A6 * sin G sin (F-B) / sin B sin (G-F) - (1+A3+A4) > A5
[c4] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C) - A7 > A6
[c5] A4 * ( sin D sin (G-E) sin (F-B) / sin F sin (G-B) sin (E-D)
- sin B sin (G-F) / sin F sin (G-B) )
- (1+A3) * sin B sin (G-F) / sin F sin (G-B) > A5
[c8] A3 > 0
[c12] A7 > 0
Combine c4 with c2 to get the new c2, and isolate A7 there:
[c1] sin B sin (E-C) / sin E sin (C-B) - A3 > A4
[c2] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C)
- sin C sin B sin (G-F) / sin G sin F sin (C-B) > A7
[c3] A6 * sin G sin (F-B) / sin B sin (G-F) - (1+A3+A4) > A5
[c4] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C) - A7 > A6
[c5] A4 * ( sin D sin (G-E) sin (F-B) / sin F sin (G-B) sin (E-D)
- sin B sin (G-F) / sin F sin (G-B) )
- (1+A3) * sin B sin (G-F) / sin F sin (G-B) > A5
[c8] A3 > 0
[c12] A7 > 0
Combine c2 with c12 to get the new c2:
[c1] sin B sin (E-C) / sin E sin (C-B) - A3 > A4
[c2] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C)
- sin C sin B sin (G-F) / sin G sin F sin (C-B) > 0
[c3] A6 * sin G sin (F-B) / sin B sin (G-F) - (1+A3+A4) > A5
[c4] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C) - A7 > A6
[c5] A4 * ( sin D sin (G-E) sin (F-B) / sin F sin (G-B) sin (E-D)
- sin B sin (G-F) / sin F sin (G-B) )
- (1+A3) * sin B sin (G-F) / sin F sin (G-B) > A5
[c8] A3 > 0
Isolate A5 in c2:
[c1] sin B sin (E-C) / sin E sin (C-B) - A3 > A4
[c2] A5 >
sin B sin (G-F) sin H sin (F-C) / sin (H-F) sin G sin F sin (C-B) - (A3+A4)
[c3] A6 * sin G sin (F-B) / sin B sin (G-F) - (1+A3+A4) > A5
[c4] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C) - A7 > A6
[c5] A4 * ( sin D sin (G-E) sin (F-B) / sin F sin (G-B) sin (E-D)
- sin B sin (G-F) / sin F sin (G-B) )
- (1+A3) * sin B sin (G-F) / sin F sin (G-B) > A5
[c8] A3 > 0
Combine c2 with c5 to form the new c2, and isolate A4 there:
[c1] sin B sin (E-C) / sin E sin (C-B) - A3 > A4
[c2] A4 >
sin B sin (G-F) sin H sin (F-C) sin (G-B) sin (E-D)
/ sin E sin (G-D) sin (F-B) sin (H-F) sin G sin (C-B)
+ sin B sin (G-F) sin (E-D) / sin E sin (G-D) sin (F-B)
- A3 * sin G sin (E-D) / sin E sin (G-D)
[c3] A6 * sin G sin (F-B) / sin B sin (G-F) - (1+A3+A4) > A5
[c4] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C) - A7 > A6
[c5] A4 * ( sin D sin (G-E) sin (F-B) / sin F sin (G-B) sin (E-D)
- sin B sin (G-F) / sin F sin (G-B) )
- (1+A3) * sin B sin (G-F) / sin F sin (G-B) > A5
[c8] A3 > 0
Combine c2 with c1 to form the new c2, and isolate A3 there.
[c1] sin B sin (E-C) / sin E sin (C-B) - A3 > A4
[c2] sin B sin (E-C) sin (G-D) / sin D sin (G-E) sin (C-B)
- sin B sin (G-F) sin H sin (F-C) sin (G-B) sin (E-D)
/ sin D sin (G-E) sin (F-B) sin (H-F) sin G sin (C-B)
- sin B sin (G-F) sin (E-D) / sin D sin (G-E) sin (F-B) > A3
[c3] A6 * sin G sin (F-B) / sin B sin (G-F) - (1+A3+A4) > A5
[c4] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C) - A7 > A6
[c5] A4 * ( sin D sin (G-E) sin (F-B) / sin F sin (G-B) sin (E-D)
- sin B sin (G-F) / sin F sin (G-B) )
- (1+A3) * sin B sin (G-F) / sin F sin (G-B) > A5
[c8] A3 > 0
Combine c2 with c8 to form the new c2:
[c1] sin B sin (E-C) / sin E sin (C-B) - A3 > A4
[c2] sin B sin (E-C) sin (G-D) / sin D sin (G-E) sin (C-B)
- sin B sin (G-F) sin H sin (F-C) sin (G-B) sin (E-D)
/ sin D sin (G-E) sin (F-B) sin (H-F) sin G sin (C-B)
- sin B sin (G-F) sin (E-D) / sin D sin (G-E) sin (F-B) > 0
[c3] A6 * sin G sin (F-B) / sin B sin (G-F) - (1+A3+A4) > A5
[c4] (A3+A4+A5) * sin C sin (H-F) / sin H sin (F-C) - A7 > A6
[c5] A4 * ( sin D sin (G-E) sin (F-B) / sin F sin (G-B) sin (E-D)
- sin B sin (G-F) / sin F sin (G-B) )
- (1+A3) * sin B sin (G-F) / sin F sin (G-B) > A5
[c8] A3 > 0
c2 now says:
sin B sin (E-C) sin (G-D) / sin D sin (G-E) sin (C-B)
- sin B sin (G-F) sin H sin (F-C) sin (G-B) sin (E-D)
/ sin D sin (G-E) sin (F-B) sin (H-F) sin G sin (C-B)
- sin B sin (G-F) sin (E-D) / sin D sin (G-E) sin (F-B) > 0
(Note: all the sines shown there are positive.)
(Note 2: A2, A3, A4, A5, and A6 have all been removed, and the rest of the
proof deals only with angles, and will show that the above condition is
incompatible with the order 0 < B < C < D < F < H < E < G < pi)
All 3 terms in the expression can be divided by sin(B) and multiplied by
sin(D)*sin(G-E), simplifying it to:
sin (E-C) sin (G-D) / sin (C-B)
- sin (G-F) sin H sin (F-C) sin (G-B) sin (E-D)
/ sin (F-B) sin (H-F) sin G sin (C-B)
- sin (G-F) sin (E-D) / sin (F-B) > 0
Get rid of all the fractions by multiplying by
sin(G)*sin(F-B)*sin(H-F)*sin(C-B) and it becomes:
sin (E-C) sin (G-D) sin G sin (F-B) sin (H-F)
- sin (G-F) sin H sin (F-C) sin (G-B) sin (E-D)
- sin (G-F) sin (E-D) sin G sin (H-F) sin (C-B) > 0
sin G sin (E-C) sin (G-D) sin (F-B) sin (H-F) >
sin H sin (G-F) sin (E-D) sin (F-C) sin (G-B)
+ sin G sin (G-F) sin (E-D) sin (C-B) sin (H-F)
Apply [*] to sin H sin (G-F):
sin G sin (E-C) sin (G-D) sin (F-B) sin (H-F) >
[sin F sin (G-H) + sin G sin (H-F)] sin (E-D) sin (F-C) sin (G-B)
+ sin G sin (G-F) sin (E-D) sin (C-B) sin (H-F)
Expand:
sin G sin (E-C) sin (G-D) sin (F-B) sin (H-F) >
sin F sin (G-H) sin (E-D) sin (F-C) sin (G-B)
+ sin G sin (H-F) sin (E-D) sin (F-C) sin (G-B)
+ sin G sin (G-F) sin (E-D) sin (C-B) sin (H-F)
Refactor:
sin G sin (E-C) sin (G-D) sin (F-B) sin (H-F) >
sin F sin (G-H) sin (E-D) sin (F-C) sin (G-B)
+ sin G sin (H-F) sin (E-D) [sin (F-C) sin (G-B) + sin (C-B) sin (G-F)]
Apply [**] to the bracketed expression:
sin G sin (E-C) sin (G-D) sin (F-B) sin (H-F) >
sin F sin (G-H) sin (E-D) sin (F-C) sin (G-B)
+ sin G sin (H-F) sin (E-D) sin (F-B) sin (G-C)
Move the last term back to the left side:
sin G sin (E-C) sin (G-D) sin (F-B) sin (H-F)
- sin G sin (H-F) sin (E-D) sin (F-B) sin (G-C) >
sin F sin (G-H) sin (E-D) sin (F-C) sin (G-B)
Factor the left side:
sin G sin (H-F) sin (F-B) [sin (E-C) sin (G-D) - sin (E-D) sin (G-C)] >
sin F sin (G-H) sin (E-D) sin (F-C) sin (G-B)
Apply [**] to the bracketed expression, and rearrange a bit:
sin G sin (F-B) / sin F sin (G-B) >
sin (G-H) sin (E-D) sin (F-C) / sin (H-F) sin (G-E) sin (D-C)
Apply [*] sin F sin (G-B) - sin B sin (G-F) = sin G sin (F-B)
[sin F sin (G-B) - sin B sin (G-F)] / sin F sin (G-B) >
sin (G-H) sin (E-D) sin (F-C) / sin (H-F) sin (G-E) sin (D-C)
1 - sin B sin (G-F) / sin F sin (G-B) >
sin (G-H) sin (E-D) sin (F-C) / sin (H-F) sin (G-E) sin (D-C)
Since all the sines are positive, the left side is 1 minus a positive number,
meaning it's less than 1. The right side is even less than that, so it must
also be less than 1.
sin (G-H) sin (E-D) sin (F-C) / sin (H-F) sin (G-E) sin (D-C) < 1
sin (G-H) sin (E-D) sin (F-C) < sin (H-F) sin (G-E) sin (D-C)
Notice B has disappeared. The end is getting closer. I can get rid of another
one just by defining a new set of variables like this:
c = C - C = 0
d = D - C
e = E - C
f = F - C
g = G - C
h = H - C
The order of d,e,f,g,h corresponds to the order of D,E,F,G,H:
0 < d < f < h < e < g < pi
And now I'll make another observation about that order, which will be userful
shortly. Between 0 and pi, The cotangent function is continuous and
decreasing. The cotangents of the angles are therefore ordered in the
opposite direction:
cot d > cot f > cot h > cot e > cot g
(The tangents are less useful because tan(x) is discontinuous at x=pi/2)
Now back to the main inequality. In terms of the new variables, it looks like
this:
sin (g-h) sin (e-d) sin f < sin (h-f) sin (g-e) sin d
sin (g-h) sin e cos d sin f - sin (g-h) cos e sin d sin f <
sin (h-f) sin (g-e) sin d
sin (g-h) sin e sin f cos d <
[sin (g-h) cos e sin f + sin (h-f) sin (g-e)] sin d
cot d < [sin (g-h) cos e sin f + sin (h-f) sin (g-e)] / [sin (g-h) sin e sin f]
Now because cot f < cot d:
cot f < [sin (g-h) cos e sin f + sin (h-f) sin (g-e)] / [sin (g-h) sin e sin f]
cos f sin (g-h) sin e < sin (g-h) cos e sin f + sin (h-f) sin (g-e)
cos f sin (g-h) sin e - sin (g-h) cos e sin f < sin (h-f) sin (g-e)
sin (g-h) [cos f sin e - cos e sin f] < sin (h-f) sin (g-e)
sin (g-h) sin (e-f) < sin (h-f) sin (g-e)
By way of [**]:
sin (g-e) sin (h-f) - sin (g-f) sin (h-e) < sin (h-f) sin (g-e)
- sin (g-f) sin (h-e) < 0
sin (g-f) sin (h-e) > 0
But sin(g-f) is positive and sin(h-e) is negative; it's over. No solution
exists.
-- Alan Curry pacman@clss.net
- Next message: gswork: "Re: Theodore Adorno, a prophet of data systems design"
- Previous message: Randy Howard: "Re: Which programming jobs will not be sent overseas?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
