Жеміс бақтарын отырғызу проблемасы - Orchard-planting problem

Тоғыз пункттен тұратын келісім Pappus конфигурациясы ) үш нүктелі он сызықты қалыптастыру.

Жылы дискретті геометрия, түпнұсқа бақ отырғызу проблемасы жазықтықтағы нақты нүктелер санының конфигурациясы бойынша қол жеткізілетін 3 нүктелік сызықтардың максималды санын сұрайды. Мұны ағаш отырғызу проблемасы немесе жай бақша проблемасы деп те атайды. К нүктелік сызықтардың қанша болуы мүмкін екендігі туралы зерттеулер де бар. Hallard T. Croft және Paul Erdős дәлелденді т_к > c n² / к³, қайда n нүктелер саны және т_к саны к- нүктелік сызықтар.^[1] Олардың құрылымында m> k болатын бірнеше м-нүктелік сызықтар бар. Бұған рұқсат етілмеген жағдайда сұрақ қоюға болады.

Бүтін реттілік

Анықтаңыз т₃^бақша(n) теңшелімімен қол жеткізуге болатын 3 нүктелік сызықтардың максималды саны болуы керек n ұпай. Ерікті ұпай саны үшін n, т₃^бақша(n) (1/6) болып көрсетілгенn² - O (n) 1974 ж.

-Ның алғашқы бірнеше мәні т₃^бақша(n) келесі кестеде келтірілген (реттілік) A003035 ішінде OEIS ).

Жоғарғы және төменгі шектер

Екі сызық екі нақты нүктені бөлісе алмайтындықтан, а болмашы жоғарғы шекара анықталған 3 нүктелік сызықтардың саны үшін n ұпай болып табылады

${ displaystyle left lfloor { binom {n} {2}} { Big /} { binom {3} {2}} right rfloor = left lfloor { frac {n ^ {2} -n} {6}} right rfloor.}$

Мұны пайдаланып 2 нүктелік жолдар саны кем дегенде 6n/13 (Csima & Sawyer 1993 ж ), бұл жоғарғы шекараны төмендетуге болады

${ displaystyle left lfloor { frac {{ binom {n} {2}} - 6n / 13} {3}} right rfloor = left lfloor { frac {n ^ {2}} { 6}} - { frac {25n} {78}} right rfloor.}$

Үшін төменгі шекаралар т₃^бақша(n) көптеген 3 нүктелік сызықтары бар нүктелер жиынтығы үшін конструкциялармен берілген. ~ (1/8) ең ерте квадраттық төменгі шекарасыn² берген Сильвестр, кім орналастырды n кубтық қисықтағы нүктелер ж = х³. Бұл жақсартылды [(1/6)n² − (1/2)n] 1974 жылы 1 + Бёрр, Грюнбаум, және Слоан  (1974 ) негізделген құрылысты қолдана отырып Вейерштрасс эллиптикалық функциялары. Пайдаланылатын қарапайым құрылыс гипоциклоидтар арқылы табылды Füredi & Palásti (1984) сол төменгі шекке жету.

2013 жылдың қыркүйегінде, Бен Грин және Теренс Дао барлық өлшемдер жиынтығы үшін жеткілікті көлемде екенін дәлелдейтін мақаланы жариялады n > n₀, ең көбі бар ([n(n - 3)/6]  + 1) = [(1/6)n² − (1/2)n + 1] Берр, Грюнбаум және Слоан белгілеген төменгі шекараға сәйкес келетін 3 нүктелі сызықтар.^[2] Бұл олардың төменгі төменгі шекарасынан тікелей шығатын шекарадан сәл жақсы n/ 2 саны үшін 2 нүктелі жолдар: [n(n - 2) / 6], сол мақалада дәлелденген және 1951 жылғы есепті өз бетінше шешкен Габриэль Эндрю Дирак және Теодор Моцкин.

Ескертулер

Әдебиеттер тізімі

• Брас, П .; Мозер, В. О. Дж .; Пач, Дж. (2005), Дискретті геометриядағы зерттеу мәселелері, Springer-Verlag, ISBN  0-387-23815-8.
• Берр, С.; Грюнбаум, Б.; Слоан, Н. (1974), «Бау-бақша мәселесі», Geometriae Dedicata, 2 (4): 397–424, дои:10.1007 / BF00147569.
• Цима, Дж .; Сойер, Э. (1993), «6 барn/ 13 жай ұпай », Дискретті және есептеу геометриясы, 9: 187–202, дои:10.1007 / BF02189318.
• Фюреди, З.; Паласти, И. (1984), «Үшбұрыштар көп болатын түзулер», Американдық математикалық қоғамның еңбектері, 92 (4): 561–566, дои:10.2307/2045427, JSTOR  2045427.
• Жасыл, Бен; Дао, Теренс (2013), «Бірнеше қарапайым сызықтарды анықтайтын жиынтықтар туралы», Дискретті және есептеу геометриясы, 50 (2): 409–468, arXiv:1208.4714, дои:10.1007 / s00454-013-9518-9

Сыртқы сілтемелер

• Вайсштейн, Эрик В. «Бақша отырғызу мәселесі». MathWorld.