Apskritimai apskritime • Konstantinas Knoopas • Mokslinės-populiarios "Elementų" problemos • Matematika

Ratai ratu

Užduotis

Koks mažiausias apskritimo spindulys, kuriame gali būti dedami 7 viengubi ratai be persidengimų? Pateikite savo atsakymą.

Pastaba Vieneto ratas – apskritimas spinduliu 1. "Nėra perdangų"reiškia, kad apskritimai gali liesti, bet neturėtų turėti bendrų interjero taškų.


1 patarimas

Spindulys yra 3, o "optimalus vaizdas" atrodo tiksliai taip, kaip jūs greičiausiai jį įsivaizdavote (1 pav.).

Pav. 1


2 patarimas

Patogu atsikratyti "perdangos" sąvokos, perėję iš šios užduoties į šį:
Apsvarstykite vietoj apskritimų tik jų centrus. Kuo mažiausio spinduliu galite juos visus pritaikyti?

Pav. 2

"Optimaliame paveikslėlyje" visi centrai yra viršūnės ir reguliariai šešiakampio su šonu 2 centras (2 pav.). Tuo pat metu atstumas tarp bet kurių dviejų viršūnių ir tokio šešiakampio centro taip pat yra 2, taigi visi taškai yra apskritimo spinduliu 2. Būtina įrodyti, kad visi šie taškai negali tilpti į mažesnio spindulio ratą. Norėdami tai padaryti, stenkitės išnagrinėti konkrečius atvejus, kiek (iš šešių taškų, kurie skiriasi nuo centro) yra išgaubtas daugiakampis.


Sprendimas

Mes veiksime pagal "priešingą" metodą. Tarkime, kad šeši taškai su pora atstumu 2 (arba daugiau nei du) sugebėjo įterpti į spindulio ratą R <2.Padarykite homothety su koeficientu 1 /R. Tada šis ratas taps vienu.

Homothety (iš graikų kalbos Homos – lygūs, identiški, abipusiai, bendri ir Thetos – įsikūręs) yra plokštumos transformacija, kurioje kiekvienas taškas M tam tikras taškas yra priskirtas M"gulėti" OMkur Oi – fiksuotas taškas ir santykis OM\’ : OM = k (homothety koeficientas) yra vienodas visiems taškams M. Su homothety kiekvienas paveikslas pasikeičia į panašią, ir visi atstumai tarp taškų tiksliai keičia k kartus

Žemiau mes tai įrodyti jei 6 taškai yra vieneto apskritime, atstumas tarp bet kurių dviejų iš jų neviršija 1. Tai reiškia, kad prieš homothety atstumas tarp bet kurių dviejų taškų neviršijo R, tai yra, ji buvo mažesnė už 2. Segmento vidurys tarp šių dviejų taškų yra nuo segmento galų mažesniu nei 1 atstumu, ty kiekvieno vieneto viduje, kurio viduryje yra šie galai. Kitaip tariant, šie vienetiniai apskritimai sutampa. Kontradicija.

Lemma Jei vienetiniame apskritime yra 6 taškai, atstumas tarp bet kurių dviejų iš jų neviršija 1.

Įrodymas.

1. Pirma, mes pastebime, kad jei kas nors iš šešių taškų (mes tai pažymėti X) lieka viduje poilsio (matematikai sako: "viduje kitų išgaubtų korpusų"), tada atstumas nuo jo iki vienos iš kitų yra ne daugiau kaip 1.

Iš tikrųjų, jei į išgaubtą korpusą pateks tik du taškai, tada visi kiti taškai yra segmento. Šio segmento ilgis yra ne daugiau kaip 2, taigi, jei į jį įdėkite tašką, atstumas nuo jo iki vieno iš segmento galų bus ne didesnis kaip 1.

Jei išgaubtoje korpuse yra bent trys taškai, tuomet jūs visada galite pasirinkti tris iš jų, tarkim, A, B, C tokiu būdu, kad X priklauso išgaubtų taškų korpusui A, B, Ctai yra slypi trikampyje ABC. Tačiau bet kuris šio trikampio taškas yra vieneto apskritimas su centru viename iš trikampio viršūnių (žr. 3 pav.).

Pav. 3 Kiekvieną trikampio viršūnę traukia apskritimas, kurio spindulys 1 yra. Kiekvienas trikampio taškas yra nudažytas bent vienos spalvos, ty jis yra padengtas bent vienu iš ratų.

Taigi, šiuo atveju (vienas iš šešių taškų yra viduje kitų išgaubtų korpusų), tvirtinimas jau buvo įrodytas.

2. Dabar tarkime, kad išgaubtas korpusas apima visus 6 taškus.

Jei kuri nors iš jų (tarkim, A) nėra ant apskritimo ribos, tada jis gali būti perkeltas į ribą taip, kad atstumas iki kitų taškų nesumažėtų.Tai gali būti padaryta, pavyzdžiui, A akordas atskyrimas A iš likusių taškų ir tada juda A ant krašto apskritimo, statmenojo šiam akordui (4 pav.).

Pav. 4

Paaiškinimas fig. 4 B ir C yra taškus iš apačia, kuris yra arčiausiai A (bet daroma prielaida, kad jie jau yra apskritime, nors tai nėra taip svarbu). Tada BAC kampas yra mažesnis nei 180 °. Tai reiškia, kad per A galite parinkti FG akordą taip, kad B ir C taškai būtų vienoje pusėje.

Taip pat galite piešti AH statmenai FG ir perkelti tašką A į tašką H. Kadangi kampai BAH ir CAH buvo didesni nei FAH ir GAH, jie abu yra tušti, o tai reiškia, kad didžiausia pusė yra trijose BAH ir CAH. Kitaip tariant, BH> BA ir CH> CA. Tai reiškia, kad nuo A iki H poslinkio padidėjo atstumai iki B ir C taškų.

Galiausiai, jei visi taškai yra vieneto apskritime, jie padalijami į 6 lankus, todėl mažiausių lankų ilgis yra ne daugiau kaip 1/6 apskritimo, tai yra, ne daugiau kaip 2π / 6. Tai reiškia, kad šio lanko centrinio kampo dydis taip pat neviršija 2π / 6, o tai reiškia, kad atstumas tarp dviejų taškų, kurie yra šios lanko galai, yra ne didesnis kaip 2sin (π / 6) = 1.


Po žodžio

Ši užduotis yra didžiulės klasės vadinamųjų "minimalaus" skaičiavimo geometrijos problemų pavyzdys.Minimalių problemų atveju ieškoma didžiausios galimos tam tikro kiekio vertės, kuri pati yra apibrėžiama kaip mažiausias kito kiekio vertes. Mūsų atveju minimax problema (į kurią mes sumažinome pradinę) buvo: pirma, tarp visų 15 pora atstumų tarp šešių taškų vieneto apskritime, buvo pasirinkta mažiausia, o tada nustatoma šešių taškų konfigūracija, kurios šis atstumas yra maksimalus.

Mūsų teiginys ir jo įrodymas priklauso žinomam amerikiečių matematikui Ronaldui Grahamui, paskelbtam 1968 m. Graham įrodė, kad dar mažesnis atstumas yra dar paprastesnis d tarp kai kurių k taškai yra vieneto apskritime. Šis įvertinimas yra

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

(t. y. d neviršija didžiausio iš dviejų skaičių – vienas ir dvigubas sinusas). Graham'o rezultatas yra optimalus 2 ≤ k ≤ 7, tai yra, yra nuotraukos, kurių vertės gaunamos dešinėje šios nelygybės pusės. Didelėms vertėms k nurodytas įvertinimas yra netikslus, nes jis suteikia d ≤ 1 ir iš tikrųjų didžiausias galimas minimalaus atstumo tarp taškų skaičius yra griežtai mažesnis kaip 1.

Natūralus mūsų užduoties apibendrinimas – surasti mažiausio spindulio, kurį galite įdėti, ratus N vienkartiniai ratai (arba, lygiaverčiai, minimax problemos sprendimo ieškojimas N nurodo vieneto ratą). Šioje paieškoje matematikų pastangos buvo orientuotos į dvi kryptis: kompiuterinis modeliavimas ir optimalumo įrodymai. Žemiau pav. 5 parodyta keletas akivaizdžių optimalių nuotraukų.

Pav. 5

Pirmųjų trijų iš jų optimalus rezultatas yra aukščiau pateiktas R. Grahamo rezultatas. Jo optimizmą (8 apskritimams) 1963 m. Įrodė olandas Boele L.J. Braaksma savo disertacijoje pagal sunkiai ištinkamą pavadinimą "Asimptotiniai pratęsimai ir analitiniai tęsimai vienai klasei Barneso integralų". Kitas skatinimas, taip pat optimumas, yra toks vaizdas (6 pav.) Su dviem vidiniais ratais (10 apskritimų)

Pav. 6

Tai buvo gauta vokiečių U. Pirl 1969 m. Panašios nuotraukos optimizavimas 11 ratų yra įrodytas po 25 metų, o 12, 13 ir 19 ratų – dar vėliau (paskutinis rezultatas buvo 2003 m.).

Ir … viskas. Visi likę rezultatai apskritimų pakuotei šiuo metu yra "optimalumo prielaida, bet jų neįrodyta". Taigi tiesiog pažvelk į nuotraukas (pav.7) su įrodytu optimumu (N = 12 ir N = 19) ir apskaičiuoti: tik prieš 15 metų tai buvo terra incognita, abu uždaviniai vis dar laukia jų sprendimo.

Pav. 7

Ir šios dvi nuotraukos (už N = 14 ir N = 15, atitinkamai) yra ši "inkognito" net ir dabar (8 pav.). Eik tai

Pav. 8

Taip pat žiūrėkite:
1) Apskritimas pritvirtintas ratu ("Aplinke esantys pakavimo ratai"). Gana išsamus straipsnis angliškai Wikipedia.
2) Draugų ratai. Erico Friedmano puslapis, iš kurio mes pasiskolinome daugumą iliustracijų. Toje pačioje vietoje, gretimuose pakavimo centro puslapiuose, aprašomos kitos pakavimo užduotys.
3) K. A. Dowsland, M. Gilbert, G. Kendall. Vietos paieškos metodas motociklų pramonei (PDF, 346 Kb). Straipsnis mokslo žurnale Operacijų tyrimų draugija – tarptautinė bendruomenė, vykdanti operacijų tyrimą, tai yra, mokslinė disciplina, kurios pagrindinė užduotis – pateisinti bet kokių mokslinių pasiekimų optimalų pritaikymą praktikoje.
Straipsnyje paaiškinama, kaip optimizuoti "žvaigždžių" ir kitų formų ratų gamybą (įrankių ir kt.) Gaminant dviračius ir motociklus. Matematikos požiūriu visiškai nieko naujo, bet ryšys su praktika yra labai juokingas. Įdomu, ar kada nors bus panašus straipsnis namų šeimininkėms – apie kiaušinių sudėtines kukulių rinkimo optimizavimą?


Like this post? Please share to your friends:
Parašykite komentarą

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