|
Тема |
Re: имах предвид.... [re: nikifortzvetkov] |
|
Автор | Пoнaзнaйвaщ (Нерегистриран) | |
Публикувано | 20.12.06 18:32 |
|
|
Редица на Фибоначи:
1, 1, 2, 3, 5, 8, 13,..
а_0=а_1=1, а_(n+1)=a_n+a_(n-1) за n>0
Свойство 1: a_n<=2*a_(n-1) - очевидно
Свойство 2: 4*а_n < 3*a_(n+1) - вярно за всяко n>=1 (3*а_(n+1)=3*a_n+3*a_(n-1)>4*a_n)
Твърдение: Ако си на ход и оставащите клечки са равни на някой член от редицата на Фибоначи и не можеш да вземеш всички оставащи клечки наведнж, то при правилна игра на противника ти ще загубиш играта.
Доказателство: Очевидно вярнo ако клечките са 2,3,5
Нека е вярно за всички числа на фибоначи, които са <=a_k, където к>=4.
Ще докажем твърдението за а_(к+1).
а_(к+1)=а_к+а_(к-1)
Ти си на ход и взимаш p на брой клечки.
1) p>=a_(k-1). Противника ти взима останлите клечки(може да го направи заради св.1)
2)р<а_(к-1), противника ти може да играе така, че да взема последната от първите а_(к-1) клечки(т.е. на масата да останат а_к на брой клечки и ти пак да си на ход) - следва от индуцкията за а_(к-1). В момента в който остават а_к на брой клечки, противника ти с последният ход е взел не повече то 2/3 от а_(к-1), т.е. ти ще имаш право да вземеш не повече от 4/3 от а_(к-1), което е по-малко от а_к(свойство 2). Т.е. остават а_к клечки и ти си на ход и не можеш да ги вземеш наведнъж - по индуцкия губиш.
987 е число на Фибоначи.
Ако първият вземе 213(както и е предложено от IdleFellow), то вторият не може да вземе останалите 987 наведнъж, съответно първият има печеливша стратегия по-натам.
|
| |
|
|
|