22 красавiка 2024, панядзелак, 6:30
Падтрымайце
сайт
Сім сім,
Хартыя 97!
Рубрыкі

Матэматыкі рашылі «задачу пра незнаёмцаў», над якой навукоўцы біліся амаль 100 гадоў

14
Матэматыкі рашылі «задачу пра незнаёмцаў», над якой навукоўцы біліся амаль 100 гадоў

Прафесар, які рашыў яе, шукаў адказ са студэнцкай лавы.

Любы матэматычны аб'ект (напрыклад, кампанію з шасці чалавек) можна паказаць у выглядзе графіка: кропак і ліній, якія злучаюць іх. Тэорыя Рамсея, якая развілася са створанай у 1930 годзе тэарэмы, гаворыць, што ў адвольна фармаваных матэматычных аб'ектах у выніку абавязкова назіраецца заканамернасць: у графіку заўсёды ёсць некалькі (не абавязкова ўсе) кропак, кожная з якіх злучаецца з кожнай, ці некалькі кропак, не злучаных адна з адной ніякімі лініямі, піша «Навука».

Прыклад: у кампаніі з шасці чалавек абавязкова знойдзецца як мінімум тры чалавекі, якія адзін з адным знаёмыя. Або наадварот, як мінімум тры чалавекі, якія адзін аднаго не ведаюць. Гэта значыць, 6 – гэта адказ на першую з задачаў Рамсея, умова якой выглядае як r(3,3).

Такіх задачаў некалькі, і яны падобныя структурай: r(s,t), дзе s – злучаныя паміж сабой кропкі, а t – не злучаныя, і трэба высветліць, пры якім ліку сувязі s або нязвязаныя t будуць гарантаваныя. У 1930-я гады, амаль адразу пасля абнародавання тэарэмы Рамсея, рашылі адну з іх: r(4,4) = 18. Адказ для r(5,5) невядомы. Але апошняя, r(4,t), амаль праз 100 гадоў атрымала рашэнне, пра гэта паведамляе Каліфарнійскі ўніверсітэт у Сан-Дыега (ЗША).

Рашыць r(4,t) змаглі прафесар Жак Верстрэтэ і постдактарант Сэм Матэвус. Зрабіць гэта, насамрэч, даволі цяжка, бо ў адрозненне ад папярэдніх функцый у гэтай – не канкрэтны лік, а пераменны t.

«Многія людзі задумваліся пра r(4,t) – гэтай загадцы ўжо больш за 90 гадоў. Але я не рабіў гэтую задачу цэнтрам сваёй даследчай працы, бо ўсе ведаюць, што яна складаная, і ўсе спрабавалі ў ёй разабрацца. Так што без нейкай новай ідэі не было чаго і спрабаваць. На рашэнне гэтай праблемы сапраўды спатрэбіліся гады. І шмат разоў здаралася, што мы захрасалі і задаваліся пытаннем, ці зможам мы ўвогуле рашыць гэтую задачу. Але ніколі не варта здавацца», – сказаў Вэрстрэтэ.

Скончыўшы ўніверсітэт (тэорыю Рамсея праходзяць у рамках універсітэцкай праграмы для матэматыкаў), Верстрэтэ час ад часу вяртаўся да загадкі. У тым ліку чытаў пра яе ў кнізе «Эрдзёш пра графікі: ягоная спадчына задачаў без рашэнняў».

Пал Эрдзёш – вугорскі матэматык, які зрабіў унёсак у развіццё тэорыі Рамсея. Выказаўшы гіпотэзу ў рамках тэорыі, але не знайшоўшы рашэнні ўсіх задачаў, Эрдзёш прапанаваў 250 даляраў першаму, хто зможа рашыць r(4,t). У 1937 годзе вугорскі навуковец адкрыў, што выкарыстанне выпадковых графікаў дае ніжнюю мяжу дыяпазону лікаў, у якім хаваецца ацэнка задачаў Рамсея.

Грунтуючыся на знаходцы Эрдзёша Верстрэтэ блізу чатырох гадоў таму разам з калегам з Універсітэта Ілінойса-Чыкага (ЗША) Дхрувам Мубай выявіў, што выбарка з псеўдавыпадковых графікаў удакладняе гэты дыяпазон. У выніку атрымалася вызначыць верхнія і ніжнія яго значэнні.

Аднак і тады да рашэння r(4,t) было далёка. Верстрэтэ шукаў падказкі ў розных галінах матэматыкі: акрамя камбінаторыкі, да якой адносіцца тэорыя Рамсея, ён звяртаўся да канчатковай геаметрыі, алгебры і тэорыі верагоднасцяў. У выніку ён аб'яднаў намаганні з постдактарантам са сваёй групы, Матэвусам, чыя адукацыя якраз была звязаная з канчатковай геаметрыяй.

«Сэм быў ідэальным чалавекам, які мог прыйсці і дапамагчы стварыць тое, што нам было патрэбна [для пошуку адказу]. Высветлілася, што патрэбную нам псеўдавыпадковую функцыю можна знайсці ў канцовай геаметрыі», – расказвае Верстратэ.

Але нават калі псеўдавыпадковы графік быў гатовы, Вэрстрэтэ і Матэвусу давяшлося разабрацца яшчэ з некалькімі матэматычнымі нюансамі. Гэта заняло амаль год, але ўрэшце яны зразумелі, што знайшлі рашэнне: r(4,t) блізкая да кубічнай функцыі t.

«Калі вы хочаце, каб на вечарынцы дакладна былі чатыры чалавекі, якія ўсе адзін аднаго ведаюць, ці t чалавек, якія не ведаюць адзін аднаго, вам спатрэбіцца запрасіць прыкладна t3 людзей. Тут трэба невялікае ўдакладненне, таму што гэта прыблізны вынік, а не дакладны адказ», – тлумачыцца ў паведамленні.

Верстрэтэ таксама паведаміў, што пасля публікацыі рашэння з ім звязаўся адзін з аўтараў кнігі «Эрдзёш пра графікі: яго спадчына задачаў без рашэнняў», які працуе ў тым самым ўніверсітэце, і сказаў, што вінен яму 250 даляраў – столькі Эрдзёш абяцаў за адказ.

Напісаць каментар 14

Таксама сачыце за акаўнтамі Charter97.org у сацыяльных сетках