K piles stone game

Their are k piles with total n stones in some order where each pile can have stones greater or equal to zero.Two player A and B plays a game in which player A cant see the configuration of piles but he knows the size of each pile only order is unknown to him.Player A points to a pile and Player B removes one stone from that pile.

If their is no stone in that pile player B informs player A that this pile is empty.

Now the Player A wants atleast C stones in minimum moves.I want to find the minimum moves P so that Player A gets atleast C stones after P moves whatever be the initial configuration of piles.

Like if we have three piles and six stones and player A needs to get four of them . Then minimum moves required to get 4 stones is 4.

• If the initial configuration is $4,1,1$, A may need $6$ moves in order to get $4$ stones: there is no strategy that guarantees that he won’t point twice at an empty pile. – Brian M. Scott Dec 8 '13 at 5:03
• I want to tell minimal value P for which there exists an initial stones distribution and moves strategy that makes Player A win no matter what order the Piles are in. – user3001932 Dec 8 '13 at 5:07
• I can get it in above example in 4 moves if all the 3 piles have 2,2,2 stones .Then Player A point to one pile two times and any other pile two times to get total of 4 stones. – user3001932 Dec 8 '13 at 5:09

Suppose that the piles have $a_1,a_2,\ldots,a_k$ stones, where $a_1\le a_2\le\ldots\le a_m=\ldots=a_k$. If $C\le a_1$, then of course Player $A$ will need only $C$ moves. It’s also clear that if $m=1$, so that all piles are the same size, Player $A$ will need only $C$ moves. Suppose that $m>1$ and $C>a_1$. In the worst case Player $A$ picks the smallest pile $a_1+1$ times and collects $a_1$ stones. If $m=2$ or $C\le a_1+a_2$, he need not make any more bad moves, so he can collect $C$ stones in $C+1$ moves. If $m>2$ and $C>a_1+a_2$, he could make $2$ bad moves in collecting the first $a_1+a_2$ stones. If $m=3$ or $C\le a_1+a_2+a_3$, he need not make any more bad moves, so he can collect $C$ stones in $C+2$ moves.
Let $b_0=0$, and for $i=1,\ldots,k$ let $b_i=a_0+\ldots+a_i$. Suppose that $b_i<C\le b_{i+1}$; if $m>i$, Player $A$ could make $i$ bad moves in collecting the first $b_i$ stones and therefore need altogether $C+i$ moves to collect $C$ stones. However, he never needs more than $m-1$ bad moves to reach a position in which all piles are the same size, so he actually needs at most $$C+\min\{m-1,i\}$$ moves to collect $C$ stones. For fixed $n,k$, and $C$, therefore, we want to choose $a_1,\ldots,a_k$ so as to minimize $\min\{m-1,i\}$, where $i$ is the unique index such that $b_i<C\le b_{i+1}$.
• @user3001932: It’s defined implicitly in the first sentence: it’s a basic fact that there are a unique $q$ and $r$ satisfying those conditions. It can be explicitly defined as $\left\lfloor\frac{n}k\right\rfloor$. – Brian M. Scott Dec 8 '13 at 5:23
• @user3001932: If you’re using C syntax and mean what I’d write $r=n\bmod k$, then yes, that’s what $r$ turns out to be. In your example $r=0$, $q=2$ and $kq=6=n$, so for any $C\le 6$ you need just $C$ moves. – Brian M. Scott Dec 8 '13 at 5:30