Problem med fruktodlingsplantering
I diskret geometri kräver det ursprungliga planteringsproblemet för fruktträdgårdar det maximala antalet 3-punktslinjer som kan uppnås genom en konfiguration av ett specifikt antal punkter i planet. Det kallas också för trädplanteringsproblemet eller helt enkelt fruktodlingsproblemet. Det finns också undersökningar om hur många k -punktslinjer det kan finnas. Hallard T. Croft och Paul Erdős bevisade t k > c n 2 / k 3 , där n är antalet punkter och t k är antalet k -punktslinjer. Deras konstruktion innehåller några m -punktslinjer, där m > k . Man kan också ställa frågan om dessa inte är tillåtna.
Heltalssekvens
Definiera t 3 fruktträdgård ( n ) som det maximala antalet 3-punktslinjer som kan uppnås med en konfiguration av n punkter. För ett godtyckligt antal poäng n , t 3 fruktträdgård ( n ) vara (1/6) n 2 − O(n) 1974.
De första värdena för t 3 fruktträdgård ( n ) ges i följande tabell (sekvens A003035 i OEIS ).
| n | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| t 3 fruktträdgård ( n ) | 1 | 2 | 4 | 6 | 7 | 10 | 12 | 16 | 19 | 22 | 26 |
Övre och nedre gränser
Eftersom inga två linjer får dela två distinkta punkter, är en trivial övre gräns för antalet 3-punktslinjer som bestäms av n punkter
Genom att använda det faktum att antalet 2-punktslinjer är minst 6 n /13 ( Csima & Sawyer 1993) , kan denna övre gräns sänkas till
Nedre gränser för t 3 fruktträdgård ( n ) ges av konstruktioner för uppsättningar av punkter med många 3-punktslinjer. Den tidigaste kvadratiska nedre gränsen för ~(1/8) n 2 gavs av Sylvester , som placerade n punkter på den kubiska kurvan y = x 3 . Detta förbättrades till [(1/6) n 2 − (1/2) n ] + 1 1974 av Burr , Grünbaum och Sloane ( 1974 ), med en konstruktion baserad på Weierstrass elliptiska funktioner . En elementär konstruktion med hypocykloider hittades av Füredi & Palásti (1984) som uppnådde samma nedre gräns.
0 I september 2013 publicerade Ben Green och Terence Tao en artikel där de bevisar att för alla punktuppsättningar av tillräcklig storlek, n > n , finns det som mest ([ n ( n - 3)/6] + 1) = [( 1/6) n 2 − (1/2) n + 1] 3-punktslinjer som matchar den nedre gränsen fastställd av Burr, Grünbaum och Sloane. Sålunda, för tillräckligt stort n, är det exakta värdet av t 3 fruktträdgård ( n ) känt.
Detta är något bättre än gränsen som direkt skulle följa av deras snäva nedre gräns på n /2 för antalet 2-punktslinjer : [ n ( n − 2)/6], bevisad i samma artikel och löste ett problem från 1951 poserad oberoende av Gabriel Andrew Dirac och Theodore Motzkin
Problem med fruktodlingsplantering har också övervägts över ändliga fält. I denna version av problemet ligger de n punkterna i ett projektivt plan definierat över ett ändligt fält.( Padmanabhan & Shukla 2020) .
Anteckningar
- Brass, P.; Moser, WOJ; Pach, J. (2005), Research Problems in Discret Geometry , Springer-Verlag, ISBN 0-387-23815-8 .
- Burr, SA ; Grünbaum, B .; Sloane, NJA (1974), "The Orchard problem", Geometriae Dedicata , 2 (4): 397–424, doi : 10.1007/BF00147569 , S2CID 120906839 .
- Csima, J.; Sawyer, E. (1993), "Det finns 6 n /13 vanliga punkter", Discrete and Computational Geometry , 9 (2): 187–202, doi : 10.1007/BF02189318 .
- Füredi, Z .; Palásti, I. (1984), "Arrangemang av linjer med ett stort antal trianglar", Proceedings of the American Mathematical Society , 92 ( 4): 561–566, doi : 10.2307/2045427 , JSTOR 2045427 .
- Grön, Ben ; Tao, Terence (2013), "On sets defining few ordinary lines", Discrete and Computational Geometry , 50 (2): 409–468, arXiv : 1208.4714 , doi : 10.1007/s00454-0813-301 , S21C919, S21C919 , 813-309
- Padmanabhan, R.; Shukla, Alok (2020), "Orchards in elliptic curves over finite fields", Finite Fields and Their Applications , 68 (2): 101756, arXiv : 2003.07172 , doi : 10.1016/j.ffa.1750.10