Körök egy körben • Konstantin Knoop • Tudományos-népszerű problémák a "Elemeken" • Matematika

Körök egy körben

feladat

Mi a legkisebb sugara egy körben, amelyben 7 egykörös kört helyezhet el átfedések nélkül? Indokolja meg a választ.

Megjegyzés. Egységkör – 1. kör sugara. "Nincsenek átfedések"azt jelenti, hogy a körök megérinthetnek, de nem rendelkeznek közös belső pontokkal.


Tipp 1

A sugár 3 és az „optimális kép” úgy néz ki, pontosan úgy, ahogy azt elképzelni, valószínűleg, és bemutatott (1.).

Ábra. 1


2. tipp

Célszerű, hogy megszabaduljon a „bevezetését” fogalmának, mozgó ezt a problémát a következő:
A körök helyett csak a központokat gondolják. Ami a legkisebb sugarat illeti, mindegyiket illesztheti?

Ábra. 2

A „legjobb kép” a központok a csúcsai és a közepén egy szabályos hatszög egy oldalon 2 (ábra. 2). A távolság két csúcsot és a központ a hatszög is egyenlő 2, úgy, hogy minden pont egy körön 2. Meg kell bizonyítani, hogy ezeket a pontokat nem lehet összefoglalni egy kört kisebb sugarú. Ehhez próbálja meg azt az esetet, hogy hány (a hat nem-center) pont egy konvex sokszög.


döntés

Az "ellenkező" módszerével fogunk cselekedni. Tegyük fel, hogy hat pont a páros távolság 2 (kettő vagy több) lehet helyezni a körön R <2.Homothety egy 1 /R. Ekkor ez a kör lesz egyetlen.

dil (görögül homók – egyenlő, azonos, kölcsönös, közös és thetos – elhelyezve) a transzformáció a sík, amelyen minden pont M valamilyen pont van hozzárendelve M"fekszik OMahol Oh – rögzített pont, és az arány OM\’ : OM = k (homothety-együttható) ugyanaz minden pontnál M. Homothety, minden alak változik egy hasonló, és minden távolság közötti pontok pontosan megváltozik k időben.

Az alábbiakban azt bizonyítjuk Ha 6 pont található az egységkörben, akkor a kettő közül kettő közötti távolság nem haladja meg az 1-et. Ez azt jelenti, hogy a homotétika előtt a két pont közötti távolság nem haladta meg a maximumot R, vagyis kevesebb volt, mint 2. A szegmens középpontja e két pont között a szegmens végeinél kisebb, mint 1, azaz mindegyik egységkörön belül, ahol ezek a központok vannak. Más szavakkal, ezek az egyes körök átfedik egymást. Ellentmondás.

Lemma. Ha 6 pont található az egységkörben, akkor bármelyik kettő közötti távolság nem haladja meg az 1-et.

Bizonyítás.

1. Először megjegyezzük, hogy ha a hat pont közül bármelyik (mi azt jelöljük X) a többiek között van (a matematikusok azt mondják: "a többiek konvex burkolatán belül"), akkor a távolság az egyikhez képest több mint 1.

Valóban, ha csak két pont lép be a konvex hajótestbe, akkor az összes többi pont a szegmensben helyezkedik el. Ennek a szegmensnek a hossza nem haladja meg a 2-et, ezért ha pontot helyez, akkor a szegmens egyik végétől mért távolság nem több, mint 1.

Ha a domború héjban legalább három pont van, akkor mindig három közül választhat, mondjuk: A, B, C oly módon, hogy X a pontok konvex hullámához tartozik A, B, Cazaz egy háromszögben fekszik ABC. De ennek a háromszögnek bármely pontja a háromszög egyik csúcsa középpontjában található egységkörben van (lásd 3. ábra).

Ábra. 3. A háromszög minden csúcsából egy sugár 1-es körét rajzoljuk, a háromszög minden egyes pontját legalább egy színben festjük, vagyis legalább a körök egyikével.

Így ebben az esetben (a hat pont közül az egyik a konvex burkolat belsejében található), az állítás már bizonyított.

2. Tegyük fel, hogy a konvex burkolat mind a 6 pontot tartalmazza.

Ha bármelyikük (mondjuk, A) nem fekszik a kör határain, akkor áthelyezhető a határba, így a többi ponttól való távolság nem csökken.Ezt például a A akkord elválasztása A a többi ponttól, majd mozog A az ezen az akkordra merőleges határoló körön (4.

Ábra. 4

Magyarázat a 6. ábrára. 4. B és C az A-hoz legközelebbi konvex hajópont pontjai (feltételezzük, hogy már körkörös, de ez nem annyira fontos). Ezután a BAC szöge 180 ° -nál kisebb. Ez azt jelenti, hogy az A-n keresztül húzhatunk egy FG-akkordot úgy, hogy a B és C pontok az egyik oldalán legyenek.

Az AH merőleges lehet az FG-re is, és az A pontot a H. pontig mozgathatja. Mivel a BAH és a CAH szög nagyobb volt, mint a FAH és a GAH, mindkettő elmosódott, ami azt jelenti, hogy a legnagyobb oldal a BAH és a CAH háromszögek közé tartozik. Más szavakkal: BH> BA és CH> CA. Vagyis az A-tól H-ig terjedő eltolódással a B és C pontok közötti távolság növekedett.

Végül, ha minden pont az egységkörön fekszik, akkor 6 ívre oszlik, ezért a legkisebb ívek hossza nem haladja meg a kerület 1/6-át, azaz legfeljebb 2/6-ot. Ez azt jelenti, hogy ennek az ívnek a központi szöge nem haladja meg a 2π / 6 értéket, ami azt jelenti, hogy a két pont közötti távolság, amely ennek az ívnek a vége, nem nagyobb, mint 2sin (π / 6) = 1.


utószó

Ez a feladat egy példa a számítási geometriák úgynevezett "minimax" problémáira.A minimax-problémákban keresik a lehető legnagyobb mennyiségű értéket, amelyet maga a másik mennyiség legkisebb értéke határoz meg. Esetünkben a minimax-probléma (amelyre az eredetiet csökkentettük) volt: először a legkisebbet választottuk ki az egységkör 6 pontjának mind a 15 páronkénti távolsága között, majd hatpontos konfigurációt találunk, amelyre ez a távolság a lehető legnagyobb.

Nyilatkozatunk és bizonyítéka a Ronald Graham figyelemre méltó matematikus, 1968-ban jelent meg. Graham egy még általánosabb becsléssel bizonyította a legkisebb távolságot d között néhány k pontok az egységkörben fekszenek. Ez a minősítés

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

(Ez azt jelenti, d nem haladja meg a két szám közül a legnagyobbat – egy és két szinuszot). Graham pontszám 2 ≤ optimális k ≤ 7, vagyis vannak olyan képek, amelyekért ezen egyenlőtlenségek jobb oldaláról érkeznek értékek. Nagy értékek esetén k a megadott becslés pontatlan, mert ad d ≤ 1, és valójában a pontok közötti legkisebb távolság lehetséges értékeinek legnagyobb értéke szigorúan kevesebb, mint 1.

Feladatunk természetes elterjedése az, hogy megtaláljuk a legkisebb sugarú köröket, amelyekbe tehetjük N egykörös körök (vagy ezzel egyenértékű módon a minimax probléma megoldásának keresése N pont az egységkörben). Ebben a kutatásban a matematikusok erőfeszítései két irányban irányultak: számítógépes modellezés és az optimális bizonyítékok. Az alábbiakban a 6. ábrán látható. Az 5. ábra néhány nyilvánvaló optimális képet mutat.

Ábra. 5

Az első három közülük optimális az R. Graham fenti eredményéből. Az utóbbi optimumát (8 kört) 1963-ban a holland Boele L.J. Braaksma doktori értekezésében a "Az aszimptotikus kiterjesztések és az analitikus folytatások egy osztályú Barnes integrálok" -nak nevezték el. A következő promóció, valamint az optimizmus egy ilyen kép (6. Ábra) két belső körrel (10 körhöz)

Ábra. 6

1969-ben fogadta el a német U. Pirl. A hasonló kép 11 körre való optimálissága 25 évvel később, 12, 13 és 19 körben – még később is (az utolsó eredmény 2003-ban volt).

És … mindent. A fennmaradó eredmények a körök csomagolásán a mai körben olyan állapotban vannak, hogy "az optimitás feltételezett, de nem bizonyított". Tehát csak nézd meg a képeket (2.7) bizonyítottan optimális (N = 12 és N = 19), és becslést: csak 15 évvel ezelőtt egy terra incognita volt, mindkét feladat még mindig megvárta a megoldóját.

Ábra. 7

És a következő két kép (a N = 14 és N = 15, vagyis) ez az "inkognitó" még most is (8. Menj rá.

Ábra. 8

Lásd még:
1) Kör körben csomagolva ("Csomagolási körök egy körben"). Elég részletes cikk az angol Wikipédiában.
2) Körök a körökben. Eric Friedman oldala, ahonnan kölcsönöztük a legtöbb illusztrációt. Ugyanazon a helyen, a csomagolóközpont szomszédos oldalain más csomagolási feladatokat ismertetnek.
3) K. A. Dowsland, Gilbert M., G. Kendall. A motorkerékpár-ipar helyi keresési módszere (PDF, 346 Kb). Cikk egy tudományos folyóiratban Operációs Kutató Társaság – A nemzetközi közösség részt vesz a műveletek tanulmányozásában, azaz a tudományos fegyelemben, amelynek fő feladata a gyakorlatban bármely tudományos eredmény optimális alkalmazása.
A cikk bemutatja, hogyan optimalizálható a "csillagok" és más alakú kerekek gyártása (a fogaskerekek stb.) Kerékpár és motorkerékpár gyártása során. A matematika szempontjából teljesen semmi új, de a kapcsolat a gyakorlatban nagyon vicces. Kíváncsi vagyok, vajon lesz-e valaha hasonló cikk a háziasszonyoknak – a húslabdák palacsintákban való kibontakoztatásának optimalizálásáról?


Like this post? Please share to your friends:
Vélemény, hozzászólás?

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