7
$\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$
1
  • $\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

2 Answers 2

Reset to default
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$
6
  • $\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
  • $\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 that you have read and understand our privacy policy and code of conduct.

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