2
$\begingroup$

Consider the following game (see also this question):

One day a castle is attacked at sunrise (by surprise) by n soldiers.

Each soldier carries a canon and a rifle.

The castle has strength s.

On the first day each soldier shoots his canon at the castle costing the castle n strength points (i.e. the castle ends the first day with s=s-n strength points). After all the soldiers have fired, the castle sends dpw defenders to battle them.

In the ensuing days the castle and the soldiers battle it out following these rules:

  1. All the soldiers fire first. A soldier can fire his canon at the castle or his rifle at one of the defenders (but not both and each soldier can only shoot once). One shot at a defender kills him. One shot at the castle decreases its strength by 1.
  2. Then each of the d defenders shoots at one soldier (and only one) killing him.

  3. If the castle still has strength points (i.e. s>0) it sends a new batch of dpw defenders at this point. The total number of defenders in the next round will be d=d+dpw.

  4. Repeat 1 through 3 on each new day.

  5. If all soldiers are killed by the defenders, the castle wins.

  6. If there are zero defenders after the soldiers shoot and the castle strength is zero, the soldiers win.

The answer to this question gives the strategy the soldiers should follow to win in a minimum number of rounds.

If $$n\leq s<2n, dpw\geq n, 2n<dpw+s<(\phi+1)n$$, the strategy that leads to a victory for the soldiers in the minimum number of rounds consists of the soldiers shooting only at the castle in the first and second days and destroying it, and from then on, the soldiers trade fire with the remaining defenders winning in a total of $2+\max(k,0)$ days, where $$k=\left\lceil\frac{\log_\phi{\left(\frac{n+(dpw+s-2n)\phi^{-1}}{n-(dpw+s-2n)\phi}\right)}}{4}\right\rceil.$$

If $dpw<n$, the soldiers can win in a minimum of $c+\max(k,0)$ days, where $$c = \left\lceil\frac{\sqrt{dpw^2+4 n\cdot dpw}-dpw+2 n-2 s}{2 (dpw-n)}\right\rceil$$ and $$k = \left\lceil\frac{\log_\phi{\left(\frac{n+(s + c\cdot dpw-(c+1)n)\phi^{-1}}{n-(s + c\cdot dpw-(c+1)n)\phi}\right)}}{4}\right\rceil.$$ In this case they shoot, in each round, at the defenders first then the castle for $c$ days which is the time it takes to destroy the castle.

What is an algorithm to find systematically all the strategies that lead to a win by the soldiers not just the minimum day strategy?

For example if $n=10, s=12, dpw=10$, there are 2 solutions in which the soldiers win: The first where the number of soldiers, defenders and castle strength goes like this (in 3 rounds)

start: 'soldiers': 10, 'defenders': 0, 'castle-strength': 12

round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 2

round2:'soldiers': 8, 'defenders': 2, 'castle-strength': 0

round3:'soldiers': 8, 'defenders': 0, 'castle-strength': 0

and the second solution where it goes like this (4 rounds)

start: 'soldiers': 10, 'defenders': 0, 'castle-strength': 12

round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 2

round2:'soldiers': 9, 'defenders': 11, 'castle-strength': 1

round3:'soldiers': 6, 'defenders': 3, 'castle-strength': 0

round4:'soldiers': 6, 'defenders': 0, 'castle-strength': 0

(in the particular case where $dpw=n$, like in the example above, there is an infinite number of solutions as @rotia points out, where the 10 soldiers eliminate the 10 defenders in either the 3rd or 4th or 5th... round before destroying the castle)

$\endgroup$
  • $\begingroup$ I´m very bad at these problems but i think there is an error in the equation $n\leq s<2n, dpw\geq n$ . If $s$ is bigger than $n$ and $dpw$ is much bigger than $n$ then the defenders always win. $\endgroup$ – rotia Jun 26 '16 at 14:57
  • $\begingroup$ You are right there are solutions in which the soldiers win only in a narrow range, I updated the question. $\endgroup$ – user35202 Jun 26 '16 at 15:23
  • 2
    $\begingroup$ Ok, thanks. The problem is that there can be an infinite number of solutions in certain cases. For instance if $n$ and $dpw$ are equal and $s$ is bigger than $n$ but equal to $n+2$, the player can win but he decides when he wants to win. He has no pressure. For instance if $s$ is $11$ $n$ is $9$ and $dpw$ is $9$ too. In the first round the player attacks the castle. But after that, the player can destroy the castle and attack the reinforcements to win in the next round, or he can attack the reinforcements. The player can kill all reinforcements and the castle calls more, it can last forever. $\endgroup$ – rotia Jun 26 '16 at 16:07
  • $\begingroup$ That is a good example I had missed. I assume these pathological/singular cases only happen if $dpw=n$. $\endgroup$ – user35202 Jun 26 '16 at 18:07
1
$\begingroup$

In the case $n\leq s<2n,dpw\geq n, 2n<dpw+s<(\phi+1)n$, a possible way of finding all soldiers wins is following this approach:

  1. Have the soldiers attack only the castle in the first 2 days, then once destroyed attack the defenders on the subsequent days. This gives you the minimum number of days solution.

  2. Have the soldiers attack the castle on the first day, then have $n-1$ of the soldiers attack the castle on the second day and $1$ of the soldiers attack the defenders on that second day. Finally destroy the castle on the third day and let the soldiers battle it out in the remainder of the days. This gives you the minimum number of days solution+1 (if there is one).

  3. Have the soldiers attack the castle on the first day, then have $n-2$ of the soldiers attack the castle on the second day and $2$ of the soldiers attack the defenders on that second day. On the third day, the remaining soldiers but 1 attack the castle and the rest attack the defenders. Finally on the fourth day the remaining soldiers destroy the castle and let the soldiers battle it out in the remainder of the days. This gives you the minimum number of days solution+2 (if there is one).

  4. etc

  5. The basic idea of this approach is to consider the cases where the castle is destroyed on day 2, on day 3, on day 4, etc

For this to work well it would be useful to know not just the minimum number of days it takes for the soldiers to win but also the maximum number of days it takes. It might be possible to find this mathematically.

Also note that there are cases like this

solution 1 (3 rounds)

start:'soldiers': 10, 'defenders': 0, 'castle-strength': 14

round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 4

round2:'soldiers': 6, 'defenders': 4, 'castle-strength': 0

round3:'soldiers': 6, 'defenders': 0, 'castle-strength': 0

solution 2 (5 rounds)

start:'soldiers': 10, 'defenders': 0, 'castle-strength': 14

round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 4

round2:'soldiers': 9, 'defenders': 11, 'castle-strength': 3

round3:'soldiers': 4, 'defenders': 5, 'castle-strength': 0

round4:'soldiers': 3, 'defenders': 1, 'castle-strength': 0

round5:'soldiers': 3, 'defenders': 0, 'castle-strength': 0

i.e. there might be gaps (there is no solution in 4 rounds)

$\endgroup$

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.