Meni yöunetkin jo? Helpoin ratkaisematon pulma

https://dynamic.hs.fi/2020/collatz/?utm_campaign=hs_tf&utm_term=1&utm_source=tf-other&share=c33c9f50d3d114e912d8159decf643ad

Helpoin ratkai­sematon pulma
Koululainenkin ymmärtää tämän yksinkertaisen väittämän, mutta edes huippumatemaatikot eivät ole pystyneet todistamaan sitä. Osaatko sinä ratkaista Collatzin konjektuurin?

Antti Hämäläinen HS, teksti

Sillä on monia toinen toistaan mystisempiä nimiä: 3x 1-ongelma, Collatzin konjektuuri, Kakutanin probleema, Hassen algoritmi, Syracusa-ongelma.

Mutta ei huolta, uhkaavista nimistä huolimatta sinun tarvitsee osata vain jakaa kahdella ja kertoa kolmella. Ei kuulosta kovin vaikealta.

Tämä matemaatikoita turhauttava, "vaarallinen" ongelma rakentuu seuraavan yksinkertaisen leikin ympärille:

Keksi päästäsi mikä tahansa positiivinen kokonaisluku.

• Jos se on parillinen, jaa se kahdella.

• Jos se on pariton, kerro se kolmella ja lisää yksi.

Tällä tavalla saat uuden luvun. Toista edellinen vaihe tälle uudelle luvulle. Jatka tätä niin kauan kunnes päädyt lukuun 1.

Menikö yli hilseen? Kokeillaan käytännössä.


Voit edelleen jatkaa samoilla säännöillä soveltaen sitä lukuun 1. Se on pariton, joten saat luvun 4. Päädyt ikuiseen silmukkaan.

Saatiin siis jono numeroita 10, 5, 16, 8, 4, 2, 1. Tätä kutsutaan Collatzin lukujonoksi.

Jos otat mielivaltaisen luvun voi lukujonon pituus kasvaa karmivan suureksi ennenkuin kuin se päättyy. Esimerkiksi jos aloitat luvusta 27, joudut laskemaan uuden luvun 112 kertaa ennen lukujonon päättymistä. Kokeile itse valitsemalla mikä tahansa luku:

Laskuri näyttää lukusarjan joka syntyy yllämainitun prosessin mukaisesti. Vain sarjan viimeisimmät kahdeksan numeroa esitetään kerrallaan.

Parilliset luvut ovat sinisiä, parittomat vihreitä.

Laske
Vaikuttaa yksinkertaiselta ja suoraviivaiselta. Missä piilee siis se ongelma?

Ongelma on lukujonon viimeinen luku 1. Voitko olla varma siitä että mikä tahansa ensimmäisenä valitsemasi luku päätyy yllä kuvatun prosessin tuloksena lopulta lukuun 1? Tämä yksinkertainen kysymys ajaa matemaatikot järjiltään, kuin seireenin laulu. Arkijärki kun voisi sanoa että lopputulos riippuu siitä, mistä luvusta aloittaa.

Kyseessä on matemaatikoiden kielellä konjektuuri, eli väite jonka arvellaan pitävän paikkansa, mutta jota kukaan ei ole vielä todistanut aukottomasti.

isainen pähkinä kulkee monilla nimillä, mutta alkuperäisen idean kerrotaan saaneen vuonna 1937 saksalainen arvostettu matemaatikko Lothar Collatz (1910–1990). Monet tutkijat ja harrastelijat ovat sittemmin yrittäneet ratkaista houkuttelevan yksinkertaiselta vaikuttavaa ongelmaa, kenenkään siinä onnistumatta.

Sen sanotaan olevan vaarallinen, sillä tuotteliaskin matemaatikko voi siihen uppouduttuaan heittää hukkaan viikkokausia aikaa jonka voisi käyttää johonkin hyödyllisempään.

Muun muassa tutkija Paul Erdős (1913–1996) uhrasi ajatuksia ongelmalle.

Erdős on yksi maailmanhistorian tuotteliaimmista matemaatikoista joka julkaisi eläessään noin 1 500 artikkelia jopa 500 muun matemaatikon kanssa. Hän matkusti jatkuvasti, kertoman mukaan usein ilmaantuen yllättäen kollegoidensa ovelle ilmoittaen mielensä olevan avoin uusille haasteille.

Collatzin konjektuurista hänen kerrotaan sanoneen, ettei matematiikka ole valmis tämän kaltaisiin ongelmiin. Hän tarjosi 500 dollaria ratkaisun esittäjälle.

Viimeisimmän merkittävän panostuksen ongelmaan on antanut "matematiikan Nobel-voittaja", Fieldsin mitalisti Terence Tao vuonna 2019.

Kuten suurin osa matemaatikoista, hänkin keskittyy yleensä yleisluonteeltaan hedelmällisempään ja tuottavampaan perustutkimukseen.

Tao tarttui kuitenkin ongelmaan ja pystyi osoittamaan että lähes kaikki lähtöarvot päätyvät lopulta arvoon joka on lähellä lukua 1. Blogissaan julkaisemassaan esitelmässä hän kertoo tuloksensa olevan niin lähellä ongelman kokonaista ratkaisua kuin vain voi.

Mutta sekään ei riitä.

Ongelman ratkaisuun on historian saatossa valjastettu ihmisaivojen lisäksi myös tehokkaita tietokoneita. Konjektuuria on testattu käsittämättömän suurilla luvuilla tarkoituksena etsiä vastaesimerkki.

Vuoteen 2017 mennessä konjektuuria on testattu jokaisella luvulla joka on pienempi kuin 87×260, eli 100 304 170 900 795 686 912.

Yhtäkään vastaesimerkkiä ei ole löydetty.

Tietokoneen tuottama valtava todistusaineisto ei kuitenkaan riitä, ja tässä juuri piilee matemaattisen tarkkuuden armottomuus. Ns. näppituntuma ei riitä, vaikka sitä olisi kottikärryittäin.

Entäs jos otat vielä hieman suuremman luvun? Tai vielä yhden suuremman? Voitko olla varma että päädyt lukuun 1?

Todistuksen täytyy olla sellainen että yksinkertaisesti mitään ei jää epäilyksen varaan.

Mutta toisaalta yksikin vastaesimerkki voi osoittaa väitteen epätodeksi.

Lukuteoria on todellakin osoittanut että joskus ongelma voi olla luonteeltaan sellainen että vasta tarpeeksi suurilla luvuilla väite osoittautuu epätodeksi.