Finding Recursive formula for value of a game

219 Views Asked by At

enter image description here

I understand the value of the game changes depending on what pile I take the coin from. If I take a coin from the front, I get $i+1$ coins (if I take $i = 1$, now $i =2$). This happens until $i = j$ and then the last player gets that coin worth $V(i+n,j-n)$. Does this suffice for a "recursive formula? What are the bounds?

2

There are 2 best solutions below

0
On BEST ANSWER

Let $S(i,j)=x_i+x_{i+1}+\dots+S_j$.

Then for $2\le i+1\le j\le n$ we have $V(i,j)=S(i,j)-\min(V(i+1,j),V(i,j-1))$.

Suppose the first player is facing $x_i,x_{i+1},\dots,x_j$. The total value available is $S(i,j)$. If he takes from the left end, then he leaves $x_{i+1},\dots x_n$. From that the second player will manage to secure $V(i+1,j)$, so the first player's take will total $S(i,j)-V(i+1,j)$. Similarly, if he takes from the right end, then his take will be $S(i,j)-V(i,j-1)$. To maximize his take he wants to secure the larger of these two, which is $S(i,j)-\min(V(i+1,j),V(i,j-1))$.

The boundary conditions must cover the situations where the first player does not have a choice of two moves. In other words, we also need $V(i,i)$. In such cases the first player's only move is to take the remaining coin, so $V(i,i)=S(i,i)$ for $1\le i\le n$.

0
On

Does this suffice for a "recursive formula?

I believe not.

A recursive formula for $V$ at the arguments $(i, j)$ will use the value of $V$ at other arguments than $(i,j)$.

Your task is more specific about those other arguments, it wants you to define $V$ at $(i,j)$ using the values of $V$ at $(i+1,j)$ and at $(i,j-1)$.

An example would be: $$ V(i,j) = 3 V(i+1,j) + V(i,k-1) $$ (Note: this is just an example, no solution :-)