Регистрирайте сеРегистрирайте се

Задача 16


 
   Форум за математика Форуми -> Задача на седмицата
Предишната тема :: Следващата тема  
Автор Съобщение
Pinetop Smith
Фен на форума


Регистриран на: 12 May 2007
Мнения: 961
Местожителство: Хасково
Репутация: 153.6Репутация: 153.6
гласове: 87

МнениеПуснато на: 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
Site Admin


Регистриран на: 12 Oct 2005
Мнения: 284
Местожителство: София(Варна)
Репутация: 45.6Репутация: 45.6Репутация: 45.6Репутация: 45.6Репутация: 45.6
гласове: 14

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

б) всяко естествено число се среща безброй много пъти.
stanislav atanasov, Турнир на градовете 2008
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение Посетете сайта на потребителя Yahoo Messenger
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Wed Nov 26, 2008 5:11 pm    Заглавие: Re: Задача 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 се среща безброй мого пъти.


Лесно се вижда, че [tex]a_{2^{n}-1}=1[/tex] , за всяко естествено число n.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Пафнутий
VIP


Регистриран на: 04 Mar 2008
Мнения: 1199

Репутация: 137.7
гласове: 54

МнениеПуснато на: Wed Nov 26, 2008 5:46 pm    Заглавие: Re: Задача 16

Baronov написа:
Николай.Каракехайов написа:
В безкрайната редица [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 се среща безброй мого пъти.

Лесно се вижда, че [tex]a_{2^{n}-1}=1[/tex] , за всяко естествено число n.
Да, така е, ама трябва да се докаже (предполагам, че имаш доказателство) Wink
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: 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
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: 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] е голямо.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Пафнутий
VIP


Регистриран на: 04 Mar 2008
Мнения: 1199

Репутация: 137.7
гласове: 54

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

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


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

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

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


Супер.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
r2d2
VIP


Регистриран на: 28 Feb 2007
Мнения: 1936
Местожителство: in the galaxy (Far Far Away)
Репутация: 311.2Репутация: 311.2
гласове: 179

МнениеПуснато на: 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](означено с зелена точка). Двете стрелки се унищожават и се вижда, че изменението е едно и също!



inter_cr.jpg
 Description:
 Големина на файла:  12.73 KB
 Видяна:  1992 пъти(s)

inter_cr.jpg


Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
r2d2
VIP


Регистриран на: 28 Feb 2007
Мнения: 1936
Местожителство: in the galaxy (Far Far Away)
Репутация: 311.2Репутация: 311.2
гласове: 179

МнениеПуснато на: 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]
Ясно е, че повтаряйки този процес можем да получим произволно число.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Пафнутий
VIP


Регистриран на: 04 Mar 2008
Мнения: 1199

Репутация: 137.7
гласове: 54

МнениеПуснато на: 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
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Задача на седмицата Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2020 math10.com.