Scenario: Each player has a deck of N cards. The first player controls an object called Grindclock, which means that at each turn, he can either :

  • Add a "charge" counter on Grindclock, or
  • Remove the top X carts of his opponent's deck

Only one of these action is possible. The second player doesn't control anything, and pass every turn. However, at each of his turn, he will have to draw a card from his deck (so he will remove the top cart from his own deck).

The game ends when the second player cannot draw his card.

What is the equation of the optimal amount of "charge" counter that should be put on Grindclock to end the match in the lowest amount of turns possible?

A friend on a social network shared that the answer was |√(N+1)-1|, but he didn't described why, and I'm very curious. I tried to solve it on my own, but it seems to be outside by reach. I'm not sure about the starting equation.

  • $\begingroup$ Is $X$ the current number of charge counters on the Grindclock? $\endgroup$
    – JimmyK4542
    Jul 14, 2014 at 1:30
  • $\begingroup$ @JimmyK4542 Yes, and $X$ starts at $0$. $\endgroup$
    – Théophile
    Jul 14, 2014 at 1:32
  • $\begingroup$ Are the charges lost when the opponent loses cards? $\endgroup$
    – vadim123
    Jul 14, 2014 at 1:35
  • 1
    $\begingroup$ @vadim123 No, the charges are never lost. $\endgroup$
    – Théophile
    Jul 14, 2014 at 1:36

2 Answers 2


Since this game is a discrete process, I thought it might be interesting to try different values of $N$ (the number of cards in the initial deck) and $x$ (the number of charge counters added) to see what number of charge counters ends the game fastest for each $N$.

It turns out that the equation $x = \lceil \sqrt{N + 1} - 1 \rceil$ (rounding up to the next integer when $N+1$ is not a perfect square) is a good choice of how many charge counters to put on Grindclock. But there are many values of $N$ for which you can put a different number of charge counters on Grindclock and still finish in the same number of turns.

In fact you can have a surprisingly large range of choices of $x$ for some values of $N$ that all end the game just as quickly as $x = \lceil \sqrt{N + 1} - 1 \rceil$. For example, if $N = 15$, then by adding $\lceil \sqrt{N + 1} - 1 \rceil = 3$ charge counters you can end the game in $7$ turns (including the turn on which the other player cannot draw a card). There is no way to end the game faster, but any integer value of $x$ in the range $2 \le x \le 5$ will end the game in the same number of turns.

In general, the length of the game will be $$ g(N,x) = x + \left\lceil \frac{N - x + 1}{x + 1} \right\rceil. $$ The term $1$ occurs in the numerator because according to the original problem statement, if $x + 1$ divides $N - x$ exactly, the second player will draw the last card on turn $x + \frac{N - x}{x + 1}$, and will only fail to draw a card on the next turn.

It's not hard to build a table giving the length of the game for various values of $N$ and $x$ and to pick out the range of optimal values of $x$ for each $N$. One pattern that becomes apparent is that if $N = k(k+2) - 1$ for some integer $k$, then $x = k$ will result in a game of length $2k$, and no other value of $x$ will end the game as quickly. This appears to be the only case in which the optimal value of $x$ is unique for a given $N$.

  • $\begingroup$ $$x + \left\lceil \frac{N - x + 1}{x + 1} \right\rceil = x-1 + \left\lceil \frac{N + 2}{x + 1} \right\rceil$$ $\endgroup$ Jul 15, 2014 at 2:47
  • 1
    $\begingroup$ True. The left-hand side has a clearer relationship to the two phases of the game, but the right-hand side is simpler to compute. $\endgroup$
    – David K
    Jul 15, 2014 at 6:05

Your friend is right. Suppose you charge for the first $x$ turns, then remove cards from that point on. That means that your opponent will lose 1 card per turn for the first $x$ turns (from drawing cards), then $x+1$ per turn until the end of the game ($x$ from your special ability, plus $1$ from drawing).

After the first $x$ turns, your opponent has $N-x$ cards left, so the total number of turns it takes to reduce your opponent's deck to $0$ is:

$$f(x) = x + \frac{N-x}{x+1}$$

The derivative is

$$f'(x) = 1 + \frac{-1-N}{(x+1)^2}$$

Setting this to $0$ and solving for $x$, we get $x = \sqrt{N+1} - 1$. Bear in mind that if $\sqrt{N+1}$ is not an integer, you'll have to round up or down.

  • 1
    $\begingroup$ The exact formula for the number of turns rounds the result to an integer, so for a given $N$ there may be several values of $x$ for which the number of turns is minimized. These values are all near the zero of $f'(x)$, however; I think you can always optimize your game by rounding that value upward when it is not already an integer. $\endgroup$
    – David K
    Jul 15, 2014 at 2:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .