15 Sayısı Sonsuz Bir Izgaranın Gizli Sınırını Açıklar

Şili Üniversitesi'nde bir lisans öğrencisi olarak, Bernardo Subercaseaux matematik yapmak için bilgisayar kullanmaya karamsar bir bakış attı. Gerçek entelektüel keşfe aykırı görünüyordu.

"Sanki fantastik bir tartışmanın ideal güzelliğine veya zarafetine aykırıymış gibi, problemlerinizi çözmek için bilgisayar kullanmaya karşı bir içgüdü veya içgüdüsel bir tepki var" dedi.

Ancak 2020'de Subercaseaux aşık oldu ve sıklıkla olduğu gibi öncelikleri değişti. Takıntısının amacı, çevrimiçi bir forumda gördüğü bir soruydu. Çoğu sorunu taradı ve unuttu, ama bu dikkatini çekti. Sağa kaydırdı.

"Yaptığım ilk şey, daha sonra başka biri bir çözüm yayınladığında bildirim almayı umarak Facebook grubundaki gönderiyi beğenmek oldu" dedi.

Soru, sonsuz bir ızgarayı sayılarla doldurmakla ilgiliydi. Görünüşe göre bu, insanın şakayla çözebileceği türden bir sorun değildi. Bunu yapmak için Subercaseaux, Carnegie Mellon Üniversitesi'nde yüksek lisans yapmak üzere Şili'den ayrılmak zorunda kaldı.

Orada, Ağustos 2021'de tesadüfi bir karşılaşma yaşadı. Marijn Heule, zor matematik sorularını çözmek için muazzam bilgi işlem gücü kullanan bir bilgisayar bilimcisi. Subercaseaux, Heule'ye sorunu denemek isteyip istemediğini sordu ve bu Ocak ayında sonuçlanan bir işbirliğini başlattı. kanıt tek bir sayı ile özetlenebilir: 15.

Mümkün Olan Her Yol

2002 olarak, Wayne Goddard Clemson Üniversitesi'nden bazı matematikçiler ve benzer düşüncelere sahip bazı matematikçiler, belirli kısıtlamalar verildiğinde haritaların renklendirilmesiyle ilgili alanın temel dayanak sorularına yeni kıvrımlar bulmaya çalışarak kombinatorikte saçma sapan problemler oluşturuyorlardı.

Sonunda, sonsuza kadar devam eden bir grafik kağıdı gibi bir ızgarayla başlayan bir soruna ulaştılar. Amaç, sayılarla doldurmaktır. Tek bir kısıtlama vardır: Aynı sayının her bir tekrarı arasındaki mesafe, sayının kendisinden büyük olmalıdır. (Mesafe, dikey ve yatay ayrımın toplanmasıyla ölçülür; bu, ızgaralı şehir sokaklarında hareket etmeye benzediği için "taksi" mesafesi olarak bilinen bir metriktir.) Bir çift 1, taksi mesafesi 1 olan bitişik hücreleri işgal edemez, ancak 2'lik bir mesafeye sahip olan doğrudan köşegen hücrelere yerleştirilebilirler.

Başlangıçta, Goddard ve işbirlikçileri, sonsuz bir ızgarayı sonlu bir sayı kümesiyle doldurmanın bile mümkün olup olmadığını öğrenmek istediler. Ancak o ve dört işbirlikçisi bu "ambalaj boyama" problemini yayınladı dergisinde Ars Kombinasyonları 2008 yılında 22 sayı kullanılarak çözülebileceğini kanıtlamışlardı. Sadece beş sayı ile çözülemeyeceğini de biliyorlardı. Bu, sorunun asıl cevabının - gereken minimum sayı sayısı - ikisinin arasında bir yerde olduğu anlamına geliyordu.

Araştırmacılar aslında sonsuz bir ızgarayı doldurmadılar. Yapmak zorunda değillerdi. Bunun yerine, ızgaranın küçük bir alt kümesini (diyelim ki 10'a 10'luk bir kare) alıp, bunu sayılarla doldurmak, ardından doldurulmuş alt kümenin kopyalarının, bir alanı kaplar gibi yan yana yerleştirilebileceğini göstermek yeterlidir. bir kiremit kopyaları ile zemin.

Subercaseaux sorunu ilk öğrendiğinde kalem ve kağıt kullanarak fayans aramaya başladı. Sayı ızgaraları çizer, üstlerini çizer ve tekrar denerdi. Kısa süre sonra bu yaklaşımdan sıkıldı ve bir arkadaşından Mayın Tarlası oyununa benzeyen ve kombinasyonları daha hızlı test etmesine izin veren web tabanlı bir araç tasarlamasını istedi. Birkaç hafta daha çalıştıktan sonra, bir ızgarayı sekiz sayıyla toplamanın bir yolu olmadığına kendini ikna etmişti, ama bundan öteye gidemezdi - karoların alabileceği çok fazla potansiyel şekil vardı ve çok fazla sayılarla doldurulabilmelerinin farklı yolları.

Sorun, daha sonra açıklığa kavuşacağı üzere, ızgaranın belirli bir sayı dizisi tarafından kapsanamayacağını göstermek, kapsanabileceğini göstermekten çok daha zor olmasıdır. Goddard, "Sadece bir yolun işe yaramadığını göstermek değil, mümkün olan her yolun işe yaramadığını gösteriyor" dedi.

Subercaseaux, CMU'da başladıktan ve Heule'yi onunla çalışmaya ikna ettikten sonra, 15 numarayla ızgarayı kaplamanın bir yolunu çabucak buldular. Ayrıca, sorunu sadece 12 sayı ile çözme olasılığını da ortadan kaldırabildiler. Ancak, uzun süredir var olan sonuçları yalnızca yeniden ürettiklerini fark ettikleri için zafer duyguları kısa sürdü: 2017'ye kadar, araştırmacılar cevabın 13'ten az veya 15'ten büyük olmadığını biliyorlardı. .

Ünlü bir profesörü evcil hayvan sorunu üzerinde çalışmaya ikna eden birinci sınıf bir yüksek lisans öğrencisi için bu rahatsız edici bir keşifti. “Dehşete kapılmıştım. Bunu fark etmeden birkaç aydır bir problem üzerinde çalışıyordum ve daha da kötüsü, Marijn'i yapmıştım. zamanını onunla harcamak!” Subercaseaux yazdı çalışmalarını özetleyen bir blog yazısında.

Ancak Heule, geçmiş sonuçların keşfedilmesini canlandırıcı buldu. Diğer araştırmacıların sorunu üzerinde çalışacak kadar önemli bulduklarını gösterdi ve elde etmeye değer tek sonucun sorunu tamamen çözmek olduğunu onayladı.

"Sorun üzerinde 20 yıllık bir çalışma olduğunu anladığımızda, bu tabloyu tamamen değiştirdi" dedi.

Vulgardan Kaçınmak

Yıllar geçtikçe, Heule çok geniş olası kombinasyonlar arasında arama yapmanın etkili yollarını bularak bir kariyer edinmişti. Yaklaşımına SAT çözme denir - "tatmin edilebilirlik" in kısaltması. Boole formülü adı verilen ve iki olası sonucu olabilen uzun bir formül oluşturmayı içerir: 0 veya 1. Sonuç 1 ise, formül doğrudur ve sorun giderilmiştir.

Paketleme renklendirme problemi için, formüldeki her değişken, belirli bir hücrenin belirli bir sayı tarafından işgal edilip edilmediğini temsil edebilir. Bir bilgisayar, formülü yerine getirmek için değişken atama yollarını arar. Bilgisayar bunu yapabiliyorsa, ızgarayı belirlediğiniz koşullar altında paketlemenin mümkün olduğunu bilirsiniz.

Ne yazık ki, bir Boole formülü olarak paketleme renklendirme probleminin basit bir şekilde kodlanması milyonlarca terime kadar uzanabilir - bir bilgisayar veya hatta bir bilgisayar filosu, içindeki değişkenleri atamanın tüm farklı yollarını test ederek sonsuza kadar çalışabilir.

Goddard, "Bunu saf bir şekilde yaparsanız, bu kaba kuvveti yapmaya çalışmak evrenin sona ermesine kadar sürer" dedi. "Yani, bunu mümkün olan bir şeye indirgemek için harika basitleştirmelere ihtiyacınız var."

Üstelik salmastra renklendirme problemine her sayı eklediğinizde, olası kombinasyonların çoğalması nedeniyle yaklaşık 100 kat daha zor hale gelir. Bu, paralel çalışan bir bilgisayar bankasının tek bir günlük hesaplamada 12'yi eleyebilmesi durumunda, 100'ü elemek için 13 günlük hesaplama süresine ihtiyaç duyacakları anlamına gelir.

Heule ve Subercaseaux, kaba kuvvet hesaplama yaklaşımını büyütmeyi bir bakıma kaba buldu. Subercaseaux, "Birkaç umut verici fikrimiz vardı, bu yüzden 'Kümede 48 saatten daha kısa bir sürede bu sorunu çözene kadar yaklaşımımızı optimize etmeye çalışalım' zihniyetini benimsedik" dedi.

Bunu yapmak için, bilgi işlem kümesinin denemesi gereken kombinasyon sayısını sınırlamanın yollarını bulmaları gerekiyordu.

"[Onlar] sadece çözmek değil, aynı zamanda etkileyici bir şekilde çözmek istiyorlar," dedi Alexander Soifer Colorado Üniversitesi, Colorado Springs.

Heule ve Subercaseaux, birçok kombinasyonun aslında aynı olduğunu kabul etti. Baklava şeklindeki bir taşı sekiz farklı rakamla doldurmaya çalışıyorsanız, yerleştirdiğiniz ilk sayının ortadaki karenin bir yukarı ve bir sağına veya bir aşağı ve bir soluna olması fark etmez. merkez kare. İki yerleşim birbiriyle simetriktir ve bir sonraki hamlenizi tamamen aynı şekilde kısıtlar, bu nedenle ikisini de kontrol etmek için bir neden yoktur.

Heule ve Subercaseaux, bilgisayarın simetrik kombinasyonları eşdeğer olarak ele almasına izin vererek toplam arama süresini sekiz kat azaltan kurallar ekledi. Ayrıca, Heule'nin önceki çalışmalarında geliştirdiği küp ve fethetme adlı bir tekniği de kullandılar, bu da birbirlerine paralel olarak daha fazla kombinasyonu test etmelerine olanak sağladı. Belirli bir hücrenin 3, 5 veya 7 içermesi gerektiğini biliyorsanız, sorunu bölebilir ve üç olasılığın her birini aynı anda farklı bilgisayar setlerinde test edebilirsiniz.

Ocak 2022'ye kadar bu iyileştirmeler, Heule ve Subercaseaux'nun iki günden daha az hesaplama süresi gerektiren bir deneyde paketleme renklendirme sorununa yanıt olarak 13'ü ekarte etmesine olanak sağladı. Bu onlara iki olası cevap bıraktı: 14 veya 15.

Büyük Bir Artı

14'ü elemek ve sorunu çözmek için Heule ve Subercaseaux bilgisayar aramasını hızlandırmanın ek yollarını bulmalıydı.

Başlangıçta, ızgaradaki her bir hücreye değişkenler atayan bir Boole formülü yazmışlardı. Ancak Eylül 2022'de hücre hücre ilerlemelerine gerek olmadığını anladılar. Bunun yerine, beş hücreden oluşan küçük bölgeleri artı işareti şeklinde düşünmenin daha etkili olduğunu keşfettiler.

Boolean formüllerini yeniden yazdılar, böylece birkaç değişken aşağıdaki gibi soruları temsil etti: Bu artı şekilli bölgenin içinde bir yerde 7 var mı? Bilgisayarın 7'nin bölgede tam olarak nerede olabileceğini belirlemesi gerekmiyordu. Sadece orada olup olmadığını belirlemesi gerekiyordu - bu, yanıtlanması için önemli ölçüde daha az hesaplama kaynağı gerektiren bir soru.

Heule, "Belirli konumlar yerine yalnızca artılardan bahseden değişkenlere sahip olmak, onlar hakkında belirli hücrelerde konuşmaktan çok daha iyi oldu" dedi.

Heule ve Subercaseaux, artı aramanın verimliliğinin de yardımıyla, Kasım 14'de 2022'ü elemek için kullandıklarından daha kısa süren bir bilgisayar deneyinde 13'ü eledi. Sonraki dört ayı, bunu doğrulamak için harcadılar. bilgisayarın vardığı sonuç doğruydu - neredeyse en başta bilgisayarın bu sonuca varmasını sağlamak için harcadıkları zaman kadar.

Goddard, "Rastgele bir dergide bir tür yan soru olarak ortaya koyduğumuz sorunun, insan gruplarının bunu nasıl çözeceklerini bulmak için aylarca uğraşmalarına neden olduğunu düşünmek memnuniyet vericiydi." söz konusu.

Subercaseaux için bu, araştırma kariyerinin ilk gerçek zaferiydi. Ve matematikte çalışmayı ilk düşündüğünde idealleştirdiği türden bir keşif olmasa da, sonunda kendi entelektüel ödülleri olduğunu gördü.

"Bana bir karatahta verdiğin ve sana neden 15 olduğunu gösterebileceğim bir form anlamak değil" dedi. "Ancak problemin kısıtlamalarının nasıl işlediğini, burada 6'ya mı yoksa 7'ye mi sahip olmanın ne kadar iyi olduğu konusunda bir anlayış kazandık. Çok fazla sezgisel anlayış kazandık.”