1567 - A simple stone game

All about problems in Volume 15. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

1567 - A simple stone game

I have generated Some pattern for this problem But how actually solve is out of my capabilities :(

Some observation :
1 . k = 1 , lossing Pos = 2, 4 , 8 , 16 , .... (2 ^ i )
2 . k = 2 , Losing Pos follows This : T(n) = T(n-1) + T(n-2)
3. k = 3 , Losing Pos Follow : T(n) = T(n-1) + T(n-4)
4 . k = 4 , Losing Pos follow : T(n) = T(n - 1) + T(n - 6)
5 . k = 5 , Losing Pos follow : T(n) = T(n - 1) + T(n - 8)
6. k = 6 , Losing Pos follow : T(n) = T(n - 1) + T(n - 10)

So in general k = p , k > 1 , Losing Pos follow T(n) = T(n-1) + T (n - 2*k+2 )

Now I have derived it , How am I supposed to find if a given N follow the formula or not ,,
Any Hint Please :)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1567 - A simple stone game

Your pattern isn't correct.
For k = 6 the first few losing positions are:
2, 3, 4, 5, 6, 7, 9, 11, 13, 16, 19, 23, 27, 32, 38, 45, 54, 63, 74, 87, 103, ...
The losing positions >= 63 follow: T(n) = T(n - 1) + T(n - 11)
Check input and AC output for thousands of problems on uDebug!