Yksinäisen juoksijan hypoteesi

Peliteoriassa , erityisesti diofantiiniapproksimaatioiden tutkimuksessa , yksinäisen juoksijan olettamus on JM Willsin vuonna 1967 esittämä olettamus. Arvauksen sovellukset ovat laajalle levinneet matematiikassa, mukaan lukien näkörajoitusongelmat [ 1 ] ja kromaattisen lukumäärän laskeminen . etäisyys- ja ympyräkaaviot [ 2] . Hypoteesi sai kuvaannollisen nimen Goddinin (L. Goddyn) ansiosta vuonna 1998 [3] .

Hypoteesi

Olkoon k juoksijaa yksikköpituista ympyrämäistä polkua pitkin. Tällä hetkellä t  = 0, kaikki juoksijat olivat samassa pisteessä ja lähtivät juoksemaan. Juoksijoiden nopeus on pareittain erilainen. Juoksijan A sanotaan olevan yksin hetkellä t , jos hän on vähintään 1/ k etäisyydellä kaikista muista juoksijoista. Hypoteesi väittää, että jokainen pelaaja tulee olemaan yksinäinen jossain vaiheessa. [neljä]

Ongelman tavallinen muotoilu olettaa, että juoksijoilla on kokonaislukuina ilmaistu nopeudet, jotka eivät ole jaollisia samalla alkuluvulla. Pelaajalla, jonka pitäisi olla yksin, on nollanopeus. Oletuksen mukaan jos D on mielivaltainen joukko positiivisia kokonaislukuja, joka sisältää täsmälleen luvun, jonka suurin yhteinen jakaja on yhtä suuri kuin 1, niin

jossa tarkoittaa etäisyyttä luvusta x lähimpään kokonaislukuun.

Merkittäviä tuloksia

Ratkaisemattomat matematiikan ongelmat : Onko mahdollista todistaa yksinäisen juoksijan arvelu k≥8:lle?
k todiste vuosi joka todisti huomautukset
yksi - - triviaali: t = 0; mille tahansa t
2 - - triviaali: t = 1 / (2 * ( v 1 - v 0 ))
3 - - Mikä tahansa todistus k >3:lle todistaa myös k =3
neljä 1972 Bethke ja Wills; [5] Kuzik [6] -
5 1984 Kuzik ja Pomerants; [7] Bienya ym. [3] -
6 2001 Bohman, Holzman, Kleitman; [8] Renault [9] -
7 2008 Barayas ja Serra [2] -

Vuonna 2011 todistettiin, että riittävän suurelle määrälle juoksijoille nopeuksia , jos hypoteesi täyttyy [10] .

Muistiinpanot

  1. ↑ TW Cusick. Näkymä-esteongelmat // Aequationes Math .. - 1973. - T. 9 , no. 2-3 . - S. 165-170 . - doi : 10.1007/BF01832623 .
  2. ↑ 1 2 J. Barajas ja O. Serra. Yksinäinen juoksija seitsemän juoksijan kanssa // The Electronic Journal of Combinatorics. - 2008. - T. 15 . - S. R48 .
  3. ↑ 1 2 W. Bienia et ai. Virtaukset, näkymän esteet ja yksinäisen juoksijan ongelma // Kombinatoriaalisen teorian sarja B. - 1998. - T. 72 . - S. 1-9 . - doi : 10.1006/jctb.1997.1770 .
  4. ↑ Stuart, 2015 , s. 407.
  5. ↑ Betke U. , Wills JM Untere Schranken für zwei diophantische Approximations-Funktionen  (saksa)  // Monatshefte für Mathematik. - 1972. - Juni ( Bd. 76 , Nr. 3 ). - S. 214-217 . — ISSN 0026-9255 . - doi : 10.1007/BF01322924 .
  6. ↑ TW Cusick. Näkymän estoongelmat n-ulotteisessa geometriassa // Journal of Combinatorial Theory, Series A. - 1974. - V. 16 , no. 1 . - S. 1-11 . - doi : 10.1016/0097-3165(74)90066-1 .
  7. ↑ Cusick TW , Pomerance Carl. Näkymän estoongelmat, III  (eng.)  // Journal of Number Theory. - 1984. - lokakuu ( osa 19 , nro 2 ) . - s. 131-139 . - ISSN 0022-314X . - doi : 10.1016/0022-314X(84)90097-0 .
  8. ↑ T. Bohman, R. Holzman, D. Kleitman. Kuusi yksinäistä juoksijaa // Electronic Journal of Combinatorics. - 2001. - T. 8 , no. 2 .
  9. ↑ Renault Jérome. Näkymän esto: lyhyempi todiste 6 yksinäiselle juoksijalle  //  Discrete Mathematics. - 2004. - lokakuu ( nide 287 , nro 1-3 ). - s. 93-101 . — ISSN 0012-365X . - doi : 10.1016/j.disc.2004.06.008 .
  10. ↑ Dubickas, A. Monen juoksijan yksinäisen juoksijan ongelma  (neopr.)  // Glasnik Matematicki. - 2011. - T. 46 . - S. 25-30 . - doi : 10.3336/gm.46.1.05 .

Ulkoiset linkit

Kirjallisuus