Матэматыкі рашылі «задачу пра незнаёмцаў», над якой навукоўцы біліся амаль 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 даляраў – столькі Эрдзёш абяцаў за адказ.