Matematyka dyskretna, zadanie nr 4834
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
tasia post贸w: 17 |  2016-10-06 00:34:40witam 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