Задача 16

Pinetop Smith · Пуснато на: Tue Nov 25, 2008 5:46 pm Заглавие: Задача 16

В безкрайната редица [tex]a_{1},a_{2},...., a_{n}[/tex] числото [tex]a_{1}=1[/tex], а всяко следващо число [tex]a_{n}[/tex] се получава от предишното [tex]a_{n-1}[/tex] по следното правило: ако най-големият нечетен делител на [tex]n[/tex] дава остътък 1 при деление на 4 , то [tex]a_{n}=a_{n-1}+1[/tex], ако този остатък е равен на 3, то [tex]a_{n}=a_{n-1}-1[/tex]. Докажете, че в редицата:
а) числото 1 се среща безброй мого пъти.

Реклама

administrator · Пуснато на: Tue Nov 25, 2008 9:59 pm Заглавие:

б) всяко естествено число се среща безброй много пъти.
stanislav atanasov, Турнир на градовете 2008

Baronov

Пафнутий

Baronov · Пуснато на: Wed Nov 26, 2008 7:19 pm Заглавие:

Естествено, че имам доказателство. Като разгледаме числата в двоична бройна система и се вижда, че ако цифрата в ляво на най дясната единица на n е 0, то [tex]a_{n}=a_{n-1} + 1[/tex], в противен случай [tex]a_{n}=a_{n-1}-1[/tex]. Това ни позволява да направим изображение между числата n които дават +1 и числата които дават -1. Просто променяме цифрата вляво от най-дясната единица в двоичното представяне. За по удобно може да считаме, че [tex]a_{0}=0[/tex]. Ако разгледаме числата от 1 до [tex]2^{n}-1[/tex] виждаме, че това съответствие е "почти" еднозначно-обратимо. Единствената единица, на която не съответства -1 е [tex]2^{n-1}[/tex]. От тук следва, че [tex]a_{2^{n}-1}=1[/tex].

Baronov · Пуснато на: Wed Nov 26, 2008 7:41 pm Заглавие:

За другото условие е достатъчно да покажем, че в редицата има произволно големи числа ( и после понеже има безбройно много единици и по непрекъснатост...).
За да докажем това нека [tex]n=101010101010101010........101010_{2}[/tex]. Тогава като вземем предвид съответстивето от горния ми пост виждаме, че [tex]a_{n}[/tex] е голямо. Наистина да вземем числото образъвано от първите няколко (четен брой) цифри на n и допълнено с нули докато стане с толкова цифри, колкото е n. Очевидно съответното му число от горепосоченото съответствие е > n. Тоест числата които дават принос +1, са "доста" повече от тези, които дават принос -1. Т.е. [tex]a_{n}[/tex] е голямо.

Пафнутий · Пуснато на: Wed Nov 26, 2008 9:21 pm Заглавие:

Аз пък доказвам за подусловие б), че поне един член на редицата в интервала [tex]a_{2^n}[/tex] и [tex]a_{2^{n+1}}[/tex] е числено равен на [tex](n+1)[/tex] Wink

Baronov · Пуснато на: Thu Nov 27, 2008 1:52 pm Заглавие:

r2d2 · Пуснато на: Fri Nov 28, 2008 2:07 pm Заглавие:

Ще започнем с очевидното твърдение, че числата k и 2k имат един и същ най-голям нечетен делител!

Ще докажем с индукция, че [tex]a_{2n}=a_{4n}[/tex]
1. n=1 a_2=a_4=2 - изпълнено е.
2. Допускаме, че е вярно при n.
3. Трябва да докажем, че [tex]a_{2n+2}=a_{4n+4}.[/tex]

Eто и картинка:
Ясно е, че [tex]a_{4n+1}=a_{4n}+1[/tex] (означено е със стрелка нагоре), понеже [tex]a_{4n+2}, \; a_{2n+1} [/tex]имат един и същ най-голям нечетен делител, изменението в редицата от [tex] a_{2n}[/tex] до [tex]a_{2n+1} [/tex]e такова, каквото е от[tex] a_{4n+1} [/tex]до [tex]a_{4n+2}[/tex] (означено с виолетова точка). После [tex]a_{4n+3}=a_{4n+2} - 1[/tex] (стрелка надолу) и накрая изменението в редицата от [tex]a_{2n+1}[/tex] до [tex]a_{2n+2}[/tex] e такова, каквото е от [tex]a_{4n+3} [/tex]до [tex]a_{4n+4} [/tex](означено с зелена точка). Двете стрелки се унищожават и се вижда, че изменението е едно и също!

r2d2 · Пуснато на: Fri Nov 28, 2008 2:30 pm Заглавие:

Aналогично се доказва, че [tex]a_{4n-1} = a_{2n-1}[/tex].

Понеже [tex]a_{4n+1}=a_{4n}+1[/tex], получаваме и равенството [tex]a_{4n+1}=a_{2n}+1[/tex].
Понеже [tex]a_{4n-1}=a_{4n-2}-1[/tex] имаме и [tex]a_{4n-2}=a_{2n-1}+1[/tex]. (Тези две равенства могат да се докажат и чрез индукция.)

Първите две равенства, показват че ако едно число се среща веднаж, то се среща безброй пъти.

От вторите две имаме [tex]a_5=a_2+1=3; a_{10}=a_5+1=4; a_{21}=a_{10}+1=5; a_{42}=a_{21}+1=6[/tex]
Ясно е, че повтаряйки този процес можем да получим произволно число.

Пафнутий · Пуснато на: Fri Nov 28, 2008 3:19 pm Заглавие:

Моето решение е значително по-сложно и дълго. Първо доказвам по индукция, че [tex]a_{2^n}=2[/tex], като използвам следната лема:
[tex]a_{2^n+i}=a_{i}+a_{2^n} [/tex] за [tex]i<2^{n-1}[/tex], която може да се усили и до [tex]a_{2^n+2^{n-1}+...+2^{n-k}+i}=a_{2^n+2^{n-1}+...+2^{n-k}}+a_{i}[/tex] за [tex]i<2^{n-k-1}[/tex]
Оттам лесно следва, че [tex]a_{2^n-1}=1[/tex]. После пак по индукция доказвам, че поне един от членовете на редицата между [tex]a_{2^n}[/tex] и [tex]a_{2^{n+1}}[/tex] e равен на [tex](n+1)[/tex], отново използвайки лемата, откъдето задачата си следва Wink