двама души разполагат с една куп4ина кле4ки и играят следната игра.
първия избира произволен брои кле4ки но няма право да вземе вси4ки.
втория има право да избере не пове4е от удвоения брои кле4ки на първия
след това идва ред на първия които също има право да избере не пове4е от удвоения брои кле4ки на противника
изобщо при всеки ход всеки игра4 има право да избере не пове4е от удвоения брои кле4ки, които противника му е взел при последния си ход
освен това всеки игра4 е длъжен всеки път да вземе поне една кле4ка
пе4ели този които вземе последните кле4ки от куп4ината
първона4ално в куп4ината има 1200 кле4ки
колко кле4ки трябва да жземе първия за да е сигурен 4е при правилна игра ште спе4ели

Съдържаниет е скрито
Влезте за да го видите

Аз бих взел 213 клечки

Горното може и да не е вярно !

Редица на Фибоначи:
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 наведнъж, съответно първият има печеливша стратегия по-натам.

Моята идея беше следната - известно е, че всяко естествено число N е или число на Фибоначи, или може да се представи еднозначно като сума от числа на Фибоначи, като най-голямото събираемо в тази сума е най-голямото число на Фибоначи, не по-голямо от N, следващото е най-голямото число на Фибоначи, не по-голямо от разликата на N с първото и т.н. при което в тази строго намаляваща сума няма да имаме съседни членове от редицата на
Фибоначи. И така - на свой ход, съобразявайки се с ограничението за броя клечки, които можем да вземем, наложено ни от предишния ход на партньора, взимаме толкова клечки, колкото е сумата на няколко (произволен брой) последователни члена от представянето на оставащия брой клечки като сума от числа на Фибоначи, започвайки от най-малкия, така че общата сума на взетите клечки да е по-малка от половината от следващия по-голям член в сумата. Така намаляваме броя членове в представянето, а партньорът, при следващия си ход, ще бъде принуден да "развали" най-малкия член в сумата на оставащите клечки и по-този начин няма да може да намали броя на членовете в сумата. Разбира се, важно е и съображението, че на свой ход винаги ще можем да вземем поне един член от сумата, тоест, че стратегията е реално приложима. Ако допуснем, че след като партньорът е "развалил" едно число на Фибоначи, ние не можем да вземем поне най-малкия член F_n в сумата на оставащите клечки, това означава, че този най-малък член е повече от 2 пъти по-голям, от броя клечки взети при последния ход, от което следва, че при последния ход са взети по-малко от F_n-1 брой клечки и оттук, че имаме нееднозначно представяне на "разваленото" число на Фибоначи - като сума на оставащия брой клечки след "развалянето" му и като сума на взетия при последния ход брой клечки, от една страна и като число на Фибоначи, от друга. Това ни дава една конструктивна стратегия за тази игра.

Горното може и да не е вярно !

Хммм, би ли пояснил как ще спечелиш като първи с начални 12 клечки? Не сичко дето мирише на Фибоначи, е Фибоначи, значи:))).

12 = 8 + 3 + 1

И тъй като 1 + 3 не е по-малко от половината на 8, при първия си ход можем да вземем само 1 клечка

Горното може и да не е вярно !

благодаря за публикуваното решение което според мен е напълно вярно

Моля, за това сме тук ! Цялостно и напълно издържано решение е дал Поназнайващ, аз само нахвърлях някои щрихи. А откъде е тази задача ?

Горното може и да не е вярно !