logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Matematyka dyskretna, zadanie nr 4834

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

tasia
postów: 17
2016-10-06 00:34:40

witam mam zadania i treśc rozwiązania:
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ę $\frac{n}{2}$, jeśli liczba n jest nieparzysta, to wybieramy z liczb 3n+1, 3n-1 i piszemy ją na tablicy.
Czy niezaleznie od tego jaką liczbę napisano na tablicy na początku mozemy, po skończonej wielu krokach uzyskać na tablicy jedynkę?

Rozwiązanie :
oczywiscie $\frac{n}{2}$ < $ n $ dla każdej liczby parzystej $ n $.
Jeśli n jest liczba nieparzystą to $ n=4k+1$ lub $ n=4k+3$ dla pewnej liczby całkowitej $k\ge0$.
w pierwszym wypadku po zmazaniu n na tablicy piszemy $3n+1=12k+4 $, więc w następnym krokach pojawiają sie liczby $\frac{3n+1}{2}=6k+2 $ i $ \frac{3n+1}{4}=3k+1 < 4k+1=n $ dla k>0, czyli n>1.
W drugim wypadku na tablicy piszemy liczbę 3n-1=12k+8, co zmusza nas do zastąpienia jej kolejno przez 6k+4 i przez 3k+2<4k+3=n dla każdej liczby $ k\ge0$.
wykazaliśmy, ze jeśli na tablicy pojawiła się na początku liczba n>1, to najdalej po trzech krokach możemy napisać liczbę od niej mniejszą (niezależnie od parzystości n ). Oznacza to, że po skończonej liczbie kroków możemy uzyskać liczbę 1.


włsnie w tym rozwiązaniu nie rozumiem dlaczego $ n=4k+1 $ lub $n =4k+3$. I muszą być akurat takie podstawienie ? jak tak to dlaczego ? i czy mozna zastąpić je czymś innym ?


tumor
postów: 8070
2016-10-06 01:04:39

Zadanie nieprecyzyjnie opisuje "wybieranie". Powinno być zaznaczone, że mamy możliwość według woli wybrać jedną z możliwości w takim właśnie celu, by w skończonej ilości kroków uzyskać 1. Wówczas ma sens pytanie, czy się to uda.

Gdyby zadanie wymuszało na nas zawsze wybór 3n+1 dla n nieparzystego, to dostalibyśmy problem Collatza, znany i do dziś nie rozwiązany, wtedy raczej nie mógłbym Ci pomóc.

Możliwość wyboru między opcjami 3n+1 i 3n-1 jest ułatwieniem, które pozwala bardzo szybko uzasadnić, że zawsze dojdziemy do jedynki. Po pomnożeniu nieparzystego n przez 3 i dodaniu lub odjęciu jedynki zawsze uzyskamy liczbę parzystą, prawda?
Pomyślmy, jak by zadanie wyglądało, gdybyśmy zawsze dodawali 1.
Wtedy dla liczby na przykład n=9 po pomnożeniu przez 3 i dodaniu 1 otrzymamy 28, co się podzieli przez 2 i jeszcze raz przez 2, otrzymamy 7, czyli mniej niż 9.
Jeśli jednak zaczniemy na przykład od n=11, to 3n+1=34, co się podzieli przez 2 tylko jeden raz, dostaniemy 17, a teraz znów mamy liczbę zwiększać.. Dla problemu 3n+1 nie udało się dotychczas wykazać, że dla każdego n w pewnej liczbie kroków musimy uzyskać liczbę mniejszą niż n.

Po przetestowaniu paru możliwości zauważysz, że nieparzyste n ze zbioru:
5,9,13,17,... po pomnożeniu przez 3 i dodaniu 1 dzielą się przez 4 (co sprawi, że wynik będzie mniejszy od wyjściowej liczby).
Liczby te są postaci 4k+1 (innymi słowy: przy dzieleniu przez 4 dają resztę 1).
Pozostałe liczby nieparzyste:
3,7,11,15 po pomnożeniu przez 3 i dodaniu 1 będą podzielne przez 2, ale nie przez 4. Stąd właśnie w zadaniu zmiana warunków i zezwolenie na odejmowanie 1. Jeśli te liczby (które są postaci 4k+3, czyli dają resztę 3 przy dzieleniu przez 4) pomnożymy przez 3 i odejmiemy od nich 1, to uzyskamy wynik podzielny przez 4.

---

Moja odpowiedź na Twoje pytanie jest zatem taka:
autor zadania znając oryginalny problem Collatza (tylko 3n+1) zdawał sobie sprawę, że z ogromnym prawdopodobieństwem przerasta on zdolności studentów. Wobec tego dobrał drugą możliwość (3n-1) właśnie tak, żeby załatwiała ona łatwo liczby, których nie załatwiało działanie 3n+1.
"Załatwianie" oznacza tu taki proces, który daje w wyniku liczbę podzielną przez 4, czyli taką, którą można dwukrotnie podzielić przez 2, otrzymując w efekcie niższą niż wyjściowa.

Skoro po każdym kroku zmniejszamy liczbę, ale pozostajemy zawsze przy liczbach dodatnich, to musimy przejść przez 1.

Dość często przedstawia się liczby w takiej konwencji. Chyba ze szkoły średniej pamiętasz, że liczby parzyste można zapisać jako 2k, a nieparzyste jako 2k+1.
Podobnie wszystkie liczby naturalne można zapisać jako
4k
4k+1
4k+2
4k+3
czyli dające reszty z dzielenia przez 4 równe 0,1,2 lub 3. Innej reszty z dzielenia przez 4 nie ma, prawda?
Liczby postaci 4k i 4k+2 są parzyste, czyli zmniejszamy je od razu dzieląc przez 2.
Liczby postaci n=4k+1 oraz n=4k+3 są nieparzyste, ale dla pierwszych 3n+1 jest podzielne przez 4, a dla drugich 3n-1 jest podzielne przez 4. To uzasadnia traktowanie ich oddzielnie.



strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj