Matematyka dyskretna, zadanie nr 4834
ostatnie wiadomości | regulamin | latex
Autor | Zadanie / 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