B. V. Beklasov
Aplicarea teoremei lui Euler la anumite probleme
În acest articol, oferim cititorilor mai multe probleme în care teorema Euler joacă un rol central. Acordând cea mai mare atenție problemelor, nu demonstrăm aici această teoremă, ci numai formularea acesteia. Dovada teorema lui Euler, precum și formularea mai generală a acestei teoreme pot fi găsite în cartea „Ce este matematica?“ Courant și Robbins și „Geometrie și“ Hilbert și Cohn-Vossen.
Înainte de a formula teorema lui Euler, suntem de acord că o linie care se termină la două puncte date va fi numită un arc care unește aceste puncte. în cazul în care această linie poate fi traversată fără a fi vizitat vreunul din punctele sale de două ori.
Teorema lui Euler. Să presupunem că există puncte m și n perechi arcuri disjuncte în plan, fiecare dintre care conectează oricare două puncte dat și nu trece prin restul de m # 150; 2 puncte și lăsați aceste arce să împartă avionul în regiuni l. Dacă dintr-un punct dat spre oricare dintre celelalte puncte puteți ajunge acolo prin mișcarea de-a lungul acestor arce
În cazul prezentat în figura 1, sunt îndeplinite toate condițiile teoremei Euler, m = 1 2, n = 18, l = 8 și m # 150; n + l = 2. Figurile 2 și 3 prezintă cazurile în care condițiile acestei teoreme nu sunt îndeplinite. Deci, în figura 2 de la punctul A1, nu puteți ajunge la punctul A5 și m # 150; n + l = 3 ≠ 2. iar în figura 3 linia care leagă punctele A1 și A2. se auto-intersectează și din nou m # 150; n + l = 3 ≠ 2.
În unele probleme, un set format din mai multe puncte și conectarea arcurilor disjuncte pereche se numește hartă; și numim punctele din aceste noduri. și regiunile în care arcele împart planul, # 151; țări.
Acum putem continua rezolvarea problemelor.
Sarcina 1. Este posibilă conectarea a zece orașe între ele prin șosele care nu intersectează, astfel încât din fiecare oraș cinci drumuri să conducă la alte cinci orașe.
Soluția. Să presupunem că orașele pot fi conectate între ele prin drumuri, așa cum este indicat în sarcină. În acest caz, dacă nu sunt conectate direct două orașe, atunci există un al treilea oraș, care va fi deja conectat direct la fiecare dintre ele. Atragând puncte pe avionul orașului și pe drumuri # 151; arce, vedem că orice două puncte sunt conectate printr-un lanț de arce. Deoarece la fiecare punct se converg cinci arce, numărul total de arce este egal cu 1,5 · 10 = 25. Conform teoremei lui Euler, aceste arce împart planul cu 2 + 25 # 150; 10 = 17 zone. Fiecare dintre aceste șaptesprezece regiuni este limitată de cel puțin trei arcuri, deoarece altfel ar exista două orașe conectate direct prin cel puțin două drumuri, ceea ce contravine condiției problemei. În consecință, numărul de arce nu este mai mic de ½ · 3 · 17 = 25,5. Astfel, presupunerea inițială ne conduce la o contradicție, iar orașul nu poate fi conectat unul cu celălalt așa cum este necesar în sarcină.
Sarcina 2. Trei vecini certați au trei puțuri comune. Este posibil să se efectueze trasee care nu se intersectează de la fiecare casă la fiecare puț.
Soluția. Să presupunem că puteți face acest lucru.
Reprezentăm casele în albastru și fântânile # 151; puncte negre și conectați fiecare punct albastru cu un arc cu fiecare punct negru astfel încât cele nouă arce obținute să nu se intersecteze în perechi. Apoi, cele două puncte care descriu case sau fântâni vor fi conectate printr-un lanț de arce, iar prin teorema Euler aceste nouă arce împart avionul în 9 # 150; 6 + 2 = 5 regiuni. Fiecare dintre cele cinci zone este limitată de cel puțin patru arce, deoarece, datorită condiției sarcinii, niciuna dintre piste nu trebuie să conecteze direct două case sau două puțuri. Prin urmare, numărul de arce trebuie să fie cel puțin ½ · 5 · 4 = 10, și, prin urmare, ipoteza noastră este falsă.
Problema 3. Dovediți că pe fiecare hartă există o țară care învecinează nu mai mult de cinci țări.
Soluția. Dacă numărul de țări de pe hartă nu depășește șase, atunci afirmația problemei este evidentă. Vom dovedi că pe o hartă cu mai mult de șase țări există chiar patru țări, fiecare având cel mult cinci țări. Vom desena topurile și arcurile hărții originale în negru, iar în fiecare țară vom marca un punct cu vopsea roșie. Orice două puncte marcate situate în țările vecine (de exemplu, țările care au un arc de cerc comun de delimitare), se alăture în aceste țări arc roșu, astfel încât arcul disjuncte roșu. Apoi, oricare două puncte roșii vor fi conectate printr-un lanț de arce, și din moment ce nu există două construit arcul nu se va alătura același punct, în fiecare țară de pe hartă, constând din puncte și arce de culoare roșie, aceasta va fi limitată de cel puțin trei arce de cerc. În cazul în care orice țară de pe această hartă este limitat la maximum trei arce de cerc, apoi pe marginea sa, puteți alege două noduri nu sunt conectate printr-un arc, și să le conecteze la arcul roșu în această țară. Dacă repetăm această operațiune de mai multe ori, primim o carte roșie, pe care fiecare țară este mărginită de exact trei arce. Din moment ce, în plus, pe această hartă, nu există două arce nu conectați aceleași vârfurile și ca numărul de vârfuri mai mult de trei, care emană de la fiecare nod cel puțin trei arce de cerc. Denumim prin n numărul de arce, de l # 151; numărul de țări, prin m # 151; numărul tuturor vârfurilor cărții roșii și a # 151; numărul de vârfuri din care apar mai puțin de șase arce. Atunci ajungem
Din formula (1) și teorema Euler aplicată la un sistem de puncte și arce de culoare roșie, rezultă că
care arată că o ≥4. Rămâne de reținut că, dacă o țară pe un card negru are mai mult de cinci vecini, mai mult de cinci arce apar din punctul roșu marcat din această țară și, prin urmare, din cauza inegalității a ≥ 4. pe un card negru există patru țări, fiecare dintre ele având nu mai mult de cinci vecini.
Problema 4. O heptagon poate fi tăiată în hexagoane convexe.
Soluția. Să presupunem că un heptagon a fost tăiat în hexagoane convexe. Să denotăm numărul acelor vârfuri ale hexagonilor care se află în interiorul heptagonului original, de către m. și numărul de vârfuri rămase (adică, situată la limita unui heptagon) # 151; prin m '. Ca arce care conectează nodurile, alegem segmente rectilinie ale laturilor poligonale care satisfac următoarea condiție: segmentul trebuie să conecteze două vârfuri și să nu treacă prin celelalte noduri. Denumim prin n numărul de arce și l # 151; numărul de regiuni la care aceste arce împart planul (numărul l este mai mult decât numărul de hexagoane). Este clar că orice două vârfuri vor fi conectate printr-un lanț de arce. Prin teorema lui Euler
Deoarece domeniul exterior este marcat de arce m, fiecare dintre celelalte # 151; nu mai puțin de șase arce, atunci
Dintre cele câteva vârfuri de la limita heptagonului există doar două arce. Indicați numărul de astfel de noduri prin a. Din fiecare alt vârf ieșesc cel puțin trei arce, așa că
Prin urmare, având în vedere egalitatea (3)
Comparând această inegalitate și inegalitate (4), obținem
Deoarece există cel puțin două vârfuri la limita heptagonului, de unde apar arcurile care duc către interiorul heptagonului, atunci m ' # 150; a ≥ 2. Această inegalitate și inegalitate (5) implică faptul că a ≥ 8.
Pe de altă parte, din moment ce Heptagon este tăiat în poligon convex, atunci fiecare nod, din care două arce ies, este vârful unui Heptagon, și, prin urmare, un ≤ 7. Astfel, Heptagon nu poate fi tăiat în hexagoane convexe.
Următoarele sarcini pe care le propunem cititorului să le rezolve în mod independent.
Este posibil să conectați cinci orașe între ele prin șosele care nu intersectează, astfel încât din fiecare oraș în orice alt oraș să existe un drum care să nu treacă prin alte orașe?
Soluția
Să presupunem că orașele sunt conectate unul la celălalt, așa cum este indicat în starea sarcinii. Apoi, patru drumuri pleacă din fiecare oraș, iar numărul total de drumuri este egal cu 5,4 / 2 = 10. Pe de altă parte, prin teorema lui Euler, numărul de regiuni pe care drumurile împărțesc planul este de 2 + 10 # 150; 5 = 7; iar fiecare dintre zone este limitat la cel puțin trei drumuri; prin urmare, numărul total de drumuri trebuie să fie cel puțin 3,7 / 2 = 10,5. Prin urmare, este imposibil să conectați orașele așa cum este spus în sarcină.
Dovedeste ca daca numarul de tari de pe harta este mai mare de nouazeci, atunci pe aceasta harta exista trei tari cu acelasi numar de vecini.
Soluția
Construim o "hartă duală": notați în fiecare țară punctul și conectați punctele situate în țările vecine cu arce disjuncte. Indicăm prin m. n și l, respectiv, numărul de vârfuri, muchii și țări ale hărții duale. Este clar că harta duală este conectată (adică fiecare două vârfuri sunt conectate printr-un lanț de arce) și fiecare țară pe o hartă duală este limitată de cel puțin trei arce. Astfel, 3l ≤ 2n.
Prin urmare, prin teorema Euler, 6m ≥ 12 + 2n. Comparând această inegalitate cu relațiile evidente
unde mi denotă numărul de vârfuri de la care ieșim margini, obținem
Pentagonul este tăiat în mai multe poligoane, astfel încât toate laturile pentagonului original nu sunt tăiate. Dovedeste ca daca numarul de poligoane rezultate nu este mai mic de cinci, atunci in unul dintre ele exista un unghi care este mai mare sau egal cu 72 °.
Soluția
Ca și în cazul heptagonului, luați în considerare harta, care este determinată de liniile de tăiere, și denotă numărul de vârfuri, arce și țări ale acestei hărți, respectiv de m. n și l. Noi numim topul hărții incorect. Dacă se află pe partea laterală a unuia dintre poligoane și nu este vârful său; numim numărul de vârfuri neregulate de m '. Indicăm prin r numărul de arce care se ridică de la vârfurile pentagonului original și diferă de laturile sale și fiecare arc, ambele capete ale cărora se află la vârfurile pentagonului, suntem de acord să luăm în considerare de două ori. Să presupunem că în fiecare dintre poligoane toate unghiurile sunt mai mici de 72 °. Apoi: a) toate țările, cu excepția celor nelimitate, sunt triunghiuri; b) de la fiecare vertex corect situat in interiorul pentagonului original, nu mai putin de sase arce ies si din fiecare varf incorect # 151; nu mai puțin de patru. Rezultă din a) că 2n = 3 (l # 150; 1) + m '+ 5 și din b) # 151; că
Din aceste relații găsim asta
Deoarece prin teorema lui Euler m # 150; n + l = 2, atunci inegalitatea obținută indică faptul că r ≤ 4. Pe de altă parte, este ușor de a arăta că, dacă pentagonului tăiat pentru mai mult de patru poligon, r> 4. În consecință, cel puțin într-una dintre poligoanelor va unghi mai mare sau egal cu 72 °.
Triunghiul, cu toate unghiurile nu mai mult de 120 °, este tăiat în mai multe triunghiuri. Dovedeste ca intr-unul din triunghiurile rezultate, toate unghiurile nu sunt mai mari de 120 °.
Soluția
Ca și în problema anterioară, luați în considerare harta definită de liniile de tăiere. Denumim numărul de vârfuri, arce și țări ale hărții rezultate cu m. n și l. numărul de vârfuri neregulate de m '. Este clar că 3l + m '= 2n. și după teorema lui Euler # 150; n + l = 2, atunci
Într-adevăr, fiecare dintre nodurile regulate situate în interiorul triunghiului inițial sunt situate nu mai mult de două unghi mai mare de 120 °, iar fiecare dintre nodurile neregulate # 151; nu mai mult de unul. Contradicția dintre (*) și (**) indică faptul că, printre triunghiuri, obținute după tăiere, există un triunghi cu toate unghiurile nu mai mult de 120 °.
Doi jucători participă la joc. Înainte de începerea jocului, punctele m sunt marcate pe plan. Jucătorii iau pe rând în căutarea pentru cele două puncte nu este conectat printr-un arc de cerc, și conectați aceste puncte de arc care se intersectează arcul construit anterior. Cel care face ultima mișcare câștigă. Pentru care m câștigă jucătorul care a făcut prima mutare și sub care # 151; adversarul său?
Soluția
Se pare că numărul de mișcări din acest joc este determinat numai de numărul m. Într-adevăr, cazul m = 2 este evident. Să presupunem că m> 2. apoi, la sfârșitul jocului va mapa un plan pe care fiecare două vârfuri sunt conectate prin arce ale unui lanț și fiecare țară este limitată la trei arce de cerc, adică 2 n = 3 l. Din teorema lui Euler rezultă că numărul de arce ale unui astfel de card este de 3 (m # 150; 2). Dar numărul de arce pe harta care rezultă este egal cu numărul de mișcări din jocul nostru. Prin urmare, obținem: pentru m. mai mult de doi, jucătorul care a făcut prima mișcare câștigă, și cu un m par. mai mult de două # 151; adversarul său.