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.

  • $\begingroup$ 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. $\endgroup$ – Brian M. Scott Dec 8 '13 at 5:03
  • $\begingroup$ 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. $\endgroup$ – user3001932 Dec 8 '13 at 5:07
  • $\begingroup$ 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. $\endgroup$ – user3001932 Dec 8 '13 at 5:09

Edit: My original answer was based on a misunderstanding of the problem and was actually wrong even for that interpretation. The problem as it now stands seems somewhat difficult. This is not an answer, and I may end up deleting it, but it does include some ideas that may be useful and shows why a complete answer may be a bit complicated, so I’ll leave it up for now.

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}$.

  • $\begingroup$ What is q in your above explanation.? $\endgroup$ – user3001932 Dec 8 '13 at 5:21
  • $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Dec 8 '13 at 5:23
  • $\begingroup$ Now,Can i say r then to be n%k ? Then can u solve above example by yur explanation ? $\endgroup$ – user3001932 Dec 8 '13 at 5:28
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Dec 8 '13 at 5:30
  • $\begingroup$ Nice explanation.Thanx $\endgroup$ – user3001932 Dec 8 '13 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.