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ę?
@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.
@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
Jak tam niebo nad Ukraina już czyste? F-16 wygrały wojnę? Nawet do linii frontu ich nie wyślą bo szybciej by spadały od Su-57 niż by zdążyli dostarczyć następne #ukraina #rosja
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ę?
jest 3 mod 4 - 3n-1 i dzielimy przez 4
więc na oko się da