5
$\begingroup$

Consider a game of two players: Player A and Player B. Each of them is assigned with the same number of soldiers. There is a battlefield (like a board game) with 7 tiles numbered 1 through 7 (a single line in an arithmetic order), with Player A's home-base at 'tile 1' and player B's home-base at 'tile 7'. At the start of the game, both's armies are on the middle tile 'tile 4'. A player wins the whole game if and only if her/his army reaches the other player's home-base. On any given turn, both simultaneously decide what fraction of one's total soldiers to be deployed. Whoever deploys more soldiers wins the battle and the winner's army advances by 1 tile (while the loser's army retreats by 1 tile). However, the winning army loses all soldiers but the losing army loses no soldiers. In addition, if both deploy the same number of soldiers, Player A loses that battle. What fraction of soldiers should Player A deploy at the 1st battle? (assuming fractional soldiers is possible)

My thought: A strategy that guarantees Player A to win cannot exist, because otherwise, such strategy would also exist for Player B, then contradiction. So my best guess is there exists a strategy for Player A such that she/he is guaranteed not to lose the game.

$\endgroup$
7
  • $\begingroup$ Just to make sure - the tiles are laid out in a single line? $\endgroup$
    – bobble
    Feb 2 at 4:36
  • $\begingroup$ Yes,1 to 7 as a arithmetic sequence $\endgroup$
    – Amira
    Feb 2 at 5:01
  • 2
    $\begingroup$ So both armies are always on the same tile? $\endgroup$
    – Florian F
    Feb 2 at 9:13
  • $\begingroup$ Are we assuming the army sizes are large enough that we can use any arbitrary fraction (eg, if player A spends half their troops winning the first battle, then player B spends half their troops winning the second, are we in an equivalent state to the starting condition?) $\endgroup$
    – StephenTG
    Feb 2 at 16:11
  • 1
    $\begingroup$ Is this a problem you devised yourself, or did you find it somewhere else? $\endgroup$
    – hexomino
    Feb 2 at 16:31

2 Answers 2

3
$\begingroup$

Rough outline of solution:

Below is a table for the target ratio of (B's surviving troops)/(A's surviving troops) which B should attempt to have at each tile:
1: 0
2: sqrt(2)-1
3: sqrt(2)/2
4: 1
5: sqrt(2)
6: sqrt(2) + 1
7: infinity

So e.g. if the round ends with the armies on tile 5 and B has at least sqrt(2) times as much army as A, then B is in good shape.

Below is a table of the proportion of B's troops that B should deploy for a round starting on a given tile to achieve this target:
1: N/A (game already over)
2: 1
3: sqrt(2) - 1
4: 1 - sqrt(2)/2
5: 1 - sqrt(2)/2
6: sqrt(2) - 1
7: N/A (game already over)

Because A always loses draws, A will have to deploy slightly more troops than B to avoid losing quickly. This will cause A's army to be ground down over time, resulting in victory for B. (Note that all this assumes that any proportion of an army can be deployed, not just proportions which can be written as a fraction i.e. a ratio of two integers.)

$\endgroup$
2
  • $\begingroup$ thanks! Does it mean at the start of the game (at tile 4) if Player A plays '1 - sqrt(2)/2' and Player B somehow does not play '1 - sqrt(2)/2', then Player A is guaranteed to at least a tie? $\endgroup$
    – Amira
    Feb 4 at 19:19
  • $\begingroup$ If B deployed more than 1-sqrt(2)/2 troops then B has fallen behind and A can force a win by continuing to use the strategy that B should have been using. If B deployed less than that many troops then A has won the battle at a "fair" cost but B's tiebreaking advantage is still in play so B can force a win by playing optimally going forwards. $\endgroup$
    – fblundun
    Feb 5 at 10:50
2
$\begingroup$

In a simplified version with 5 tiles, I found a way for B to win every time if they start with 20 soldiers each.

Here's the strategy for B on board 1,2,3,4,5, with m|n meaning m soldiers left for A and n soldiers left for B.

We start 20|20 on tile 3, B plays 10 soldiers. If B wins then we're 20|10 on tile 2, and if B loses then the worst case scenario for B is 9|20 on tile 4.

20|10 on tile 2, B plays 10 resulting in either a win for B, or 9|10 on tile 3. 9|20 on tile 4, B plays 10 resulting in 9|10 on tile 3.

9|10 on tile 3, B plays 4. If B wins this then it's 9|6 on tile 2, then playing 6 it's a win or 2|6 on 3; but then B plays 2 every time and wins. If B loses in the worst way, then it's 4|10 on tile 4.

4|10 on tile 4, B plays 4 resulting in 4|6 on tile 3, B plays 2. If B wins then it's 4|4 on tile 2, and B can play 4 and win. If B loses in the worst way, then it's 1|6 on tile 4, in which case B can win by playing 1 for the rest of the game.

I think this should help generalize to 7 tiles. It seems like if they start with enough soldiers, B can chip away slowly a soldier here and there which turns into a big percentage advantage as the armies get small. The chipping away may stick to one side of the board, like tiles 2,3,2,3,2,3,... or 5,6,5,6,5,6,...

$\endgroup$
1
  • 1
    $\begingroup$ Sorry, I forgot to mention fractional soldiers is possible, so can assume all start with just 1 soldier. $\endgroup$
    – Amira
    Feb 4 at 7:49

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.