Meni yöunetkin jo? Helpoin ratkaisematon pulma

toni.smolander

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.

2

91

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000

    Ketjusta on poistettu 0 sääntöjenvastaista viestiä.

    Luetuimmat keskustelut

    1. Putin hoiti Suomen natoon ja myös Ruotsin

      Iso kiitos Vladimir Putinille. Hänen ansiosta pääsemme nyt Natoon. Putin halusi Naton lähelle ja nyt sai. Voimme tästä kiittää vain Putinia.
      Maailman menoa
      666
      8084
    2. Niinistö teki hetkessä Suomesta Venäjän ydinaseiden maalitaulun

      Kaiken lisäksi mies vielä lällätteli Putinille eilisessä tiedotustilaisuudessa ja käski katsomaan itseään peiliin. Kyllä vähän asiallisempaa käytöstä
      Maailman menoa
      467
      2336
    3. Voi Stefu ja sun kiivas luonteesi

      Sielä lentelee ullakkohuoneiston ikkunasta daamin vaatteet ja matkalaukut pitkin pihaa. Toisaalta,en ihmettele yhtään että tämä suhde päättyi näin,kyl
      Kotimaiset julkkisjuorut
      233
      2286
    4. Poliisi otti Stefun kiinni!

      Seiska tietää kertoa.
      Kotimaiset julkkisjuorut
      147
      1868
    5. Ohhoh! Martina Aitolehti ja seurapiirihurmuri-Jesper ekassa yhteiskuvassa - Sutinaa Mallorcalla!

      Martina Aitolehti ja seurapiirijulkkis-Jesper nauttivat toisistaan varsin vauhdikkaissa merkeissä Mallorcalla. Aitolehti ei ole esitellyt rakastaan vi
      Kotimaiset julkkisjuorut
      28
      1393
    6. Veikkaus: Miten The Rasmus pärjää Euroviisuissa?

      Euroviisuhuuma on ylimmillään, kun Suomi ja The Rasmus taistelee biisillään Jezebel. Bändi on tikissä, kunhan Lauri Ylösen ääni kantaa. Mitä veikka
      Viihde ja kulttuuri
      51
      1252
    7. Stefanilta tuli taas karu totuus Sofiasta

      Marokkolainen h*o*ra! Voi tsiisus kun mulla on hauskaa! Lumput lentää ikkunasta kun Stefu raivoaa h*uralleen🤣🤣🤣 Nyt ne popparit tulille, tästä tule
      Kotimaiset julkkisjuorut
      114
      1244
    8. Steppuli veressä

      Seiskan lööpissä Steppulilla naama ja nyrkit veressä. Ei tainnut ihan kamojen pihalle paiskominen riittää. Onkohan pistänyt kämpän tuusannuuskaks.
      Kotimaiset julkkisjuorut
      70
      938
    9. Ootko onnellinen kun ei tarvitse

      nähdä tätä tyhmää naamaa enää koskaan? Multa se särkee sydämen, mutta minkäs teen. Vaikka olisi kuinka sinnikäs eikä hellittäisi, se ei aina auta.
      Ikävä
      65
      862
    10. Oletko nähnyt eroottiset kohuleffat? Fifty Shades Of Grey -trilogia tv:stä

      Fifty Shades -trilogia starttaa, kun nuori opiskelijanainen Anastasia tapaa rikkaan liikemiehen. Seksisuhdehan siitä starttaa, höystettynä sadistisill
      Suhteet
      7
      802
    Aihe