Page 1 of 1

1567 - A simple stone game

Posted: Mon Apr 06, 2015 8:52 pm
by Repon kumar Roy
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 :)

Re: 1567 - A simple stone game

Posted: Thu Apr 09, 2015 12:52 am
by brianfry713
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)