Ongelmaketju - ratkaise & esitä

[Ekku]

Tällainen löytyi toisaalta, näppärä päättelytehtävä :

1. Samalla kadulla on viisi taloa, joista jokainen on eri värinen. Jokaisen talon omistaja on eri kansallisuutta.
2. Talojen omistajista, jokainen juo eri juomaa, polttaa eri merkkistä savuketta ja omistaa eri lemmikkieläimen.
3. Kenelläkään ei siis ole samaa lemmikkiä, kukaan ei juo samaa juomaa, polta samaa savukemerkkiä eikä ole samaa kansallisuutta kuin toinen.

Kysymys kuuluu: "Kuka omistaa kalan?"

Faktat:

* Britti asuu punaisessa talossa.
* Ruotsalaisella on koiria lemmikkeinä.
* Tanskalainen juo teetä.
* Vihreä talo on valkoisen talon vasemmalla puolella.
* Vihreän talon omistaja juo kahvia.
* Henkilö, joka polttaa Pall Mallia, kasvattaa lintuja.
* Keltaisen talon omistaja polttaa Dunhillia.
* Henkilö, joka asuu keskimmäisessä talossa, juo maitoa.
* Norjalainen asuu ensimmäisessä talossa.
* Henkilö, joka polttaa Blendiä, asuu kissan omistajan naapurissa.
* Henkilö, jolla on hevonen asuu sen naapurissa joka polttaa Dunhillia.
* Henkilö, joka polttaa Bluemastersia, juo olutta.
* Saksalainen polttaa Princeä.
* Norjalainen asuu sinisen talon naapurissa.
* Henkilöllä, joka polttaa Blendiä, on naapuri joka juo vettä.

Eipä tuo vaikea ollut, meni muuten päättelyllä, mutta yhdessä kohdassa piti kokeilla kahden vaihtoehdon välillä.

[JMe1]

Ohessa linkki tunnettuun ongelmaan:
https://en.wikipedia.org/wiki/Three_utilities_problem

Mielestäni, löytyy yksinkertainen päättelyketju joka näyttää että ratkaisua ei ole silloin kun yksiköt ovat kaikki samassa tasossa.

[Eusa]

Ohessa linkki tunnettuun ongelmaan:
https://en.wikipedia.org/wiki/Three_utilities_problem

Mielestäni, löytyy yksinkertainen päättelyketju joka näyttää että ratkaisua ei ole silloin kun yksiköt ovat kaikki samassa tasossa.

Tuossa on näkyvissä fundamentaali syy miksi todellisuus rakentuu vuorovaikutuslinjoiksi 3-ulotteisen avaruuden varaan.

[Ekku]

Sakemannilla on kaloja.

[JMe1]

Joskus muinoin edellisellä pastalla oli keskustelua ongelmasta johon ei ole matemaattista todistusta:

https://en.wikipedia.org/wiki/Collatz_conjecture

Sillon esitin että mikä tahansa alkuarvo päätyy väistämättä samaan alkupisteeseen kuin mikä tahansa muu luku eli ykköseen.

Ongelmaa on historian saatossa lähestytty kaikilta mahdollisilta suunnilta löytämättä ratkaisua, rajasin sen binäärilukujen käsittelyyn, eli bittijonoksi.

Haluan avata ajatteluani hieman lisää:

Funktio 3x+1 kuuluu kategoriaan https://en.wikipedia.org/wiki/Linear_co ... _generator, tuolla on määritelty:

"
The generator is defined by the recurrence relation:
X n + 1 = ( a X n + c ) mod m
where X X is the sequence of pseudo-random values
"
Tämä tarkoittaa että jos mille tahansa luvulle toistetaan operaatiota (3x+1), luku alkaa bittivirtana lähestyä satunnaista, nollat ja ykköset ovat tasaisesti jakautuneet.

Esimerkki satunnaiselta näyttävästä bittijonosta:
10100101101001011110100110

Ja sen vastakohta on tietysti:
11111111111111111111111111 tai
00000000000000000000000000

Collatz conjecturen funktiot voidaan lyhentää tällaisiksi (https://en.wikipedia.org/wiki/Collatz_conjecture):

n/2, jos päättyy nollaan
(3n+1)/2, jos päättyy ykköseen

No miksi bittijono alkaa väistämättä lyhentyä ?

Koska alin bitti on satunnaisuudesta johtuen 50% todennäköisyydellä 1 tai 0. Ja jos ei ole, 3x+1 jatkaa työstämistään ja ajaa sitä aina vaan kohti tuota tasajakoa.

Jos viimeinen numero on 0, se poistetaan joten bittijono lyhenee yhdellä, AINA.
MUTTA, jos viimeinen numero on ykkönen, luku ei kasvakaan pituudeltaan kaikissa tapauksissa.
Esimerkki jossa pituus säilyy : 1001+10011=11100/2=1110 9+19=28/2=14

Tämä ero, (lyhenee aina yhdellä, pitenee useimmiten yhdellä) YHDESSÄ oikeanpuoleisen bitin 50%/50% jakauman kanssa pakottaa bittijonon lyhentymään.

Ohjelmallinen kokeilu osoitti että joissakin tapauksissa 3n+1 funktiolta meni aika kauan ennekuin satunnaisuus asettui. Pelkkien ykkösten bittijono oli tällainen "hankala tapaus".

No niin, nyt sitten vaan matemaatikot töihin, kääntäkää tämä idea todistukseksi.
Edellyttää tietysti että ajattelussani ei ole virhettä. Saa korjata jos sellaisia löytyy.

[Eusa]

JMe1: "Koska alin bitti on satunnaisuudesta johtuen 50% todennäköisyydellä 1 tai 0. Ja jos ei ole, 3x+1 jatkaa työstämistään ja ajaa sitä aina vaan kohti tuota tasajakoa."

"Ja jos ei ole" 1 tai 0? Mikä muu se voisi olla? Tuossa kohti tarvis vähän tarkentaa mitä tarkoitat...

[JMe1]

JMe1: "Koska alin bitti on satunnaisuudesta johtuen 50% todennäköisyydellä 1 tai 0. Ja jos ei ole, 3x+1 jatkaa työstämistään ja ajaa sitä aina vaan kohti tuota tasajakoa."

"Ja jos ei ole" 1 tai 0? Mikä muu se voisi olla? Tuossa kohti tarvis vähän tarkentaa mitä tarkoitat...

Tarkoitin alimman bitin todennäköisyysjakaumaa, vääristyneessä voi olla vaikka pelkkiä ykkösiä joten juku vaan jatkaa pitenemistään. Kun satunnaisuus on asettunut ja tehdään vaikkapa 1000 operaatiota, huomataan että alin bitti oli 1 vaikkapa 485 tapauksessa, 0 niissä lopuissa.

Mainitsemassani hankalassa tapauksessa 11111111111111 alimman bitin todennäköisyydet ovat 1: 100%, 0 : 0%, tämä korjaantuu vasta hyvin monen 3x+1 operaation jälkeen.

[Eusa]

Collatz on aika naiivi ongelma.

Otetaan peräkkäiset alkuluvut 7, 5 ja 3. Nyt 7x+n3 (n<5) jaetaan 5:llä, kunnes menee ykköseen tai ei ole jaollinen. Esim. 71...80...16...25...5...1.

Sitten seuraavat pienemmät 5, 3 ja 2 -> 5x+n2 (n<3) [/3]: 59...63...21...7...9...3...1.

Seuraava sarja 3, 2 ja 1 -> 3x+n1 (n<2) [/2] tuottaa Collatzin.

Riittää "todistaa", että mitkä tahansa kolme peräkkäistä alkulukua tuolla logiikalla johtaa lopulta ykköseen. lol. mot.

[Eusa]

Collatz on aika naiivi ongelma.

Otetaan peräkkäiset alkuluvut 7, 5 ja 3. Nyt 7x+n3 (n<5) jaetaan 5:llä, kunnes menee ykköseen tai ei ole jaollinen. Esim. 71...80...16...25...5...1.

Sitten seuraavat pienemmät 5, 3 ja 2 -> 5x+n2 (n<3) [/3]: 59...63...21...7...9...3...1.

Seuraava sarja 3, 2 ja 1 -> 3x+n1 (n<2) [/2] tuottaa Collatzin.

Riittää "todistaa", että mitkä tahansa kolme peräkkäistä alkulukua tuolla logiikalla johtaa lopulta ykköseen. lol. mot.

Heh. Jäi sampleissa toki kertomatta isoksi - mutta todistuvuusidea selkis.

Saattaisipa liittyä kaksosalkulukujen esiintyvyyteen nämä.

[JMe1]

Collatz on aika naiivi ongelma.

Otetaan peräkkäiset alkuluvut 7, 5 ja 3. Nyt 7x+n3 (n<5) jaetaan 5:llä, kunnes menee ykköseen tai ei ole jaollinen. Esim. 71...80...16...25...5...1.

Sitten seuraavat pienemmät 5, 3 ja 2 -> 5x+n2 (n<3) [/3]: 59...63...21...7...9...3...1.

Seuraava sarja 3, 2 ja 1 -> 3x+n1 (n<2) [/2] tuottaa Collatzin.

Riittää "todistaa", että mitkä tahansa kolme peräkkäistä alkulukua tuolla logiikalla johtaa lopulta ykköseen. lol. mot.

Ei kyllä auennut minulle tuo ylläoleva logiikka. Mutta tuosta naiiviudesta saa käsityksen jos menee tänne:

https://arxiv.org/

.. ja kirjoittaa hakusanaksi collatz

Huomaa että matemaatikot ovat tehneet (kymmeniä)tuhansia tunteja työtä löytämättä ratkaisua.
Näyttää siltä että ongelman esittäjä oli oikeassa sanoessaan "matematiikka ei taivu tällaiseen ongelmaan".


Eli, kyllä tuonne kannattaa ratkaisu/todistus lähettää jos sen helposti löytää.

[Eusa]

Näemmä tulee olla 5, 3 ja 2 -> 5x+1+n2 (0<=n<3) [/3], niin voi osua oikein ja kiertää kaikkia lukuja. Taitaa isommilla olla sitten tarve summailla vastaavasti alkuun aiempia pienempiä ensin jne. Mutta logiikka, jolla nähdään Collatziin voidaan säilyttää...

[Eusa]

Näemmä tulee olla 5, 3 ja 2 -> 5x+1+n2 (0<=n<3) [/3], niin voi osua oikein ja kiertää kaikkia lukuja. Taitaa isommilla olla sitten tarve summailla vastaavasti alkuun aiempia pienempiä ensin jne. Mutta logiikka, jolla nähdään Collatziin voidaan säilyttää...

Vaatiikin 5, 3 ja 2 -> 5x-1+n2 (0<=n<3) [/3], muuten menee luuppiin.

[Eusa]

Kylläpä nuo yleistykset menevät luuppiin varsin herkästi. On siinä Collatzissa ainutkertaisuutta, jota haastava yleistää.

[JMe1]

Kylläpä nuo yleistykset menevät luuppiin varsin herkästi. On siinä Collatzissa ainutkertaisuutta, jota haastava yleistää.

No mitä sanot eittämästäni satunnaisuuteen perustuvasta ratkaisusta ? Onko logiikka pitävä ? Onko se käännettävissä matemaattiseksi todistukseksi ?

[Eusa]

Kylläpä nuo yleistykset menevät luuppiin varsin herkästi. On siinä Collatzissa ainutkertaisuutta, jota haastava yleistää.

No mitä sanot eittämästäni satunnaisuuteen perustuvasta ratkaisusta ? Onko logiikka pitävä ? Onko se käännettävissä matemaattiseksi todistukseksi ?

Satunnaisuus ei käänny matemaattisesti loogisesti pitäväksi todistukseksi koko lukujoukolle. Mutta, jos voi todistaa, että kyse on (kaoottisesta) kattavasta väistelystä, todistus voi toimia.