Winning a card game

Question

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.

Answer 1

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

Answer 2

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.