Wpis z mikrobloga

#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ę?
  • 6
@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 w