# 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 Grade one Bingjie Wu: Webmaster of mathoe Grade two www.mathoe.com Registered Address: Panyu District Nancun town Nanda Road No.168 Guangzhou 511442 Tutor Qiyin Li (the chairman of mahtoe website) пј€Please seewww.mathoe.comпј‰ 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 diagonals of the quadrilateral are Оё 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 linked. 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 ) Which is a contradiction. 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 about s .let s = 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 is increasing about 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.

1/--страниц