Problém tří řádků - No-three-in-line problem

Sada 20 bodů v mřížce 10 × 10 bez tří bodů v řadě.

v matematika, v oblasti diskrétní geometrie, ne-tři v řadě problém žádá o maximální počet bodů, které lze vložit do n × n mřížka tak, aby žádné tři body nebyly kolineární. Toto číslo je maximálně 2n, protože pokud 2n +1 body jsou umístěny do mřížky a poté do princip pigeonhole nějaký řádek a nějaký sloupec bude obsahovat tři body. Problém představil Henry Dudeney v roce 1917.

I když lze problém vyřešit pomocí 2n body za každou n až 46, předpokládá se, že méně než 2n body jsou možné pro dostatečně velké hodnoty n. Nejlepší řešení, o nichž je známo, že fungují pro libovolně vysoké hodnoty n místo o něco méně než 3n/ 2 body.

Dolní hranice

Paul Erdős (v Roth 1951 ) poznamenal, že když n je prvočíslo, soubor n body mřížky (i, i² mod n), pro 0 ≤ i < n, neobsahuje žádné tři kolineární body. Když n není primární, lze tuto konstrukci provést pro a p × p mřížka obsažená v n × n mřížka, kde p je největší vrchol, který je nejvýše n. V důsledku toho pro jakékoli ε a jakékoli dostatečně velké n, lze umístit

${ displaystyle (1- epsilon) n}$

body v n × n mřížka bez kolineárního bodu.

Erdősova vazba byla následně vylepšena: Hall a kol. (1975) ukaž, že kdy n/ 2 je prime, lze získat řešení s 3 (n - 2) / 2 body umístěním bodů na hyperbola xy ≡ k (mod n/ 2), kde k lze zvolit libovolně, pokud se nejedná o nenulový režim n/ 2. Opět pro svévolné n jeden může provést tuto konstrukci pro nejlepší blízko n/ 2 k získání řešení s

${ displaystyle left ({ frac {3} {2}} - epsilon right) n}$

bodů.

Vymyšlené horní hranice

Guy & Kelly (1968) domníval se, že pro velké n člověk nemůže udělat lépe než c n s

${ displaystyle c = { sqrt [{3}] { frac {2 pi ^ {2}} {3}}} přibližně 1,874.}$

Pegg (2005) poznamenal, že Gabor Ellmann v březnu 2004 zjistil chybu v původním článku heuristického uvažování Guy a Kelly, která, pokud bude opravena, má za následek

${ displaystyle c = { frac { pi} { sqrt {3}}} přibližně 1,814.}$

Aplikace

The Heilbronnův trojúhelníkový problém žádá o umístění n body v jednotkovém čtverci, který maximalizuje plochu nejmenšího trojúhelníku tvořeného třemi body. Použitím Erdőovy konstrukce sady bodů mřížky bez tří kolineárních bodů lze najít umístění, ve kterém má nejmenší trojúhelník plochu

${ displaystyle { frac {1- epsilon} {2n ^ {2}}}.}$

Zobecnění

Vyšší rozměry

Nekolineární sady bodů v trojrozměrné mřížce byly považovány za Pór & Wood (2007). Dokázali, že maximální počet bodů v n × n × n mřížka bez tří kolineárních je ${ displaystyle Theta (n ^ {2})}$. Podobně jako u Erdőovy 2D konstrukce toho lze dosáhnout použitím bodů (X, y, X² + y²) mod p, kde p je vrcholný shodný s 3 mod 4.

Dalším analogem ve vyšších dimenzích je najít sady bodů, které ne všechny leží ve stejné rovině (nebo nadrovině). U ne-čtyřkoplanárního problému ve třech rozměrech to hlásil Ed Pegg „Oleg567 a kol., Že v mřížce 3x3x3 lze vybrat 8 takových bodů (přesně jedno řešení až do rotace / odraz), 10 takových bodů lze najít pro 4x4x4 (232 různých řešení) a 13 takových bodů lze najít pro 5x5x5 (38 různých řešení).^[1][2] Od roku 2015^{[Aktualizace]}, není známo, jaké je maximální řešení pro mřížku 6x6x6, ani kolik takových řešení existuje. Podobně jako u 2n horní mez pro 2D případ, existuje 3n horní mez pro 3D případ (ne více než 3 body na rovinu a ne více než n takové roviny v mřížce), i když, jak je vidět výše, ne všechny hodnoty n dosáhnout horní hranice.

The sada čepic problém se týká podobného problému ve vysoké dimenzi vektorové prostory přes konečná pole.^[3]

Zobecnění grafů

Nekolineární umístění n body lze také interpretovat jako a kreslení grafu z kompletní graf takovým způsobem, že ačkoliv se hrany protínají, žádná hrana neprochází vrcholem. Erdőovu konstrukci výše lze zobecnit a ukázat, že každý n-vrchol k-barevný graf má takový výkres v a Ó(n) × Ó(k) mřížka (Dřevo 2005 ).

Lze také uvažovat kresby grafů v trojrozměrné mřížce. Zde podmínka nekolinearity znamená, že vrchol by neměl ležet na nesousedící hraně, ale je normální pracovat se silnějším požadavkem, aby se nepřekřížily žádné dvě hrany (Pach, Thiele & Tóth 1998; Dujmović, Morin & Wood 2005; Di Giacomo, Liotta & Meijer 2005 ).

Malé hodnoty n

Pro n ≤ 46, je známo, že 2n body mohou být umístěny bez tří v řadě. Počet řešení (nepočítaje různé odrazy a rotace) pro malé n = 2, 3, ..., jsou

1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, ... (sekvence A000769 v OEIS ).

Poznámky

Reference

• Dudeney, Henry (1917). „317. Puzzle s pěšci“. Zábava v matematice. Edinburgh: Nelson. str. 94.CS1 maint: ref = harv (odkaz). Řešení, str. 222.
• Di Giacomo, Emilio; Liotta, Giuseppe; Meijer, Henk (2005). "Výpočet lineárních 3D mřížkových výkresů grafů v lineárním objemu". Výpočetní geometrie: Teorie a aplikace. 32 (1): 26–58. doi:10.1016 / j.comgeo.2004.11.003.CS1 maint: ref = harv (odkaz)
• Dujmović, Vida; Morin, Pat; Wood, David R. (2005). "Rozložení grafů s ohraničenou šířkou stromu". SIAM Journal on Computing. 34 (3): 553–579. arXiv:cs / 0406024. doi:10.1137 / S0097539702416141.CS1 maint: ref = harv (odkaz)
• Felsner, Stefan; Liotta, Giuseppe; Wismath, Stephen K. (2003). „Přímé kresby na omezených celočíselných mřížkách ve dvou a třech rozměrech“ (PDF). Journal of Graph Algorithms and Applications. 7 (4): 363–398. doi:10,7155 / jgaa 00075.CS1 maint: ref = harv (odkaz)
• Flammenkamp, ​​Achim (1992). „Pokrok v problému ne tři v řadě“. Journal of Combinatorial Theory. Řada A. 60 (2): 305–311. doi:10.1016 / 0097-3165 (92) 90012-J.CS1 maint: ref = harv (odkaz)
• Flammenkamp, ​​Achim (1998). "Pokrok v problému ne tři v řadě, II". Journal of Combinatorial Theory. Řada A. 81 (1): 108–113. doi:10.1006 / jcta.1997.2829.CS1 maint: ref = harv (odkaz)
• Guy, R. K.; Kelly, P. A. (1968). "Problém ne-tři v řadě". Kanadský matematický bulletin. 11 (0): 527–531. doi:10.4153 / CMB-1968-062-3. PAN  0238765.CS1 maint: ref = harv (odkaz)
• Hall, R. R.; Jackson, T. H .; Sudbery, A .; Wild, K. (1975). „Některé pokroky v problému ne tři v řadě“. Journal of Combinatorial Theory. Řada A. 18 (3): 336–341. doi:10.1016/0097-3165(75)90043-6.CS1 maint: ref = harv (odkaz)
• Lefmann, Hanno (2008). "Ne l Body mřížky v prostorech malého rozměru ". Algoritmické aspekty v oblasti informací a managementu, 4. mezinárodní konference, AAIM 2008, Šanghaj, Čína, 23. – 25. Června 2008, sborník. Přednášky z informatiky. 5034. Springer-Verlag. 259–270. doi:10.1007/978-3-540-68880-8_25.CS1 maint: ref = harv (odkaz)
• Pach, János; Thiele, Torsten; Tóth, Géza (1998). Msgstr "Trojrozměrné mřížkové kresby grafů". Kresba grafu, 5. Int. Symp., GD '97. Přednášky z informatiky. 1353. Springer-Verlag. 47–51. doi:10.1007/3-540-63938-1_49.CS1 maint: ref = harv (odkaz)
• Pegg, Ed Jr. (11. dubna 2005). „Matematické hry: Úkoly na šachovnici“. Citováno 25. června 2012.CS1 maint: ref = harv (odkaz)
• Pór, Attila; Wood, David R. (2007). „No-three-in-line-in-3D“. Algorithmica. 47 (4): 481. doi:10.1007 / s00453-006-0158-9.CS1 maint: ref = harv (odkaz)
• Roth, K.F. (1951). „Na problém Heilbronnu“. Journal of the London Mathematical Society. 26 (3): 198–204. doi:10.1112 / jlms / s1-26.3.198.CS1 maint: ref = harv (odkaz)
• Wood, David R. (2005). "Mřížkové výkresy k-barevné grafy ". Výpočetní geometrie: Teorie a aplikace. 30 (1): 25–28. doi:10.1016 / j.comgeo.2004.06.001.CS1 maint: ref = harv (odkaz)

externí odkazy

• Flammenkamp, ​​Achim. „Problém č. 3 v řadě“.
• Weisstein, Eric W. „Problém se třemi v řadě“. MathWorld.