Sa presupunem ca am un numar "x".
Daca este par, il impart la 2, obtinand "x/2"
Daca este impar, il triplez si adun 1, obtinand "3x+1".
Repetand procedeul de mai multe ori (in sensul ca noul numar obtinut cu metoda de mai sus devine "x", caruia va trebui sa ii reaplicam aceeasi metoda) se observa ca majoritatea numerelor ajung in cele din urma la 1. Se poate demonstra sau infirma ca asta e valabil pentru orice "x"?
P.S1: Daca stiti deja raspunsul nu dati spoilere.
P.S.2: Mi-ar placea ca intrebarea sa fie eliminata de un admin pe motiva ca e tema scolara.
Un exemplu:
X=10.
10 e numar par, deci obtinem 10/2=5
5 este numar impar, deci obtinem 3*5+1=16.
16,numar par, obtinem 16/2=4
4, tot par, deci 4/2=2.
2 e par, deci 2/2=1.
Am obtinut 1.
Ordonare:
După relevanţă
Răspunde
Să luăm cazul unui număr impar, să zicem 7. Îl triplez şi adun 1, deci obţin 22. Acum zici să repet procedeul. Adică ce să fac? Să îl triplez pe acest 22 şi să adaug 1? Obţin 67. Sau cum?
Răspunde
Să plec tot de la 22-ul meu. Prin operaţiile respective obţin: 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1. Trebuie să încerc acum cu un număr mai mare, cum ar fi 226.
Oricum, interesantă ideea. Frumoasă problemă! Tu, Inferno, aveai o altă metodă decât cea propusă de t&t?
16/2=8, nu 4.
E clar că pentru orice k(k diferit de 1), dacă a[k] e par și a[k]/2=a[k-1], unde a[k-1] par atunci a[2]=2. De exemplu în exemplul tău ai 16/2=8, 8/2=4, 4/2=2, 2/2=1. În caz că obții un număr impar trebuie să îl fac par și să repeți operația, însă să îl faci par nu în orice sens. De exemplu pot să fac par un număr q impar aplicând 4q în loc de 3q+1. Atunci în exemplul tău am avea 10/2=5, 4*5=20, 20/2=10, 10/2=5, 4*5=20 și ne-am învârti în buclă sau într-un caz mai nasol ne-am duce spre infinit. Pentru a evita asta trebuie să ne asigurăm că q*2 e mai mare ca 4*q/2 ceea ce nu e adevărat și de asta numerele nu vor descrește. Avem nevoie de descreștere pentru a ajunge la 1.
Aceeași condiție o putem pune în cazul tău. (3*x+1)/2 mai mic ca 2x deci 3x+1 mai mic ca 4x deci x mai mare ca 1 de unde deduc că merge pentru orice număr natural mai mare ca 1. Normal ăsta e cazul pentru care avem un număr impar și după un număr par. Nici nu poți obține număr impar după număr impar căci 3x+1 îl face par dar poți obține clar par după par că ăsta ne e scopul, să generăm un șir de numere pare descrescătoare, ultimul fiind 2.
Am făcut și un program care să verifice primele 100000 de numere mai mari ca 1. Concluzia, dacă programul a funcționat cum trebuie, că regula asta merge pentru primele 100000 de numere.
https://imgur.com/a/g0MYM
https://imgur.com/a/k2UYC
Fiecare număr testat e despărțit prin virgulă. Acel 1 reprezintă faptul că s-a ajuns în final la 1 iar numărul după el reprezintă numărul de operații efectuate ca să ajungă la 1. Numerele sunt în ordine consecutivă. Error=0 de la sfârșit reprezintă faptul că niciun număr nu s-a abătut de la regulă.
Pare sa fie valabila regula.
Deci care spui tu ca e motivul pentru care orice "x" am calcula cu algoritmul de mai sus acesta ar ajunge la 1?
Am spus mai sus care e motivul. Făcând împărțirea repetată a unui număr x la 2, fără rest obții 1. Ex. 9/2=4, 2/2=1. E îndeajuns să știi asta ca să deduci că regula e adevărată și să faci comparația pe care am făcut-o mai sus. Cum deduci prima chestie? Orice număr împărțit la 2 este mai mic ca numărul anterior și e normal că descrești strict. E clar că în cele din urmă ajungi la 2 dacă tot descrești iar împărțind pe 2 la 2 e 1. E o chestie general valabilă și când treci în baza 2 un număr din baza 10, ultimul cât va fi întotdeauna 1 dacă numărul e mai mare ca 0 iar acea trecere se face prin împărțire repetată la 2.
Ce am vrut să zic. Echivalentul regulei este că dacă e un număr par ai x/2 iar dacă un număr e impar ai (3x+1)/2
Dacă ai 22 vei obține.
a1=11
a2=17
a3=26
a4=13
a5=20
a6=10
a7=5
a8=8
a9=4
a10=2
Se poate demonstra ușor faptul că 2*ak mai mare ca ak+1 asta în caz că ak+1 e par implică faptul că ak mai mare ca ak+1/2 deci ak mai mare decât ak+2
De exemplu dacă te uiți la
a2=17
a3=26
a4=13
a2 mai mare ca a4. De aia am zis că e descrescător și se duce la 2(deși în realitate nu e descrescător însă termenii să le zic așa remarcabili sunt descrescători, adică nu sunt în buclă sau să se ducă la infinit).
În cazul general 2ak mai mare ca ak+1 unde ak+1 poate fi impar.
Atunci 2ak+1 mai mare ca ak+2
Obținem 2 relații.
2ak mai mare ak+1
ak+1 mai mare ak+2/2
Deci 2ak mai mare ca ak+2/2
Deci ak (în caz că ak+2 e par) mai mare ca ak+3/2
Și ajungem iar la o discuție iar dacă și ak+3 e par atunci e clar că
ak mai mare ca ak+4. Și ajungem la aceeași concluzie.
Nu e o demonstrație completă că trebuie generalizat complet și să mai demonstrăm niște chestii pe deasupra dar ideea asta cu puțină intuiție mă face să cred că e o chestie general valabilă(de aia am ales să și testez acel program care mi-a confirmat parțial presupunerea). Nu pare prea simplu să se obțină o regulă generală și o formă generală.
La asta m-am gândit când am făcut comparația.
"E îndeajuns să știi asta ca să deduci că regula e adevărată"
Cum asa? Este adevarat ca daca impart un numar la 2 (ignorand restul) ad infinitum in cele din urma obtin 1. Descresterea e clara, perfect logic.
Insa nu asta e ceea ce fac eu aici. Eu impart numarul la 2 numai daca el e par, in cazul in care e impar il triplez si adun 1, crescand valoarea. Iar de data asta nu imi pare deloc evident ca ar fi o descrestere clara pentru orice numar.
"Se poate demonstra ușor faptul că 2*ak mai mare ca ak+1"
Presupun ca prin ak+1 intelegi "a" cu indicele "k+1".
Pai sa vedem daca se poate demonstra ce spui tu.
In primul rand indicele il notaml cu "[]" ca sa se inteleaga.
Afirmatia ta e:
2*a[k]>a[k+1]
Unde a[k] este un numar oarecare, iar a[k+1] este numarul obtinut din a[k] prin aplicarea algoritmului nostru.
- Daca a[k] este numar par, atunci a[k+1]=a[k]/2,conform algoritmului.
Verificand: 2*a[k]>a[k]/2
4*a[k]>a[k]
4*a[k]-a[k]>0
3*a[k]>0
a[k]>0
Deci daca a[k] e par atunci 2*a[k]>a[k+1] pentru a[k]>0.
-Daca a[k] este numar impar, atunci a[k+1]=(3*a[k]+1)/2,conform algoritmului.
Verificand: 2*a[k]>(3*a[k]+1)/2
4*a[k]>3*a[k]+1
a[k]>1
Intr-adevar, daca a[k] e impar, atunci 2*a[k]>a[k+1] pentru a[k]>1.
https://en.wikipedia.org/wiki/Collatz_conjecture
Din ce am citit nimeni nu a găsit demonstrația conjuncturii.
Așa cum am zis, asta nu e o demonstrație și nici nu cred că te așteptai ca cineva de pe aici să o demonstreze însă m-am ghidat după o chestie care evidentă sau nu(faza cu descreșterea) din ce se observă cam asta se întâmplă. Nu există nicio buclă sau o creștere evidentă iar dacă exista(am dat un exemplu mai sus de buclă) condiția mea nu mai era validă.
Ce am vrut să spun eu e faptul că vei obține în acest șir de numere generate unul din altul, un subșir de numere pare descrescătoare. Adică având în vedere că fiecărui număr par i se va aplica împărțirea la 2, vom obține dintr-un număr actual par x un alt număr par y(evident unde y mai mic ca x) ori un număr impar care va genera la rândul său la un moment dat(depinde de situație când) un număr par z mai mic ca x de asemenea și tot așa, așa ajungându-se la 2. De fapt cam asta se întâmplă în cele 100.000 de situații confirmate de algoritmul meu. Nu am adus o demonstrație serioasă că cine știe cu câte mii de euro mă alegeam însă o consider bună ca reper chestia asta.
Acum ca vad cum evalueaza lucrurile pe aici deja sunt foarte multumit ca am reusit sa ma abtin sa nu incalc ce scria la P.S1.
Chiar sunt curios pana unde o sa se ajunga cu 'rationamentele'.
Eh,am oprit eu "nebunia".
Cand am scris P.S.1. la tine m-am gandit.
Răspunsul este publicat...
Te rugăm să aştepţi ca răspunsul tău să fie trimis spre publicare.
