 Регистрирайте се
| Предишната тема :: Следващата тема |
| Автор |
Съобщение |
Saposto_MM
Напреднал
Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
  
гласове: 67
|
 Пуснато на: Sun Jul 12, 2009 6:36 pm Заглавие: Линейно-рекурентни... |
|
|
Нека [tex]c[/tex] е положително цяло число. Редицата [tex]\{\math{f}_n\}[/tex] е дефинирана както следва:
[tex]\math{f}_1=1[/tex], [tex]\math{f}_2=c[/tex], [tex]\math{f}_{n+1}=2\math{f}_n-\math{f}_{n-1}+2[/tex] [tex]\left(n\ge 2\right)[/tex].
Докажете, че за всяко [tex]k\in\mathbb{N}[/tex], съществува [tex]r\in\mathbb{N}[/tex], такова че [tex]\math{f}_{k}\math{f}_{k+1}=\math{f}_{r}[/tex].
И две допълнения от мен:
a) може ли [tex]c[/tex] да не бъде цяло;
б) може ли [tex]c[/tex] да не бъде положително? |
|
| Върнете се в началото |
|
 |
Реклама
|
| Пуснато на: Заглавие: Реклама |
|
|
|
|
|
| Върнете се в началото |
|
|
martin.nikolov
Напреднал
Регистриран на: 22 Apr 2009
Мнения: 489
гласове: 21
|
| Пуснато на: Mon Jul 13, 2009 6:51 pm Заглавие: |
|
|
Предполагам, че има интересно хитро решение. Аз не можах да измисля нищо и затова го направих с директни сметки.
За общия член се получава: [tex]f_n=n^2+(c-4)n+(4-c)[/tex]. От тук при дадено k заместваме и решаваме относно r. Получава се [tex]r=k^2+(c-3)k+(4-c)[/tex]. От тук е ясно, че c трябва да е цяло. Ако не е положително, твърдението няма да е вярно за всяко k, а от дадено цяло число нататък.
Може да сеъм сбъркал някъде в сметките. |
|
| Върнете се в началото |
|
|
Saposto_MM
Напреднал
Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
гласове: 67
|
| Пуснато на: Mon Jul 13, 2009 7:23 pm Заглавие: |
|
|
Да, има възможност да съществува някакво комбинаторно решение. Иначе и аз го решавам почти като теб. Решението във файла, от който го взех е същото (в общи линии).
А относно б) от въпроса ми, отговорът (поне така както аз го решавам) е положителен! Естествено, с тази формула, която си написал, при някои отрицателни [tex]c[/tex], индекса е отрицателен. Но това може, така да се каже, да се заобиколи!
Иначе самата задача е от съкратения списък за МОМ 1984! |
|
| Върнете се в началото |
|
|
martin.nikolov
Напреднал
Регистриран на: 22 Apr 2009
Мнения: 489
гласове: 21
|
| Пуснато на: Mon Jul 13, 2009 7:29 pm Заглавие: |
|
|
Жалко, понеже беше очевидно, че задачата е олимпииска аз се надявах да има кефещо тарикатско решение без сметки. За положителното или отрицателно съм съгласен, в зависимост от тълкуването може да се приеме.
Иначе за сметките, аз първо намерих общия член по стандартния начин и чак после видях, че може и без да се знае как се решават линейни рекурентни редици. |
|
| Върнете се в началото |
|
|
Saposto_MM
Напреднал
Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
гласове: 67
|
| Пуснато на: Mon Jul 13, 2009 7:45 pm Заглавие: |
|
|
| martin.nikolov написа: | | За положителното или отрицателно съм съгласен, в зависимост от тълкуването може да се приеме. |
Може ли да кажеш какво точно имаш предвид. Защото мисля, че не е това, което аз имам.
| martin.nikolov написа: | | Иначе за сметките, аз първо намерих общия член по стандартния начин и чак после видях, че може и без да се знае как се решават линейни рекурентни редици. |
Става ли да покажеш как? С индукция ли?
Иначе това, че не е публикувано комбинаторно решение, не отхвърля съществуването му. Такива решения, често са доста трудни за откриване. Честно казано на състезание, ако ми се падне такава задача, в началото ще реша да си изкарам сигурен максимален брой на нея, отколкото несигурен такъв, макар възможност за специална награда (искам да кажа, че ще тръгна по алгебричен път (бил той и грозен, и хамалски), вместо да бродя в дебрите на комбинаториката с цел (неизвестно дали въобще съществува) красиво решение). |
|
| Върнете се в началото |
|
|
martin.nikolov
Напреднал
Регистриран на: 22 Apr 2009
Мнения: 489
гласове: 21
|
| Пуснато на: Mon Jul 13, 2009 8:16 pm Заглавие: |
|
|
| MM написа: | | martin.nikolov написа: | | За положителното или отрицателно съм съгласен, в зависимост от тълкуването може да се приеме. |
| Цитат: |
Може ли да кажеш какво точно имаш предвид. Защото мисля, че не е това, което аз имам.
|
|
Не, аз просто се съгласявах, че индекса ще е отрицателен в някой случай.
| Цитат: |
| martin.nikolov написа: | | Иначе за сметките, аз първо намерих общия член по стандартния начин и чак после видях, че може и без да се знае как се решават линейни рекурентни редици. |
Става ли да покажеш как? С индукция ли?
|
Записваш го така [tex]f_{n+1}-f_n=f_n-f_{n-1}+2[/tex], полагаш [tex]a_n=f_{n+1}-f_n[/tex]. Това е аритметична прогресия, за която се знае първия член и разликата. Следователно може да се сметне сумата
[tex]S_n=a_1+\cdots+a_n=(f_2-f_1)+(f_3-f_2)+(f_4-f_3)+\cdots+(f_{n+1}-f_n)=f_{n+1}-f_1[/tex]
| Цитат: |
Иначе това, че не е публикувано комбинаторно решение, не отхвърля съществуването му. Такива решения, често са доста трудни за откриване. Честно казано на състезание, ако ми се падне такава задача, в началото ще реша да си изкарам сигурен максимален брой на нея, отколкото несигурен такъв, макар възможност за специална награда (искам да кажа, че ще тръгна по алгебричен път (бил той и грозен, и хамалски), вместо да бродя в дебрите на комбинаториката с цел (неизвестно дали въобще съществува) красиво решение). |
Да, не се изразих правилно. Надявах се да ти е известно за да го постнеш. Иначе е ясно, че дори на никой да не е извесно не значе че го няма. Пък и стандартните методи трябва да се знаят, и да се изпозват. |
|
| Върнете се в началото |
|
|
Saposto_MM
Напреднал
Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
гласове: 67
|
| Пуснато на: Mon Jul 13, 2009 9:43 pm Заглавие: |
|
|
| martin.nikolov написа: |
Записваш го така [tex]f_{n+1}-f_n=f_n-f_{n-1}+2[/tex], полагаш [tex]a_n=f_{n+1}-f_n[/tex]. Това е аритметична прогресия, за която се знае първия член и разликата. Следователно може да се сметне сумата
[tex]S_n=a_1+\cdots+a_n=(f_2-f_1)+(f_3-f_2)+(f_4-f_3)+\cdots+(f_{n+1}-f_n)=f_{n+1}-f_1[/tex]
|
А ти от това директно общия член ли намираш или правиш някаква друга врътка.
Ако може покажи!
А иначе ето до какво друг стигнах.
Взимаме [tex]c\le 0[/tex]. Получаваме още [tex]\left(n^2+\left(c-4\right)n+4-c\right)\left(\left(n+1\right)^2+\left(c-4\right)\left(n+1\right)+4-c\right)=\left(-n^2+\left(3-c\right)n\right)^2+\left(c-4\right)\left(-n^2+\left(3-c\right)n\right)+4-c[/tex]
Значи имаме [tex]f_{n}f_{n+1}=f_{-n^2+\left(3-c\right)n}[/tex], за което естествено трябва [tex]-n^2+\left(3-c\right)n>0[/tex]. Последното е вярно за [tex]n\in \left(0,3-c\right)[/tex]. Също така имаме, че ни трябва [tex]n^2+\left(c-3\right)+c-4>0[/tex]. Последното е вярно за всички [tex]n[/tex] извън интервала [tex]\left(-\frac{sqrt{c^2-2c-7}+c-3}{2},\frac{sqrt{c^2-2c-7}-c+3}{2}\right) [/tex] (Ако дискриминантата е отрицателна нямаме проблем с положителността). Лесно се проверява, че последния интервал е подинтервал на по-горния. Така ако за някое [tex]n[/tex] имаме проблем с единия индекс, то няма да имаме с другия и ще вземем него (под "проблем" разбирам отрицателност). Значи за всяко [tex]c[/tex] нямаме противоречие с това, което се иска да се докаже в задачата. |
|
| Върнете се в началото |
|
|
martin.nikolov
Напреднал
Регистриран на: 22 Apr 2009
Мнения: 489
гласове: 21
|
| Пуснато на: Mon Jul 13, 2009 10:43 pm Заглавие: |
|
|
| MM написа: | | martin.nikolov написа: |
Записваш го така [tex]f_{n+1}-f_n=f_n-f_{n-1}+2[/tex], полагаш [tex]a_n=f_{n+1}-f_n[/tex]. Това е аритметична прогресия, за която се знае първия член и разликата. Следователно може да се сметне сумата
[tex]S_n=a_1+\cdots+a_n=(f_2-f_1)+(f_3-f_2)+(f_4-f_3)+\cdots+(f_{n+1}-f_n)=f_{n+1}-f_1[/tex]
|
А ти от това директно общия член ли намираш или правиш някаква друга врътка.
Ако може покажи!
|
Ами от тук [tex]f_{n+1}=S_n+f_1[/tex]. А [tex] S_n[/tex] е сумата на аритметична прогресия с разлика 2 и първи член c-1.
Да, за останалото аз бях решил, че индекса ще е отрицателен в някой случай и не го смятах. |
|
| Върнете се в началото |
|
|
Saposto_MM
Напреднал
Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
гласове: 67
|
| Пуснато на: Tue Jul 14, 2009 9:35 am Заглавие: |
|
|
Извинявай, всичко е ясно просто бях използвал неправилната формула за аритметична прогресия и не ми се получаваха нещата (утрото е по-мъдро от вечерта).
Иначе добре си го направил. Аз съвсем наскоро се запознах с теория около тези редици и веднага я прилагах, не съм се замислял за друг начин ("знанията понякога ограничават ума" - теория, която подкрепям). |
|
| Върнете се в началото |
|
|
|
|
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
Може да прикачвате файлове
Може да сваляте файлове от този форум
|
|
Меню
