Let *S*(*n*, *k*) be a number of states of the game where two bots together can make *n* moves and first bot can make *k* moves itself (*k* ≤ *n*). It is obvious that *S*(*n*, 0) = *S*(*n*, *n*) = *n* + 1. *S*(*n*, *k*) can be defined by the simple recurrence relation *S*(*n*, *k*) = 1 + *S*(*n* - 1, *k* - 1) + *S*(*n* - 1, *k*). Hence *S*(*n*, *k*) = *F*(*n*, *k*) - 1 where *F*(*n*, *k*) is defined by recurrence relation *F*(*n*, *k*) = *F*(*n* - 1, *k* - 1) + *F*(*n* - 1, *k*). It is a well-known formula for binomial coefficients. So where *a* and *b* are some constants. They can be found using the foregoing equation for *S*(*n*, 0): *a* = 2, *b* = 1. Hence . But in the optimal winning strategy both bots make exactly *N* moves each so *n* = 2*N* and *k* = *N*. Finally we have that the number of possible states is equal to

.

I found the same formula for this problem but by analysing a large table.

Do you know any sources where the proof for the formula f(i,j) = f(i-1,j-1) + f(i-1,j) = combination(i+a,j+b)? I could not google it since I dunno how to search with mathematical formula.

I came up with same approach, so I will try to explain how it works. You know, that F(n,0)=S(n,0)+1=n+2=C(n+2,1); F(n,n)=S(n,n)+1=n+2=C(n+2,1)=C(n+2,n+1). We know, that F has the same recurrence relation as C. Let's try calculating some other values. For example F(2,1)=F(1,0)+F(1,1)=C(1+2,1)+C(1+2,1+1)=C(3,1)+C(3,2)=C(4,2). So the good guess would be F(n,k)=C(n+2,k+1). You can prove it by induction.

Actually I am prone to disagree that recurrence relation will necessarily result in combination(i+a, j+b) as a solution. It really depends on boundary values. It could have been twice the combination of some values or even not a combination at all. But it always seems to be some sum (finite or infinite) of combinations

why S(n,k)=F(n,k)-1; please explain it?

By transition from

StoFwe get rid of the unnecessary constant (1) in the recurrence relation forS.