Cirkler i en cirkel • Konstantin Knoop • Videnskabelige-populære problemer på "Elements" • Matematik

Cirkler i en cirkel

opgave

Hvad er den mindste radius af en cirkel, hvor 7 enkeltcirkler kan placeres uden overlapninger? Retfærdiggør dit svar.

Bemærk. Enhedscirkel – cirkel af radius 1. "Ingen overlejringer"betyder at cirklerne kan røre, men bør ikke have fælles indvendige punkter.


Tip 1

Radien er 3, og det "optimale billede" ser ud, som du sandsynligvis forestillede dig selv (figur 1).

Fig. 1


Tip 2

Det er praktisk at slippe af med begrebet "overlay" ved at flytte fra denne opgave til dette:
Overvej i stedet for cirkler kun deres centre. Hvad angår den mindste radius, kan du passe dem alle sammen?

Fig. 2

I det "optimale billede" er alle centre hjørner og midten af ​​en regelmæssig sekskant med side 2 (figur 2). Samtidig er afstanden mellem to hjørner og midten af ​​en sådan sekskant også 2, derfor ligger alle punkter i en cirkel med radius 2. Det er nødvendigt at bevise, at alle disse punkter ikke kan passe i en cirkel med mindre radius. For at gøre dette, prøv at overveje tilfælde af hvor mange (ud af de seks punkter, der er forskellige fra midten) danner en konveks polygon.


beslutning

Vi vil handle ved metoden "det modsatte." Antag at seks punkter med parvis afstand 2 (eller mere end to) lykkedes at sætte en radius cirkel R <2.Lav en homoteti med en koefficient 1 /R. Så bliver denne cirkel en enkelt.

Dil (fra græsk homos – lige, identiske, gensidige, fælles og thetos – placeret) er en transformation af flyet, hvor hvert punkt M nogle point er tildelt M'ligger på OMhvor Oh – Fast punkt og forholdet OM\’ : OM = k (homotetik koefficient) er den samme for alle punkter M. Med homoteti ændres hver figur til en lignende, og alle afstande mellem punkter ændres nøjagtigt ind k tid.

Nedenfor beviser vi det Hvis 6 point ligger i enheden cirkel, overstiger afstanden mellem to af dem ikke 1. Dette betyder, at afstanden mellem de to punkter ikke oversteg, før homotetien R, det vil sige, det var mindre end 2. Midten af ​​segmentet mellem disse to punkter er placeret fra enderne af segmentet på en afstand mindre end 1, dvs. inden for hver af enhedens cirkler med centre i disse ender. Med andre ord overlapper disse enkelte cirkler. Modsigelse.

Lemma. Hvis 6 punkter ligger i enhedens cirkel, overstiger afstanden mellem to af dem ikke 1.

Bevis.

1. For det første bemærker vi, at hvis nogen af ​​de seks punkter (vi betegner det X) ligger inde i resten (matematikere siger: "Indenfor de konvekse skrog af de andre"), så er afstanden fra den til en af ​​de andre ikke mere end 1.

Faktisk, hvis kun to punkter kommer ind i det konvekse skrog, ligger alle de andre punkter på segmentet. Længden af ​​dette segment er ikke mere end 2, så hvis du sætter en prik på den, vil afstanden fra den til en af ​​enderne af segmentet ikke være mere end 1.

Hvis i det konvekse skrog der er mindst tre punkter, så kan du altid vælge tre af dem, siger, En, B, C på en sådan måde at X tilhører det konvekse skrog af punkter En, B, Cdet vil sige ligger i en trekant ABC. Men ethvert punkt i denne trekant ligger i enhedens cirkel med midten ved en af ​​trekantenes hjørner (se fig. 3).

Fig. 3. Vi tegner en cirkel med radius 1 fra hvert hjørne af trekanten. Hvert punkt i trekanten er mindst i en farve, det vil sige det er dækket af mindst en af ​​cirklerne.

Således for denne sag (et af de seks punkter ligger inde i de andre konvekse skrog), er påstanden allerede blevet bevist.

2. Antag nu, at det konvekse skrog indeholder alle 6 punkter.

Hvis nogen af ​​dem (siger, En) ligger ikke på grænsen af ​​cirklen, så den kan flyttes til grænsen, så afstanden til de andre punkter ikke falder.Dette kan f.eks. Gøres ved En akkord adskille En fra de resterende punkter og derefter flytte En på grænsekredsen vinkelret på denne akkord (figur 4).

Fig. 4

Forklaring til fig. 4. B og C er punkterne i et konveks skrog tættest på A (vi antager at de allerede er i en cirkel, selv om dette ikke er så vigtigt). Så er vinklen af ​​BAC mindre end 180 °. Det betyder at gennem A kan du tegne en akkord af FG, så point B og C er på den ene side af den.

Du kan også tegne AH vinkelret på FG og flytte punkt A til punkt H. Da vinklerne BAH og CAH var større end FAH og GAH, er de begge obtuse, hvilket betyder at den største side ligger i trekanterne BAH og CAH. Med andre ord, BH> BA og CH> CA. Det vil sige, med et skifte fra A til H, steg afstanden til punkterne B og C.

Endelig, hvis alle punkter ligger på enheden cirkel, dividerer de den i 6 buer, derfor er længden af ​​de mindste buer ikke mere end 1/6 af omkredsen, det vil sige ikke mere end 2π / 6. Dette betyder, at størrelsen af ​​den centrale vinkel på denne bue også ikke overstiger 2π / 6, hvilket betyder at afstanden mellem to punkter, som er enden af ​​denne bue, ikke er mere end 2sin (π / 6) = 1.


efterskrift

Denne opgave er et eksempel på en enorm klasse af såkaldte "minimax" -problemer med beregningsgeometri.I minimaxproblemer søges den størst mulige værdi af en mængde, som i sig selv er defineret som den mindste værdi af en anden mængde. I vores tilfælde var minimax-problemet (som vi reducerede den oprindelige) således: For det første blandt alle 15 parvise afstande mellem seks punkter i enhedscirklen, den mindste er valgt, og derefter er der fundet en sekspunkts konfiguration, for hvilken denne afstand er størst mulig.

Vores erklæring og dens bevis tilhører den bemærkelsesværdige amerikanske matematiker Ronald Graham, udgivet i 1968. Graham viste et endnu mere generelt skøn for den mindste afstand d mellem nogle af k punkter ligger i enhedens cirkel. Denne rating er

d ≤ max (1, 2 sin π /k)

(Det vil sige, d overstiger ikke det største af de to tal – en og dobbelt sinus). Grahams score er optimal for 2 ≤ k ≤ 7, det vil sige, der er billeder, for hvilke værdier opnås fra højre side af denne ulighed. Til store værdier k Det angivne skøn er unøjagtigt, fordi det giver d ≤ 1, og faktisk er den største af de mulige værdier af den minimale afstand mellem punkter strengt mindre end 1.

Den naturlige generalisering af vores opgave er at finde de cirkler af den mindste radius, som du kan sætte N enkeltcirkler (eller ækvivalent søgen efter en løsning på minimaxproblemet ved N punkter i enhedens cirkel). I denne søgning fokuserede matematikernes indsats på to retninger: computer modellering og Bevis for optimalitet. Nedenfor i fig. 5 viser nogle indlysende optimale billeder.

Fig. 5

Optimaliteten af ​​de første tre af dem følger af ovenstående resultat af R. Graham. Den sidstnævnte (i 8 cirkler) blev vist i 1963 af nederlandskeren Boele L.J. Braaksma i sin afhandling under det svære at udtale sig "Asymptotiske forlængelser og analytiske fortsættelser for en klasse Barnes integraler". Den næste forfremmelse samt optimitet er et sådant billede (figur 6) med to indre cirkler (for 10 cirkler)

Fig. 6

Den blev modtaget af tyske U. Pirl i 1969. Optimaliteten af ​​et lignende billede til 11 omgange er bevist 25 år senere, og i 12, 13 og 19 omgange – selv senere (den sidste af resultaterne var i 2003).

Og … alt. De resterende resultater på emballagen af ​​cirkler i en cirkel i dag er i en tilstand af "optimitet er antaget, men ikke bevist." Så se bare på billederne (fig.7) med påvist optimitet (N = 12 og N = 19) og skøn: Kun 15 år siden var det en terra incognita, begge opgaver venter stadig på deres solver.

Fig. 7

Og de følgende to billeder (for N = 14 og N = 15) er denne "inkognito" selv nu (figur 8). Gå efter det.

Fig. 8

Se også:
1) Cirkelpakning i en cirkel ("Pakkercirkler i en cirkel"). Nok detaljeret artikel i engelsk Wikipedia.
2) Cirkler i cirkler. Siden på Eric Friedman, hvorfra vi lånte de fleste af illustrationerne. På samme sted, på pakningscentrets tilstødende sider, beskrives andre pakningsopgaver.
3) K. A. Dowsland, M. Gilbert, G. Kendall. En lokal søgemetode til motorcykelindustrien (PDF, 346 Kb). Artikel i et videnskabeligt tidsskrift Operations Research Society – Det internationale samfund beskæftiger sig med undersøgelsen af ​​operationer, det vil sige videnskabelig disciplin, hvis hovedopgave er at retfærdiggøre den optimale anvendelse af videnskabelige resultater i praksis.
Artiklen forklarer hvordan man optimerer fremstillingen af ​​"stjerner" og andre formede hjul (til gear osv.) Til fremstilling af cykler og motorcykler. Fra matematikens synspunkt er absolut intet nyt, men forbindelsen med praksis er meget sjov. Jeg spekulerer på, om der nogensinde vil være en lignende artikel for husmødre – om at optimere udfoldningen af ​​kødboller i en stegepande?


Like this post? Please share to your friends:
Skriv et svar

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: