[jeronimo_martini]

#matematyka

Heja,

chciałbym zapytać was o pomoc w jednym zadanku. Próbuję je zrobić od jakiegoś czasu i do niczego jak na razie nie doszedłem. Nie musi to być kompletne rozwiązanie, może być jakaś wskazóweczka (⌒(oo)⌒).

Zadanie

Na tablicy napisano liczbę całkowitą dodatnią. W każdym kroku zmazujemy liczbę n napisaną na tablicy i piszemy nową liczbę . Jeśli liczba n jest parzysta, to piszemy na tablicy liczbę n/2. Jeśli liczba n jest nieparzysta, to wybieramy jedną z liczb 3n + 1, 3n − 1 i piszemy ją na tablicy. Czy — niezależnie od tego, jaką liczbę napisano na tablicy na początku — możemy, po skończenie wielu krokach, uzyskać na tablicy jedynkę?

[q.....d]

@jeronimo_martini: jest hipoteza collatza, że zawsze skończymy na 1

[q.....d]

@jeronimo_martini: ten problem był bez wyboru 3n+1 czy 3n-1, ale można to tak uogólnić

[q.....d]

@jeronimo_martini: i aktualnie nie ma rozwiązania tego problemu

[jeronimo_martini]

@qweasdqweasd: Ale to raczej nie jest problem Collatza, bo tam mamy dla liczb nieparzystych 3n + 1, a tu mamy jeszcze możliwość wybrania 3n - 1. Plus, problem Collatza jest nierozstrzygnięty.

[E.....a]

@jeronimo_martini: jest 1 mod 4 - 3n+1 i dzielimy przez 4
jest 3 mod 4 - 3n-1 i dzielimy przez 4
więc na oko się da

[A.....t]

@jeronimo_martini: Tak. Bez straty ogólności możesz rozpatrywać początek tylko dla liczb nieparzystych. W mojej ocenie wystarczy tylko pokazać że na każdą ekspansję (pomnożenie przez 3 +/-1) wykonasz co najmniej dwie redukcje podział przez 4. Czyli że da się wykonać przejście z jednej nieparzystej do nieparzystej co najmniej o 3/4 mniejszą. A że zbiór jest ograniczony od dołu to w pewnym momencie się zatrzymasz. Wystarczy w mojej ocenie rozpisać 2-3 kroki