Забыли?

?

# How to find the best point and the shortest web Team: Mathoe The

код для вставки
```How to find the best point and the shortest web
Team: Mathoe
The member of the team: Yuan Zhang (female) :
Guangdong Experimental High School
Bingjie Wu: Webmaster of mathoe Grade two
www.mathoe.com
No.168 Guangzhou 511442
Tutor
Qiyin Li (the chairman of mahtoe website)
Introduction
This paper is motivated by a report: assume we span the telephone lines among
Beijing, Shanghai and XiвЂ™an, one way is to connect Beijing----- Shanghai and
Beijing-----XiвЂ™an, another one is to choose the fourth point, for example, Zhengzhou.
Therefore, wiring telephone lines to the three cities respectively, you will never suggest
that the phone lines which the second method uses is just 86.6 percent of that the first
method uses. Hence, the second method may get more (13.3 percent ) remarkable
economic efficiency than the first one. Once Wu Bingjie made the panels by the report as
the main contents, going to Hongkong Diocesan girls to show his panels on behalf of our
school. Hence this actuates us to consider the problem.
Abstract
The aim of this paper is how to look for the best
point connecting all points the total distance is the minimum and the minimum connected
graph. This paper begins with the famous Fermat points, and then solves the weighted
Steiner problem by a physical model, i.e., finding a point connecting the known finite
points in the plane, the total
distance is minimum and finding its weighted form. Then we consider it from the
mathematics, and look for the formula of the weighted Fermat points and it's the shortest
length by computation. Hereafter, we solve the generalized final title of Beijing high school
applied mathematics competition about laying the land.
But we know these Engineering problems still have many questions to be solved in the
real problems. If many points are given, it is very difficult to solve this problem by the
mathematical method.
Our key is the approximation method, i.e., we seek the web instead of seeking the
point. Based on the special square, we explore the way of connecting four points Steiner
tree, then generalize the proof of Pollark theorem. But, we still have no idea for five or
more points. By KruskalвЂ™s algorithm, i.e., an algorithm in graph theory that finds a
minimum spanning tree for a connected weighted graph, we think that the ratio the length
of the tree to the length of the ideal must be in a scale after comparing the three points
with four points. This is the famous Steiner ratio conjecture.
In 1982, Du Dingzhu proved this conjecture in a paper titled as вЂњTalking about the
proof of G-P TheoremвЂќ which was published in the Dissemination of mathematics (Vol 17
(No 4)). After reading DuвЂ™s paper and Zhao MinyiвЂ™s paper, we decide to prove the Steiner
ratio conjecture from the view of middle school students, similar to the proof of Zhao Minyi.
Keywords
he weighted Steiner problem, Pollark Theorem, KruskalвЂ™s algorithm
the Steiner ratio conjecture and its proof, seeking the optimization point,
construct the optimization network
Contents
As is known to us that the famous problem is Fermat point problems.:
As the following figure, A, B, C are three factories, they construct an acute triangle, we
built a gas station. Show that when the perspectives of the gas station to each two factory
are equal (120 degree), the pipeline we need pave is the minimum possible.
Analysis: An acute triangle ABC, where в€ AMB = в€ BMC = в€ CMA = 120В° , P be
any point which is different from the point M. Let d(P)=PA+PB+PC,
d(M)=MA+MB+MC, it is very difficult to prove d(M)<d(P). In fact, by the suitable
transformation, let the line segments MA,MB and MC are on a line, and the first and end
point link a line segment. At the same time, let the line segments PA,PB and PC links a
broken line which has the same first and end point as the line segment.
Then the problem is solved. It is easy to prove the next theorem.
R
A
K
S
Q
M
P
B
C
In fact, a point M be a Fermat point inside the triangle ABC, when the angle at A is
120 degree, the Fermat point is the point A, it is easy to prove it.
Naturally, we will think how to find a point inside a plane such that the total distance
from the finite vertices to the point is the minimum possible. At first, we find it difficult to
attempt to look for it directly. In fact, it is easy to solve the problem by the physical
model we have known.
We may solve this mathematical problem by Physical method. The Physical method,
is to describe a mathematical problem using a suitable physical model, and then certain
the solution of the problem in terms of the physical principles. In the physical method of
an external problem, the usual physical principle is Minimum Potential Energy Principle
(when a mechanical systems is static, its potential energy is the minimum) and the
Principle of LightвЂ™s Swiftest Speedпј€in the optical media, the distance of the light from A
й�џеђЌпјљmathoe
to B is the minimum length of all the curves connecting A and Bпј‰. Next, we first solve the
Fermat problem and connecting many points problem by Minimum Potential Energy
Principle.
We fix another endpoint of the three elastic thread whose points are the same on the
three vertexes in the triangle ABC, when the mechanical system is in balance, the
potential energy is the minimum. The potential energy may be described by the length
of the thread (in the elastic , the elastic force is proportion to the length), i.e.,
PA+PB+PC is the minimum. Furthermore, if the system is in balance, P is not some
vertex (the triangle ABC is an acute triangle, otherwise, an angle at some point is в‰Ґ120
degree, P is this vertex ) . The elastic force acted on P has three equal forces
T1 , T2 , T3 ,
their total force is zero. Hence we have
в€ APB = в€ BPC = в€ CPA = 120o . Therefore, P is the Fremat point of the triangle
ABC.Generalizing this problem: for any arbitrary given n points
A1 пјЊвЂ¦вЂ¦, An .How
n
to find a point such that
в€‘ AP
i
is the minimum possible, where AiP denotes the
i =1
distance from
Ai to
P. We may also design a simple machinery to find P.
A2
O
A1
An
q2
q1
qn
qn-1
In fact, we can solve the weighted point problem by this model which belongs to the
general of the Steinhaus problem.
Assume there are n points Ak in the plane, the weight of every point (which may be
seen as the quantity of a person or an object) is
qk
(k=1,2, вЂ¦вЂ¦пјЊn). Now we need to
find a point
o such that the sum of the product of rk and qk
Assume that every threadвЂ™s length is
lk
respectively, obviously,
l,
lk = l в€’ rk пјЊ
is the minimum possible.
the length of every thread under the flat is
then the total potential energy of this system
n
в€‘ q (h в€’ l )
i
i
is the minimum (h is the height of the flat to the ground), i.e., the triangle
i =1
A ' B ' C ' is the maximal. When the system is in balance,
n
в€‘ql
n
n
i i
is the maximum, on the other handпјЊ l
i =1
в€‘q
i
is a given value. Hence,
is the minimum, if the system is in balance, i.e.,
o
в€‘qr
i i
i =1
i =1
is the point we need.
After all, this is only a physical model, we still need to compute it by the mathematical
method. Without loss of general, we compute it from the weighted three points.
This problem is for any given three positive number a1 пјЊ a2 пјЊ a3 and three points
A1 , A2 , A3
in the plane, how to find a point F such that in the plane,
a1 A1 P + a2 A2 P + a3 A3 P is the minimum. We say that the point F of the problem is
Fermat point. The specific practices as follows:
Assume the three sides whose lengths are a, b,c
respectively can construct a
triangle, denoted as в–і A ' B ' C ' , its interior angles are A ' B ' C ' . There is another
triangle ABC, its sides are also a, b, c respectively.
(1) If A + A ' гЂЃ B + B ' гЂЃ C + C ' has at least one is larger than 180В°, without loss of
general, A + A ' в‰Ґ180В°. Then A is Fermat point, the minimum value is b ' c + c ' b .
(2) If A + A ' гЂЃ B + B ' гЂЃ C + C ' are less than 180В°, then there exists a point
inside the triangle ABC such that
в€ BFC = 180o в€’ A ' пјЊ в€ CFA = 180o в€’ B ' пјЊ в€ AFB = 180o в€’ C ' пјЊ and a point F is
Fermat point.
We say that a point F in (2) is non-trivial Fermat point, we can get it as follows.
Do a triangle BCP towards the outside of the side BC such that в€ CBP = B ' пјЊ
в€ BCP = C ' . Linking AP, then the intersection point of AP and the circumscribed circle of
в–і BCP .
P
B
F
A
C
Next, we show this connected length precisely.
If F is not Fermat point, then
a 'в‹… PB = c 'в‹… BC
1
2 2 2
вЋЎ a ( b ' + c '2 в€’ a '2 ) + b 2 ( a '2 + c '2 в€’ b '2 ) + c 2 ( b '2 + a '2 в€’ c '2 ) + 16 SS 'вЋ¤ 2
=
вЋ¦
2 вЋЈ
where S , S
Proof:
'
are the areas of О”ABC гЂЃ О”A ' B ' C ' respectively.
F , B, P , C
may construct a circle, by Ptolemy Theorem,
PC в‹… FB + PB в‹… FC = BC в‹… PF
(2)
It is easy to see that
в–і BCP в€Ѕв–і A ' B ' C ' , we have
PC PB BC
=
=
b'
c'
a'
в€ґ a 'в‹… PC = b 'в‹… BC ,в€ґ a 'в‹… PB = c 'в‹… BC ,
Taking it to (2), we have
b 'в‹… FB + c 'в‹… FC = a 'в‹… FP , hence
в€ґ l пјќ a 'в‹… FA + a 'в‹… FP = a 'в‹… AP
In the triangle PCA , by the Cosine theorem,
a '2 в‹… AP 2 = a '2 в‹… AC 2 + a '2 в‹… PC 2 в€’ 2a '2 в‹… AC в‹… PC в‹… cos ( C + C ')
Hence, we have,
l 2 = a '2 b2 + b '2 a 2 в€’ 2aa ' bb 'cos ( C + C ') .
(3)
(1)
teamпјљmathoe
1
Notice that, S ' = a ' b 'sin C '
2
cos C =
a2 + b2 в€’ c2
2ab
cos C ' =
a '2 + b '2 в€’ c '2
2a ' b '
Taking the above to (3), then we get (1).
In fact similarly solving external value problems are useful in the nonlinear programming in
the real life. For example, this problem is the final title of the second session of the Beijing
school of applied mathematics knowledge contest finals.
The analysis computation of mathematics make it easy to solve the problem directly.
There is a river, the factories P, Q lie in the same side of the river bank, the known
coordination of two factories P
( a, b ) , Q ( c, d ) пј€ a пјЊ b пјЊ c пјЊ d
be nonnegative
constantsпјЊ a пјњ c пј‰. Now we plan to choose a point R on the side of the factories. A
hydropower will be built at R and the line
water pipe will be built from R to the river bank
and the factories respectivelyпјЋIf the cost of building per km water pipe between the
hydropower and the total water pipe is
pipe from R to P, Q respectively is
О» пј€ О» пјћ0пј‰YuanпјЊthe cost of building per water
u Yuan and v Yuanпј€ u пјЊ v пјћ0пј‰. Choose the place
of R such that the total cost of building water pipes is the minimum,and obtain the cost.
Solve: Let the hydropower be R ( x, y ) пј€0в‰¤ a в‰¤ x в‰¤ c пјЊ y в‰¤ b пјЊ y в‰¤ d пј‰,
the total cost of building hydropower is О»TR + uRP + vRQ ,
i.e., f ( x, y ) = О» y + u
( x в€’ a ) + (b в€’ y )
2
2
+v
(c в€’ x) + ( d в€’ y)
2
2
(1)
P(a,b)
Q(c,d)
R
A
в‘ If О» в‰Ґ u + v пјћ0пјЊliking
T
C
x
TP , TQ , the total cost of building water pipes is
О»TR + uRP + vRQ в‰Ґ ( u + v ) TR + uRP + vRQ пјќ u ( RP + TR ) + v (TR + RQ )
пјћ uTR + vTQ гЂ‚
The above inequality shows that, we need not built the total water pipe TR, Water
pump built on the river bank i.e., axis of x. At the same time y = 0 ,
The function (1) becomes
f ( x, 0 ) = u
( x в€’ a)
2
+ b2 + v
(c в€’ x)
2
+ d2
Team:mathoe
1
1
By the refraction of light theorem, = u ,
= v , we have u sin Оё 1 = v sin Оё 2
c1
c2
Where
Оё1 = в€ PTR , Оё 2 = в€ RTQ ,then the hydropower should be built on the bank
AC, and closed to the factory which need the higher cost of building water pipe per
km.
в‘ЎIf u + v пјћ О» пјћ u , v пјћ0,by seeking extreme value, (1) may be written as
f ( x, y ) в‰Ґ u ( x в€’ a ) 1 в€’ m2 + v ( c в€’ x ) 1 в€’ n2 + umb + vnd
пјќ ( c в€’ a ) u 1 в€’ m + umb + vnd
2
Where
m, n
are undetermined constants whose absolute values are less than 1
and satisfy
вЋ§вЋЄum + vn = О»
вЋЁ
2
2
вЋЄвЋ©u 1 в€’ m = v 1 в€’ n
пј€2пј‰
1
вЋ§
2
2
2
вЋЄвЋЄm = 2О»u ( О» + u в€’ v )
By(2), вЋЁ
вЋЄn = 1 ( О» 2 в€’ u 2 + v 2 )
2О» u
пј€3пј‰
inпј€3пј‰пјЊobviously, m пјћ0пјЊ n пјћ0пјЊwe compute 1 в€’ m
пјќ
( 2О» u в€’ О»
2О» u
1
2
в€’ u 2 + v2 ) пјќ
1 вЋЎ 2
1
2
v в€’ (О» в€’ u ) вЋ¤ пјќ
v + О» в€’ u )( v в€’ О» + u ) в‰Ґ0
вЋ¦ 2О» u (
2О» u вЋЈ
Hence,0пјњ m пјњ1.
similarly, 0пјњ n пјњ1.
Hence the function f(x,y) has a minimum,
f ( x, y ) в‰Ґ u ( x в€’ a ) 1 в€’ m2 + v ( c в€’ x ) 1 в€’ n2 + umb + vnd
пјќ ( c в€’ a ) u 1 в€’ m + umb + vnd
2
вЋ§
( x в€’ a) m
вЋЄy в€’b = в€’
1 в€’ m2
вЋЄ
вЋЁ
вЋЄ y в€’ d = в€’ (c в€’ x) n
вЋЄ
1 в€’ n2
вЂњпјќвЂќholds if and only if
(4).
teamпјљmathoe
вЋ§
( x в€’ a) m
вЋЄb в€’ y = в€’
1 в€’ m2
вЋЄвЋЄ
Takingпј€2пј‰into(4) we have вЋЁ
nv
(c в€’ x)
вЋЄ
u
вЋЄd в€’ y = в€’
2
1в€’ m
вЋ§
amu + cnv ( b в€’ d ) u
1 в€’ m2
+
вЋЄx =
О»
О»
вЋЄ
then we get вЋЁ
вЋЄ y = bnv + dmn + ( a в€’ c ) v mn
О»
О»
1 в€’ m2
(5)
Takingпј€3пј‰into(5), we have
a
c
bв€’d
вЋ§
2
2
2
2
2
2
2 2
2
2
2 2
x
u
v
u
v
u
u
О»
О»
4
О»
О»
v
=
+
в€’
+
в€’
+
+
в€’
+
в€’
(
)
(
)
(
)
вЋЄ
2О» 2
2О» 2
2О» 2
вЋЄ
вЋЁ
b
d
aв€’c
О» 4 в€’ (u 2 в€’ v 2 )2
2
2
2
2
2
2
y
u
v
u
v
О»
О»
=
в€’
+
+
+
в€’
+
в‹…
(
)
(
)
вЋЄ
2
2О» 2
2О» 2
2О» 2
вЋЄ
4О» 2u 2 в€’ ( О» 2 + u 2 в€’ v 2 )
(6)
The condition a пјњ x пјњ c satisfies
О» 2 в€’ u 2 + v2
4О» u в€’ ( О» + u в€’ v
2
and
2
2
2
)
пјћ
2 2
О» 2 + u 2 в€’ v2
4О» u в€’ ( О» + u в€’ v
2
2
2
2
)
2 2
d в€’b
cв€’a
пјћ
bв€’d
cв€’a
(7)
(8).
If (7) and (8) are satisfied,then if (6) holds,the total cost of building water pipe is the
minimum,
f min = umb + vnd + ( c в€’ a ) u 1 в€’ m2
пјќ
2
b
d
cв€’a
О» 2 + u 2 в€’ v2 ) + ( О» 2 в€’ u 2 + v2 ) +
4О» 2u 2 в€’ ( О» 2 + u 2 в€’ v 2 ) .(9)
(
2О»
2О»
2О»
At this point, we choose the hydropower R by (6). If (7) (8) are not satisfied, then
(6) is wrong. The hydropower is built at the factory which is close to the bank, for
example, the factory
Q
( b пјњ d пјњ 0),the hydropower is built at the factory
Q ( c, d ) ,the total cost of building water pipe is
О» CQ + uQP пјќ О» d + u
( a в€’ c ) + (b в€’ d )
2
2
Finally by this formula, we solve the final title of the second session of teamпјљmathoe
Beijing high
school of applied mathematics knowledge contest finals.
Firstly, we simple the formula, let О» = u = v :
The conditions(7)(8) are
вЋ§
a+c
+
вЋЄx =
вЋЄ
2
(6) is вЋЁ
вЋЄy = b + d +
2
3
(b в€’ d )
2
3
(a в€’ c)
6
вЋЎb + d
(9) is f min = вЋў
bв€’d
1
пјћ
,
aв€’c
3
вЋЈ 2
+
вЋ¤
3
( c в€’ a )вЋҐ О» ,
2
вЋ¦
The minimum of the total length of water pipe is
bв€’d
3
+
(c в€’ a) .
2
2
In origin title, the distances from the factories P and Q to the bank are 10km and
8km respectively. The distance between two factories is 14km. According to
(
)
142 + (10 в€’ 8 ) = 8 3 , we have P ( 0,10 ) пјЊ Q 8 3,8 which satisfy
2
10 в€’ 8
1
пјћ
.
0 в€’8 3
3
The hydropower
R
вЋ§
0+8 3
3
+
(10 в€’ 8) = 5 3
вЋЄx =
вЋЄ
2
2
.
вЋЁ
вЋЄ y = 10 + 8 + 3 0 в€’ 8 3 = 5
2
6
(
The minimum value of the total water pipe is
)
10 + 8
3
8 3 в€’ 0 = 21 .
+
2
2
(
)
We find a real problem after considering the above problem, even if the computation
seek the minimum point, we can not do it when we meet the high mountain or desert.
Furthermore, if n is very bigger, it is difficult to find the point. Hence, we try to consider
these problems from the view of approximation.
In fact, lots of real problems refer to a mathematical problem, i.e., how to find the
network in which the total distance from the finite vertices to the point is the minimum
possible. This is also a well-known problem----the Steiner tree problem.
By the references, this problem rises to the attention of many
mathematicians.
EspeciallyпјЊmany famous physicists considered this problem. Until 1934,teamпјљmathoe
Jarnik and
Kossler put forward Steiner tree problem:
For any arbitrary given n points
A1 ,вЂ¦вЂ¦, An , how can we get a minimal network linking
n points. This is not a point P пјЊbut the minimal connected network constructed by some
line segments linking n points. Hence Steiner tree problem becomes a special example.
Firstly, we consider the case of four points.
The problem is the four cities A, B,C,D
are four vertexes of a square, to build a
highway system such that there is highway between each two cities and the total length of
the whole highway is minimum, ask: how to design the highway?
D
A
E
D
A
G
E
H
F
F
B
C
B
C
The result is AE + EB + EF + FC + FD гЂ‚The reason as followsпјљIf the sum of line
segments is the shortest, where the broken line linking AC must intersect with the
broken line linking BD. Assume their common part is EF (including E is F), AE, BE,
EF,FC,FD must be straight line because the line is the shortest between two points. E
must be Fremat point ofв–і ABF пјЊotherwiseпјЊwe use the Fermat point of в–і ABF
instead of E to get the shortest route.
SimilarlyпјЊ F is also Fermat point of в–і CDE .
Thus
в€ ABE = в€ FEA = в€ FEB = в€ EFD = в€ EFC = в€ CFD = 120o .
Of course, the above answer is not complete, i.e., we donвЂ™t consider
E is not inside в–і ABF гЂ‚We may proof as followsпјљIn order the sum of
line segments is the minimumпјЊEF must parallel to one side of the square, and EF lies on
the symmetry axis of the square. Such as the above graph, choose GH such that it
parallels to BC, and lies the midpoint of the vertical. We may revise E, F as G,H to get
broken line. Obviously пјЊ AE + EB в‰Ґ AG + GB пј› EF в‰Ґ GH пј›
FG + FD в‰Ґ HC + HD пјЊi.e., the new broken line is shorter than the original one. If
EF вЉҐ BC пјЊthen we may adjust other directions. By further adjustment, we may
change the problem into the above case.
Next considering the not regular quadrilateral, this theorem is
Pollark Theorem.
a
new
Pollark Theorem
Let A, B, C, D be four given points, the intersect angles of two
Оё and 180o в€’ Оё respectively. Assume that two full
(topology) Steiner trees exist.
If
Оё в‰¤90В°, then the shortest one of the two Steiner trees is the one lying the region
where the angle is
Оё.
H
F
I
C
B
J
E
A
D
L
teamпјљmathoe
в–і DCJ пјЊв–і AEB пјЊв–і CBF пјЊв–і DAL пјЊв–і CEH and в–і AFI are Equilateral triangle.
Оё в‰¤90В°пјЊby в€ JCE = 60o + в€ DCE = в€ DCH пјЊ we have BH = BI and JE = DH .
By the same tokenпјЊ в€ FBH = П† = в€ BCA and LF = DI ,
To prove JE в‰¤ LF пјЊ only to prove DH в‰¤ DI .
Firstly we show that BH = BI ,
This may be obtained by в–і FAB в‰Њв–і IAE and в–і HFB в‰Њв–і ABC ,then we have
BI = AC гЂ‚
Similarly, by в–і HFB в‰Њв–і ABC пјЊ
Hence, we have в€ FBH = П† = в€ BCA пјЊ BH = AC .
henceпјЊwe have BH = BI .
In в–і DBH and в–і DBA , DB is the common line segment, BH = BI ,
в€ DBH = 60o + r + П† = 60o + 0o ,
в€ DBI = 60o + a + П†
By a + П† пјќ180В°пјЌ0В°в‰Ґ0, we have ID в‰Ґ DH . The proof is completed.
It is worthwhile to notice that if A,B,C,D lie the veterxes of the 1Г—2 rectangular.It is
easy to see thatпјЊthe four points has only a Steiner tree. Hence, for the same n, the
number of Steiner stree is different even if under the case of nondegeneration.
We consider convex pentagon and more sides, we solve it by approximation
algorithm because the possiblity is too much.
Definition: A minimum spanning tree or minimum weight spanning tree is then a
spanning tree with weight less than or equal to the weight of every other spanning tree.
Next, we give a method
which may find minimum spanning tree for any graph,
which is said that KruskalвЂ™s algorithm.
KruskalвЂ™s algorithm
a minimum
Assume n = [ p1 ,..., pn ] be a given point set, the KruskalвЂ™s algorithm to findteamпјљmathoe
spanning tree for connecting p1 пјЊвЂ¦вЂ¦пјЊ pn as follows.
1гЂЃWe obtain the length of Pi and Pj I ( pi p j ) , then there are
n ( n + 1)
2
line
segments. We denote
them as l1 в‰¤ l 2 в‰¤ l 3 в‰¤ l 4 в‰¤вЂ¦вЂ¦в‰¤ l n в‰¤вЂ¦вЂ¦.
2гЂЃChoose l1 at first, let li
= l ( pi p j ) .
Draw the straight line segment linking Pi
and Pj , then choose l2 пјЊ and so on. But we need to keep theses linked lines donвЂ™t
construct a circle. If l1 пјЊвЂ¦вЂ¦пјЊ lk have been chosen, the linking line corresponding to
lk +1 are addedпјЊ there exists a circleпјЊthen we omit lk +1 . Then go on until all pi are
By the graph method, the graph
G
must be one of the spanning trees of
N . Now
we show that it is the minimum by induction. If n пјќ3пјЊthen the proposition holds.
Omit
G'
pi
N , then
in
the line segments pi p j in G also omitted. We denote it as
. In term of the diagram and induction assumption,
tree connecting
G
in li , hence
n
. Now we add pi1 to
pi1
G' пјЊ
G'
then we get
is the minimum spanning tree of
is the minimum spanning
N . l1
is the minimum
N.
Now we consider the ratio of this minimum spanning tree to Steiner minimum
spanning tree, i.e., the scale of the ratio of the real value to the approximation value. By
simply computation, we find both three points and weighted three points satisfy the ratio
is larger than
and equal to
3
.
2
Actually, this is the famous Steiner tree ratio conjecture.
We may describe as follows: Let X be a set consisting of n given points. The
distance of two points A [ X 1 , Y1 ] and B [ X 2 , Y2 ] is defined by
(
Let Ls ( x ) = L SMT ( x )
minimum
Ls ( X ) в‰Ґ
tree
and
3
LM ( X ) .
2
)
the
(
and Ls ( x ) = L MST ( x )
minimum
support
)
tree
( x1 в€’ x2 ) + ( y1 в€’ y2 )
2
2
.
denote the length ofteamпјљmathoe
the Steiner
respectively,
then
we
have
в‘ According to look up the references, the proof of this conjecture was
Full of twists and turns пј€see page 234 of вЂњThe errors and creation of the mathematical
masterвЂќ editor by Wu Zhenkui, Wu JianпјЊ Wu Min пј‰.
In this paper, we mainly use the proof of Zhao[5]We rewrite the main process in brief.
Before proving the theorem, we assume the following conditions holdпјљ
пј€1пј‰Without loss of general, all the points in X are leaves in
T = SMT ( X )
of
X . It is said that endpoint, i.e., the degree of every point is 1.
пј€2пј‰Without loss of general, we assume there exists a branch on the
of
X
SMT ( X )
shown in the following figure. If not, we may add a infinite small branch on
C or D .
Next we prove the Stenier ratio conjecture Theorem by induction.гЂ‚
A
B
a
b
S1
s
P
Q
S2
c
d
C
D
E
F
If not, assume the inequality в‘ does not hold, i.e., there exists a point set X, such
that Ls ( X ) в‰Ґ
3
LM ( X ) . Then there must exists a
2
minimum point number, such that
Ls ( X )
3
пјњ
.
2
LM ( X )
X
which contains the
Team:mathoe
A
B
AвЂІ
a
b
S1
s
S2
c
P
G
d
E
D
Q
C
F
CвЂІ
R
E
As shown in the above Figure, where
F
A пјЊ B пјЊ ( P пјЊ Q ) is the points of X , and
S1 пјЊ S2 пјЊ C пјЊ D (properly contain P пјЊ Q ) are Stenier points.
Without loss of general, we assume
C'D =
cпјћd .
Hence we construct
C ' D вЉҐ CC ' ,
3
(c + d ) .
2
Assume a в‰¤ b , a
2
+ ab + b 2 = 1 , let PC = tc , DQ = td .
Then
min { AP + PQ ' + Q ' B, AP ' + P 'Q + QB}
в‰¤
AP + PQ + QB
max { AP + PQ ' + Q ' B, AP ' + P 'Q + QB} .
We get the following equalities by the plane geometry.
AP 2 = s 2 + sc + c 2 + a ( s в€’ c ) в€’ tc вЋЎвЋЈ 2a + s в€’ (1 + t ) c вЋ¤вЋ¦
BQ 2 = s 2 + sd + d 2 + b ( s в€’ d ) в€’ td вЋЎвЋЈ 2b + s в€’ (1 + t ) d вЋ¤вЋ¦
в‰¤
teamпјљmathoe
PQ 2 =
3
1
2
2
2
2
(1 + t ) ( c + d ) + (1 в€’ t ) ( c в€’ d ) .
4
4
We have to prove the following two realities.
Reality. 1пјљ
When proving four points, we construct Cartesian coordinates, then
( 2s + a + d )( 2s + b + c ) в‰Ґ 3 ( a + d )( b + c ) .
Furthermore, we obtain the corollary
s в‰Ґ 0.366 min {a + d , b + c} .
Reality.2пјљ
пј€1пј‰if a в‰¤ b , a
2
+ ab + b 2
вЋ› 3
вЋћвЋ›
3вЋћ
в€’ b вЋџ вЋњ 2a + b в€’
вЋџ
вЋњ
2
2 вЋ вЋќ
вЋ вЋќ
= 1 ,then s + c + d пјњ
a + 2b в€’ 3
пј€2пј‰if s + c + d в‰Ґ О» a пјЊthen вЋЎ( 2О» + 1) a в€’ 3 вЋ¤ 1 в€’
вЋЈ
вЋ¦
1вЋћ
3 2
вЋ›
a + 1.75 в‰¤ 3 вЋњ О» + вЋџ a + 1.5a 2
2вЋ 4
вЋќ
Here we make use of the assumption about
X
,let
S ' = LS ( A, C , D ) пјЊ
X ' =X в€’ { B} .
By the following inequalities,
3
LM ( X ' ) в‰¤ LS ( X ' ) в‰¤ LS ( X ) в€’ ( s + a + b + c + d ) +s ' .
2
We get
s + a + b + c + d в€’ s' пјњ
'
By the computation, s пјќ
3
2
a2 + a ( s + c + d ) + ( s + c + d )
Henceпј€1пј‰ is proved. Consider the relation
Next, we prove by contradiction. If
from the formula (1).
Ls ( X )
3
пјњ
,
LM ( X ) 2
LS ( X ) в€’ a в€’ b в€’ c в€’ d + s + C ' D
X \ { A, B} .
О» and a
2
is the length of the connected graph
teamпјљmathoe
Hence, by induction assumption,
LS ( X ) в€’ a в€’ b в€’ c в€’ d + s + C ' D
в‰Ґ LS
( X \ { A, B}) в‰Ґ
3
LM ( X \ { A, B} ) .
2
If we have
a + b + c + d + s в€’ C'D в‰Ґ
Then
LM ( X ) пјћ
3
( AP + BQ ) .
2
2
Ls ( X )
3
в‰Ґ
вЋ¤
2 вЋЎ
3
'
L
X
в€’
a
в€’
b
в€’
c
в€’
d
в€’
s
+
C
D
+
AP
+
BQ
(
)
(
)
вЋў S
вЋҐ
2
3вЋЈ
вЋ¦
в‰Ґ
вЋ¤
2 вЋЎ 3
3
LM ( X \ { A, B} ) +
( AP + BQ ) вЋҐ
вЋў
2
3вЋЈ 2
вЋ¦
в‰Ґ LM
(X )
Hence we only need to prove
a + b + c + d + s в€’ C'D в‰Ґ
3
( AP + BQ )
2
Similarly, we only need to prove the following inequality
a+b+c+d +sв‰Ґ
3
( AP + AB (ж€–PQ ) + BQ )
2
And we must notice that
AB пјќ1
Next, we attempt to prove one of the two formulas.
в… if a пјЊ d в‰Ґ b пјЊ s в‰¤ a пјЊ s в‰Ґ min 0.366
( a + b, b + c ) в‰Ґ 0.366 ( a + b ) .
We have
a+c+
s 3вЋ› a
s 3вЋ› b
вЋћ
вЋћ
в‰Ґ
+ BQ вЋџ .
+ AP вЋџ пјЊ b + d + в‰Ґ
вЋњ
вЋњ
2 2 вЋќ a+b
2 2 вЋќ a+b
вЋ вЋ We only need to prove one of these inequalities, we show the first one. teamпјљmathoe
By
AP 2 = s 2 + sc + c 2 + a ( s в€’ c ) в€’ tc вЋЎвЋЈ 2a + s в€’ (1 + t ) c вЋ¤вЋ¦ .
Take it into the first inequality, minus both sides, derivate about
c , we get
О” 'c пјќ 2c + 11a + s в€’
Let c
4 3a
пјћ0.
a+b
= a , then prove
3a 2 4 3a вЋ› 2 1 вЋћ
2
13a + 2as +
в‰Ґ
вЋњ 2a + as вЋџ + 2 s .
1 + ab a + b вЋќ
2 вЋ 2
By
c в‰Ґ a пјЊ d в‰Ґ b пјЊ s в‰¤ a пјЊ s в‰Ґ min 0.366 ( a + b, b + c ) в‰Ґ 0.366 ( a + b ) ,
And the above inequality is increasing about
a
on both sides, let
a = 0.48 ,then
a + b = 1.1495
And we can get s в‰¤1.1445a .
If s в‰Ґ1.1445a , we have
c в‰Ґ a пјЊ d в‰Ґb пјЊc + d пјќl в‰Ґ a + b .
Now we prove
a+b+c+d +sв‰Ґ
3
( AP + 1 + c + d ) .
2
Squaring both sides and then do minus, we find that it is increasing
= 0.366 ( a + b ) , then take it into the above inequality and do minus, we
find that it is decreasing about
a + bв‰¤
a + b . By
2
пјќ1.1547,
3
we choose вЂњпјќвЂќ, take it into the inequality
5.964ab + 1.902ac + 0.0718l 2 + 0.7624l
в‰Ґ 4.098a
2
+ 3c 2 + 1.098bc .
If b=c, we get
11.964ab +0.0718l 2 + 0.7624l в‰Ґ4.098. It is easy to verify
that the inequality holds when
l в‰Ґ0.48пјЊ a в‰Ґ0.44.
By the reality 2, we have
a в‰Ґ0.48пјЊ l в‰Ґ a + b в‰Ґ1.495.
The left of в‘Ў minus the right of в‘Ў is decreasing about
c,
c в‰¤1.2b , we take c=1.2b into в‘Ў, let l пјќ1.1495, we obtain
If
11.964ab в€’ 1.5396b 2 в‰Ґ3.1267,
Obviously, when
a в‰Ґ0.48, the above inequality holds. The
proof of the first case is
completed.
в…Ў
tв‰¤
1
пјЊ c пјњ a пјЊ 0.1a в‰¤ d в‰¤ b пјЊ s в‰¤ 0.366 ( a + b )
6.5
or
s в‰¤ a пјЊ s пјћ 0.366 ( a + b ) .
We only need to prove
a+c+
E
s 3
s 3
в‰Ґ
( AP + EP ) еЏЉ b + d + в‰Ґ ( BQ + EQ ) ,where
2 2
2 2
is the intersection of
S1S2
and
PQ .
In fact, we only need to prove the first formula, similarly, we can prove the second one.
By the geometry relations,
PE =
Let О±
c
d
PQ , EQ =
PQ .
c+d
c+d
=
PQ
,then PE = О± c пјЊ EQ = О± d .
c+d
AP
Extend
to
R
such that
PR = PE = О± c ,
Hence, we only need to prove
a+c+
s 3
+О±c .
в‰Ґ
2 2
The function
AP + О± c
t , let
1
.
6.5
t=
PA ( A' ) в€Ґ S1S2 ,and
Hence,
1 вЋћ
вЋ›
A' P = c + s , a = вЋњ1 +
вЋџc.
вЋќ 6.5 вЋ Only need to prove
a+c+
s 3
в‰Ґ
(c + s + О± c)
2 2
is equivalent to
вЋЎ 3
вЋ¤
0.366 s в‰¤ a в€’ вЋў
(1 + О± ) в€’ 1вЋҐ c .
вЋЈ 2
вЋ¦
3
1
2
2
2
2
(1 + t ) ( c + d ) + (1 в€’ t ) ( c в€’ d ) , it holds if
4
4
0.9985в‰¤ О± в‰¤1.0851, i.e., a в‰Ґ0.4581.
By PQ
2
=
Next, there are several cases about s.
If s
= 0.366 ( a + b ) , by
a в‰Ґ0.3575пјЊ a + b в‰Ґ1.1296, hence
s в‰Ґ0.4134, if a пјќ0.43, s в‰Ґ 0.9615a . By
cпјќ
dв‰Ґ
Team:mathoe
13
a , we assume c + d в‰Ґ a , i.e.,
15
2
a.
15
By (2) of the reality 2, if
О» в‰Ґ1.9615, the left side of the formula in reality 2
пјќ2.1072, the
right side пјќ2.1106, hence, we must have
a в‰Ґ0.43. And if d в‰Ґ
a
, we obtain
4
a в‰Ґ0.4580.
Hence,
sв‰¤
0.366 ( a + b )
Now we assume s в‰Ґ 0.366
a в‰Ґ0.43. Let c =
13
a
15
holds.
( a + b ) , by (1) of the reality of 2, we have
and d
=
a
, then
4
О± в‰¤1.2622. Take it into
вЋЎ 3
вЋ¤
0.366 s в‰¤ a в€’ вЋў
(1 + О± ) в€’ 1вЋҐ c , we have
вЋЈ 2
вЋ¦
0.366 s в‰¤ 0.3459a , and if d
becomes larger, we have
sв‰¤a .
Hence, if
s в‰¤ 0.9451a , c =
13
a , the proposition holds.
15
If a пјћ
15
c , it is easy to verify
13
aв€’
3
AP
2
is increasing. Hence the formula holds by the above calculation. Hence, in
case в…Ў, the original proposition
holds. In fact, other cases can change to case в… by the
symmetry. The proof is completely.
Team:matheo
The end
This paper is finished in summer vacation, the main contents of the paper is based on the
email communication. Hence, the members of the team learns to encourage each other.
Of course, the proof of the Steiner ratio conjecture is not completed. We give a proof of
the Steiner ratio conjecture from the high studentsвЂ™ view, by Zhao MinyiвЂ™s method. We try
to make up the discussion and the computation proof of the inequalities.
Because
there are some
we have no
enough time to give the proof of the Steiner ratio conjecture,
small mistakes. The paper tends to explore the minimum connecting
problem in the network. Because
we have no the ability about them, we will go on
exploring.
By taking part in this contest, we not only learn to the use of mathematics but also
the direction studying mathematics. We would like to thank this contest for the great
support and hospitality.
References
[1] X.Q.,Nan, how to find the optimal point,
Hunan Education Publishing House, Mathematics Olympiad
Issue:3, 1989.
[2] K.H.,Li, The minimum formula of the weighted FermatвЂ™s problem,
High- School Mathematics, Issue:2, 1998.
[3] D.L.,Lei, Soving three famous problems by a class of external value, High- School
Mathematics, Issue:1,2001.
[4] D.Z.,Ding, About the proof of Filbert-Pollak Theorem, Dissemination of
mathematical, Volume: 17 Issue: 4, 1982
[5] M.Y., Zhao, the minimum network, Shanghai Science and Technology Publishing
House, 2006.
Acknowledgements.
The team would like to thank the mathoe web set for the great support and hospitality.
The team would like to thank
Mr Li Qiyin for the great support and hospitality.
teamпјљmathoe
The team would like to thank the parents of two students for
the great support and hospitality.
```
###### Документ
Категория
Без категории
Просмотров
16
Размер файла
329 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа