10
$\begingroup$

In the land of Humilia, a tournament game is played between two players with 101 stones in a pot between them. On each turn, a player may take up to five stones from the pot (and must take at least one), and nominally, the winner is whoever winds up with the most stones in the end. However, modesty is valued above all in Humilia, and if a player wins by more than five stones in the end, they will be shunned and disqualified from the tournament.

Question: Under perfect play, do you choose to be the player who plays first, or second?

Bonus: What happens if you must instead not win by more than three stones? In general, what is the result if the rules are such that you may take $n$ stones but may not win by more than $k$, with a sufficiently large starting pot?

Improve this question
$\endgroup$
2
  • $\begingroup$ Have you found an answer to the bonus question? If yes, then please post it . $\endgroup$
    – Hemant Agarwal
    Jul 5, 2022 at 19:41
  • 1
    $\begingroup$ @HemantAgarwal Happy to report the bonus question has been answered :) $\endgroup$
    – Feryll
    Oct 14, 2023 at 5:02

3 Answers 3

Reset to default
7
$\begingroup$

Time for an answer to the bonus question! We'll go straight to the generalized case. The theorem we shall prove is:

When $N, k$ are odd, the first player wins if and only if $n \leq k+1$ or $N \leq 2k + 1$.

We have chosen to assume that $N$ is odd, since if $N$ is even, it introduces the complication of draws. Moreover, without loss of generality we have assumed $k$ is odd; we may do this because the case $(N,n,k)$ with even $k$ is equivalent to the case $(N,n,k-1)$, since the ending difference between the two players' stone counts must also be odd whenever their sum $N$ is odd.

Now, we show the cases where the first player can win:

If $n \leq k+1$ we use the copying strategy in Rand al Thor's answer, i.e. take $n$ to start, and then copy player two afterward. Our lead is always between $0$ and $k+1$, and will not end in a draw with an ending difference of $0$ or immodestly with an ending difference of $k+1$ (the ending difference must be odd), so we are guaranteed victory.

So suppose $k + 1 < n$ and the second inequality $N \leq 2k + 1$ holds. Then we may take $k+1$ stones with our first move, which is already more than half in the entire game. We can keep our lead at the end of our turns at a maximum of $k+1$ using the copying strategy; again, the game finishes with our lead at most $k$ and so we win.

Now for the cases where the second player wins:

We have $k+1 < n$ and $2k+3 \leq N$. We write $N = 2k+3 + 2\ell$ for some $\ell \geq 0$, choosing to think of $N$ as composed of an "ending pot" of $2k+3$ stones plus two "lobes" of $\ell$ stones, one lobe for each player. Refer to these lobes as $L_1$ and $L_2$.

Our strategy as the second player: If $L_1$ and $L_2$ are empty because $N = 2k+3$, skip this paragraph. Otherwise copy the first player's moves (where we visualize him as taking stones from $L_1$, and us from $L_2$) up until he exhausts $L_1$, and possibly started digging into the ending pot. Once this happens, exhaust $L_2$ with our move and take no more.

Now, if the first player leaves the ending pot with $k+1$ or less in their next move, they lose since their lead would be at least $k+2$, and we can render them immodest by always taking a single stone. Otherwise, we take exactly $k+2$ ($\leq n$) from the ending pot, giving us a lead at most $k+1$ after our turn; as before, we are guaranteed to finish with more stones (all of $L_2$ and more than half of the ending pot) and a lead not exceeding $k$ after the final move.

Thus, for the case $N = 101$, $n = 5$ and $k = 3$ the winner is

the second player.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I'm so very pleased to see progress (or even a solution) on this problem after three years! I'm trying to verify your proof, but it's a little difficult. I agree up to the 2nd player strategy. First, if we're assuming k odd, so k = 2l - 1, then the denial of k >= n (as in your theorem statement) is k < n, that is, 2l - 1 < n, while you start with 2l < n. A word on this? Secondly, it's hard for me to see why we may be guaranteed to attain m - 2l stones after breaking from the initial copying strategy. $\endgroup$
    – Feryll
    Oct 13, 2023 at 4:25
  • $\begingroup$ For example, if (N,n,k) = (9,4,3), then (l,m) = (2,4), and according to your results player two wins (k < n and N > 7). In this case m - 2l = 0, so your strategy cannot be followed... and indeed, player one is the one with a winning strategy! He starts by taking four stones. Player two cannot render him immodest by e.g. always playing one stone, as player one copying will result in a 6-3 victory. $\endgroup$
    – Feryll
    Oct 13, 2023 at 4:42
  • 1
    $\begingroup$ Thanks, that was indeed an oversight and k >= n should be 2l >= n; I'll edit in a fix for that. As for what happens when the second player breaks from the copying strategy, that point is equivalent to the point at which the first player's total reaches m-2l stones for the first time (since if we copy that, both players will have a total of 2m-4l, and subtracting (2m+1)-(2m-4l) = (4l+1)). Thus, the second player is below m-2l and has a move that can take them to m-2l or larger, and since they can take any number less than that they can choose a move that takes them to exactly m-2l. $\endgroup$
    – Arcorann
    Oct 13, 2023 at 6:54
  • $\begingroup$ Good job! I can attest the proof is clean. I also took the liberty of simplifying it, if you don't mind, by removing any references to the derived variables m and l, changing inequalities to < and \leq, and also giving a more visually intuitive understanding for the algebra underlying player two's strategy. $\endgroup$
    – Feryll
    Oct 14, 2023 at 3:59
7
$\begingroup$

I choose to play

first.

My strategy is as follows:

  1. In the first move, take five stones.

  2. Every move thereafter, copy the second player's move. (If they take $n$ stones, I take $n$ too.)

  3. Continue until this is no longer possible or doing so would end the game. That means

    the number $m$ of stones remaining is less than or equal to the number $n$ that the second player took in their last move. Also, I now have $K+5$ stones and you have $K+n$, for some large number $K$.

    So if I take

    all remaining stones, then I'll have $K+5+m$ and you'll have $K+n$, where $0\leq m\leq n\leq 5$. So I win by at most 5 stones ($5+m\geq n$ but $5+m-n\leq5$).

Improve this answer
$\endgroup$
9
  • $\begingroup$ A good and valid answer, certainly; I must admit at this point to having misremembered the proper constant values to my own problem. I've included a "bonus" section for the problem which is hopefully more interesting, should you or others choose to solve it. In the event no one does, I'll just mark this as correct :) $\endgroup$
    – Feryll
    Jul 5, 2020 at 7:41
  • $\begingroup$ What if n= 5 and m= 0 ? In that case, both players will have the same number of stones . So, I am guessing that the answer is that this strategy will either lead to a win for the first player or will lead to a draw, right ? $\endgroup$
    – Hemant Agarwal
    Nov 10, 2021 at 1:10
  • $\begingroup$ @HemantAgarwal There's 101 stones in total, so someone has to win, as they can't end with the same number of stones. $\endgroup$
    – Rand al'Thor
    Nov 10, 2021 at 5:34
  • $\begingroup$ cool ...so, for 101 stones , the person who goes first, is guaranteed to win. But what about the general case : "In general, what is the result if the rules are such that you may take n stones but may not win by more than k, with a sufficiently large starting pot?" My understanding is is that in the general case, the first one will either win or the result will be a draw, right ? $\endgroup$
    – Hemant Agarwal
    Nov 10, 2021 at 6:56
  • $\begingroup$ @HemantAgarwal I think so, but it seems I didn't address the bonus puzzle in this answer (it was edited into the question after I answered). $\endgroup$
    – Rand al'Thor
    Nov 10, 2021 at 8:17
1
$\begingroup$

What I tried is the same game where you have 101 stones but instead of winning more than five would make you lose I tried it with 3.
Working on @Rand al' Thor's strategy by picking 5 first, I figured out we can always lose if we copy our opponent's move every time.
For eg.
If I first play 5, then we are left with 96 stones in total. Our opponent might take 3 and we can have turns of 3. If we blindly follow the strategy we would end up winning by 5 stones (which indeed is a defeat for us). But pertaining to rule 3 and we have basically done with 90 stones (95 in actual game since I am considering taking 5 and turns of 3 two separate things. Now the scenario is that it is our opponent's turn with we in the lead of 5. Our opponent could easily make this a game of taking one stones and in this way opponent can force us to win by more than 3 points.
So, if we follow same strategy of taking $n$ when we actually have to win with difference not more than $k$ where $n$ is greater than $k$, we could certainly lose if we follow the above mentioned strategy.

Improve this answer
$\endgroup$
6
  • $\begingroup$ What I want to say that the above mentioned strategy is not optimal for us in the bonus situation. I could not comment it since I do not have enough reputation to comment on others question or answer. $\endgroup$
    – Lakshay Sura
    Jul 5, 2020 at 9:54
  • 1
    $\begingroup$ Indeed, this essentially underlines why I considered my original formulation of the problem a "mistake," while the bonus question is in fact the problem I had in mind. Be sure to let us know if you figure the bonus out! $\endgroup$
    – Feryll
    Jul 5, 2020 at 11:32
  • $\begingroup$ Well what do you want to imply about k in bonus? Is it smaller or larger than n? $\endgroup$
    – Lakshay Sura
    Jul 5, 2020 at 11:52
  • $\begingroup$ Either case. If it's equal to or larger than $n$, then Rand's solution applies. $\endgroup$
    – Feryll
    Jul 5, 2020 at 11:58
  • $\begingroup$ So you want us to figure out who would win and what is the strategy? $\endgroup$
    – Lakshay Sura
    Jul 5, 2020 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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