A recap
In the previous two posts we looked at two different ways of solving the following problem: A group of \(n\) soldiers, each carrying a canon and a rifle, attacks a castle which has initial strength \(s\). If \(s>0\) at the end of a bloody day, the castle can send \(dpw\) defenders a day out of its gates to battle the soldiers. On the the first day, all soldiers fire their canons at the castle decreasing its strength to \(s-n\). In the ensuing days the castle and the soldiers battle it out following these rules:- All the soldiers fire first. A soldier can either 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.
- Each of the defenders will then shoot one soldier (and only one) killing him.
- If the castle still has strength points (i.e. \(s>0\)) it will send a new batch of defendersPerWave (dpw) defenders at this point. The total number of defenders in the next round (day) will then be \(defenders=defenders + defendersPerWave\).
- Repeat 1 through 3 each new day.
- If all soldiers are killed by the defenders, the castle wins even if its strength is zero.
- If there are zero defenders left after the soldiers shot and the castle strength is also zero, the soldiers win.
In the first post of this series we described two simple strategies in which the soldiers, in each wave, either decided to attack the castle first and only then its defenders or vice versa, i.e. attack the defenders first and only then the castle. Neither of these approaches was able to find the minimum number of days solution for every set of initial values of \(s\), \(n\) and \(dpw\).
In the second post we described a recursive brute force search algorithm that correctly finds the minimum number of days for the soldiers to win and the exact steps-the path from the initial state towards the end goal- that the soldiers should take to win the battle in that minimum number of days. The algorithm is also used to find all possible solutions not just those that lead to a win by the soldiers in a minimum number of days but also solutions in which the castle wins and solutions in which the soldiers win in a non minimum number of days.
In this post we will do a careful mathematical study of the problem and use its peculiar structure to determine, given the number of initial soldiers \(n\), the number of initial castle hits/strength \(s\) and the number of defenders per wave \(dpw\),
1) Whether the soldiers can win and, if they can, what is the minimum number of days it takes for them to do so and what is the strategy the soldiers should use to accomplish it. We will be able to give a complete answer to this.
2) If the soldiers can not win, what is the minimum number of days for the castle to win and which strategy should the castle follow to achieve this. This is harder than 1) but we will go over some cases.
3) Finally is there a simple way to find all the paths that lead to a win by either side? Unfortunately it is too difficult to find these without an exhaustive search.
This post is fairly advanced mathematically and it is perhaps the hardest of this blog's posts so far. The result of all this hardship is a deeper insight into the problem as well as a quicker way to solve it. In particular we will see that the analysis will give the best strategy the soldiers should follow and therefore will tell us the path from the initial state to the goal state without the need to do a computationally expensive search like we did in our second post .
1) Whether the soldiers can win and, if they can, what is the minimum number of days it takes for them to do so and what is the strategy the soldiers should use to accomplish it. We will be able to give a complete answer to this.
2) If the soldiers can not win, what is the minimum number of days for the castle to win and which strategy should the castle follow to achieve this. This is harder than 1) but we will go over some cases.
3) Finally is there a simple way to find all the paths that lead to a win by either side? Unfortunately it is too difficult to find these without an exhaustive search.
This post is fairly advanced mathematically and it is perhaps the hardest of this blog's posts so far. The result of all this hardship is a deeper insight into the problem as well as a quicker way to solve it. In particular we will see that the analysis will give the best strategy the soldiers should follow and therefore will tell us the path from the initial state to the goal state without the need to do a computationally expensive search like we did in our second post .
1. The case \(s\leq n\) : The castle can not win
If the number of soldiers \(n\) is greater or equal to the castle strength \(s\), then the soldiers clearly win in one day (in the first day right after they discharge their canons on the castle).
2. The case \(s > n\): When can the soldiers win?
In the opposite case where the number of initial soldiers is smaller than the initial castle strength, there will always be (bad) soldier strategies that lead to the castle winning.
In some cases however even if they follow the best strategy, the soldiers can not win. In this section we would like to determine for what initial values of \(n,s,dpw\) can the soldiers win and the minimum number of days it will take for them to achieve the win.
Lets introduce some notation: For a given day i, let \(c_{i}\) be the remaining castle strength, \(s_{i}\) be the remaining number of soldiers and \(d_{i}\) the remaining number of castle defenders. Let \(dpw\) be the number of defenders the castle sends each new day/wave.
2.a Best strategy if \(dpw<n\): Kill all defenders every day
Consider first the case where \(d_{i}=dpw\) at the start of a given day, i.e. the soldiers killed all defenders the previous day.
Suppose that on this day the soldiers kill some defenders, leaving \(x\) of them at the end of the day (i.e. \(dpw-x\) of the soldiers killed \(dpw-x\) defenders, the remaining \(s_{i}-(dpw-x)\) soldiers shot at the castle and the \(x\) defenders shot back at the soldiers leaving \(s_{i}-x\) of them standing), and the castle is left standing (i.e. \(c_{i}>0\)). Then the start of the new day (\(i+1\)) begins with the following numbers
\begin{align}
s_{i+1} &= s_{i}-x\tag{1}\label{ref1}\\ \\
d_{i+1}& = dpw+x\tag{2}\label{ref2}\\ \\
c_{i+1}&=c_{i}-[s_{i}-(d_{i}-x)]=c_{i}-[s_{i}-(dpw-x)]=(c_{i}+dpw)-(s_{i}+x)
\tag{3}\label{ref3}
\end{align}
Clearly on day \(i+1\) there are more defenders and less soldiers than on day \(i\).
Lets suppose that the soldiers on day \(i+1\) decide to kill all \(d_{i+1}\) defenders again. This means that the remaining \(s_{i+1}-d_{i+1}\) soldiers attack the castle. We still assume that \(c_{i+1}>0\).
Then at the start of the next day we will be left with
\begin{align}
s_{i+2}& = s_{i+1}=s_{i}-x\\ \\
d_{i+2}& = dpw\\ \\
c_{i+2}&=c_{i+1}-(s_{i+1}-d_{i+1})=c_{i}+dpw-s_{i}-x-s_{i}+x+dpw+x=c_{i}+2dpw + x-2s_{i}\tag{4}\label{ref4}
\end{align}
where we replaced the quantities on day \(i+1\) with \ref{ref1},\ref{ref2},\ref{ref3}.
If however the soldiers killed all defenders every single day (i.e. \(x=0\)), we would have on day \(i+2\)
\begin{align}
s_{i+2}& = s_{i+1}=s_{i}\\ \\
d_{i+2}&= dpw \\ \\
c_{i+2}&=c_{i}+2dpw -2s_{i}\tag{5}\label{ref5}
\end{align}
i.e. the castle would end up with less strength points (since \(c_{i+2}\) in \ref{ref5} is smaller than \(c_{i+2}\) in \ref{ref4}).
From this analysis we see that the castle strength is smaller on day \(i+2\) if the soldiers kill all defenders every single day instead of leaving some alive and firing a few extra shots at the castle.
Therefore the soldiers, if they can, should never leave defenders and the castle alive on the same day. It is possible that \(c_{i+2}=c_{i}+2dpw + x-2s_{i}<0\), i.e. the soldiers finish the castle on day \(i+1\) while leaving \(x\) defenders alive. But they could also have been done with the castle on day \(i+1\) or earlier if they kept killing all defenders (since if \(c_{i}+2dpw + x-2s_{i}<0\) obviously \(c_{i}+2dpw-2s_{i}<0\) ) and they would have the added bonus of not having lost any soldier. So while it is not always completely disadvantageous to leave some defenders alive, it is never advantageous since the soldiers can finish always in the same number of days and with all the soldiers alive by always killing all the defenders.
s_{i+1} &= s_{i}-x\tag{1}\label{ref1}\\ \\
d_{i+1}& = dpw+x\tag{2}\label{ref2}\\ \\
c_{i+1}&=c_{i}-[s_{i}-(d_{i}-x)]=c_{i}-[s_{i}-(dpw-x)]=(c_{i}+dpw)-(s_{i}+x)
\tag{3}\label{ref3}
\end{align}
Clearly on day \(i+1\) there are more defenders and less soldiers than on day \(i\).
Lets suppose that the soldiers on day \(i+1\) decide to kill all \(d_{i+1}\) defenders again. This means that the remaining \(s_{i+1}-d_{i+1}\) soldiers attack the castle. We still assume that \(c_{i+1}>0\).
Then at the start of the next day we will be left with
\begin{align}
s_{i+2}& = s_{i+1}=s_{i}-x\\ \\
d_{i+2}& = dpw\\ \\
c_{i+2}&=c_{i+1}-(s_{i+1}-d_{i+1})=c_{i}+dpw-s_{i}-x-s_{i}+x+dpw+x=c_{i}+2dpw + x-2s_{i}\tag{4}\label{ref4}
\end{align}
where we replaced the quantities on day \(i+1\) with \ref{ref1},\ref{ref2},\ref{ref3}.
If however the soldiers killed all defenders every single day (i.e. \(x=0\)), we would have on day \(i+2\)
\begin{align}
s_{i+2}& = s_{i+1}=s_{i}\\ \\
d_{i+2}&= dpw \\ \\
c_{i+2}&=c_{i}+2dpw -2s_{i}\tag{5}\label{ref5}
\end{align}
i.e. the castle would end up with less strength points (since \(c_{i+2}\) in \ref{ref5} is smaller than \(c_{i+2}\) in \ref{ref4}).
From this analysis we see that the castle strength is smaller on day \(i+2\) if the soldiers kill all defenders every single day instead of leaving some alive and firing a few extra shots at the castle.
Therefore the soldiers, if they can, should never leave defenders and the castle alive on the same day. It is possible that \(c_{i+2}=c_{i}+2dpw + x-2s_{i}<0\), i.e. the soldiers finish the castle on day \(i+1\) while leaving \(x\) defenders alive. But they could also have been done with the castle on day \(i+1\) or earlier if they kept killing all defenders (since if \(c_{i}+2dpw + x-2s_{i}<0\) obviously \(c_{i}+2dpw-2s_{i}<0\) ) and they would have the added bonus of not having lost any soldier. So while it is not always completely disadvantageous to leave some defenders alive, it is never advantageous since the soldiers can finish always in the same number of days and with all the soldiers alive by always killing all the defenders.
Given this optimal strategy, how many days does it take for the soldiers to win? It is convenient to break this question into two: 1) In which day should the castle be destroyed, i.e. how many days should it take to bring the castle down and 2) How many days after the castle has been destroyed it takes for the soldiers to kill all defenders. It turns out that to answer 1) we must first answer 2).
Number of days to kill all defenders (after the castle has been destroyed)
Lets suppose the castle is destroyed on day \(q\). Since up to day \(q\) the soldiers have been killing all defenders every day, all the soldiers are still alive. Let \(n\) be the number of initial soldiers (i.e. \(s_{1}=n\)). At the start of day \(q\), \(c_{q}\) of the \(n\) soldiers shoot at the castle destroying it. The remaining \(n-c_{q}\) soldiers fire then at the \(dpw\) defenders leaving
\begin{equation}
x=dpw-(n-c_{q})=c_{q}+dpw-n
\end{equation}
of the defenders standing.
Afterwards the number of soldiers and defenders in the days after the castle was destroyed \(q+1, q+2, q+3, ...\), changes like this
\begin{align}
d_{q+1}&=x\\ \\
s_{q+1}&=n-x\\ \\
d_{q+2}&=d_{q+1}-s_{q+1}=2x-n\\ \\
s_{q+2}&=s_{q+1}-d_{q+2}=n-x-2x+n=2n-3x\\ \\
d_{q+3}&=d_{q+2}-s_{q+2}=2x-n-2n+3x=5x-3n\\ \\
s_{q+3}&=s_{q+2}-d_{q+3}=2n-3x-5x+3n=5n-8x
\end{align}
More generally we can write
\begin{align}
d_{q+i+1}&=xFib(2i+1)-nFib(2i)\tag{def}\label{def}\\ \\
s_{q+i+1}&=nFib(2i+1)-xFib(2i+2)\tag{sold}\label{sold}
\end{align}
where \(Fib\) is the Fibonacci sequence of numbers (see for example Wikipedia).
It turns out that the Fibonacci \(p\) term can be written in closed form as
\begin{align}
Fib(p) &=\frac{\phi^{p}-(-\phi)^{-p}}{\sqrt{5}}\\ \\
\phi &=\frac{1+\sqrt{5}}{2}
\end{align}
where \(\phi\) is the golden ratio (see for example Wolfram Mathworld).
It follows that the number of defenders reaches zero, \(d_{q+i+1}=0\) for \(i=k\) such that
\begin{align}
xFib(2k+1)-nFib(2k)=\frac{x(\phi^{2k+1}-(-\phi)^{-2k-1})-n(\phi^{2k}-(-\phi)^{-2k})}{\sqrt{5}}=0
\end{align}
Because any negative number raised to an even power like \(2k\) is a positive number, this can be rewritten as
\begin{align}
(x\phi-n)\phi^{2k}+(x\phi^{-1}+n)\phi^{-2k}&=0
\end{align}
or
\begin{align}
\phi^{4k}(n-x\phi)&=(n+x\phi^{-1})
\end{align}
Taking the logarithm in the base \(\phi\) of both sides then leads to
\begin{align}
\log_{\phi}\phi^{4k}(n-x\phi)&= 4k+\log_{\phi}(n-x\phi)=\log_{\phi}(n+x\phi^{-1})
\end{align}
solving for \(k\) gives,
\begin{align}
k&=\left\lceil\frac{\log_{\phi}\frac{n+x\phi^{-1}}{n-x\phi}}{4}\right\rceil\tag{6}\label{ref6}\\ \\
x\equiv x_{q}&=dpw-(n-c_{q})=c_{q}+dpw-n\tag{7}\label{ref7}\\ \\
\phi &=\frac{1+\sqrt{5}}{2}
\end{align}
The ceiling in the above expression takes into account that depending on the values of \(x,n\) there might not be an integer value of \(k\) for which the number of defenders is zero, i.e. the defenders might be zero for a decimal value of \(k\). We should therefore round up to the nearest integer that decimal value, since we are interested in finding out the day \(k\) in which the number of defenders becomes zero or negative, i.e. the soldiers will win on the day \(k\) after \(q\) in which \(d_{q+k}<=s_{q+k}\).
Note that to find \(k,x\) we need to know \(c_{q}\) which is the castle strength at the beginning of the day the castle was destroyed. To find it we next turn to finding \(q\), the number of days to destroy the castle.
\begin{equation}
x=dpw-(n-c_{q})=c_{q}+dpw-n
\end{equation}
of the defenders standing.
Afterwards the number of soldiers and defenders in the days after the castle was destroyed \(q+1, q+2, q+3, ...\), changes like this
\begin{align}
d_{q+1}&=x\\ \\
s_{q+1}&=n-x\\ \\
d_{q+2}&=d_{q+1}-s_{q+1}=2x-n\\ \\
s_{q+2}&=s_{q+1}-d_{q+2}=n-x-2x+n=2n-3x\\ \\
d_{q+3}&=d_{q+2}-s_{q+2}=2x-n-2n+3x=5x-3n\\ \\
s_{q+3}&=s_{q+2}-d_{q+3}=2n-3x-5x+3n=5n-8x
\end{align}
More generally we can write
\begin{align}
d_{q+i+1}&=xFib(2i+1)-nFib(2i)\tag{def}\label{def}\\ \\
s_{q+i+1}&=nFib(2i+1)-xFib(2i+2)\tag{sold}\label{sold}
\end{align}
where \(Fib\) is the Fibonacci sequence of numbers (see for example Wikipedia).
It turns out that the Fibonacci \(p\) term can be written in closed form as
\begin{align}
Fib(p) &=\frac{\phi^{p}-(-\phi)^{-p}}{\sqrt{5}}\\ \\
\phi &=\frac{1+\sqrt{5}}{2}
\end{align}
where \(\phi\) is the golden ratio (see for example Wolfram Mathworld).
It follows that the number of defenders reaches zero, \(d_{q+i+1}=0\) for \(i=k\) such that
\begin{align}
xFib(2k+1)-nFib(2k)=\frac{x(\phi^{2k+1}-(-\phi)^{-2k-1})-n(\phi^{2k}-(-\phi)^{-2k})}{\sqrt{5}}=0
\end{align}
Because any negative number raised to an even power like \(2k\) is a positive number, this can be rewritten as
\begin{align}
(x\phi-n)\phi^{2k}+(x\phi^{-1}+n)\phi^{-2k}&=0
\end{align}
or
\begin{align}
\phi^{4k}(n-x\phi)&=(n+x\phi^{-1})
\end{align}
Taking the logarithm in the base \(\phi\) of both sides then leads to
\begin{align}
\log_{\phi}\phi^{4k}(n-x\phi)&= 4k+\log_{\phi}(n-x\phi)=\log_{\phi}(n+x\phi^{-1})
\end{align}
solving for \(k\) gives,
\begin{align}
k&=\left\lceil\frac{\log_{\phi}\frac{n+x\phi^{-1}}{n-x\phi}}{4}\right\rceil\tag{6}\label{ref6}\\ \\
x\equiv x_{q}&=dpw-(n-c_{q})=c_{q}+dpw-n\tag{7}\label{ref7}\\ \\
\phi &=\frac{1+\sqrt{5}}{2}
\end{align}
The ceiling in the above expression takes into account that depending on the values of \(x,n\) there might not be an integer value of \(k\) for which the number of defenders is zero, i.e. the defenders might be zero for a decimal value of \(k\). We should therefore round up to the nearest integer that decimal value, since we are interested in finding out the day \(k\) in which the number of defenders becomes zero or negative, i.e. the soldiers will win on the day \(k\) after \(q\) in which \(d_{q+k}<=s_{q+k}\).
Note that to find \(k,x\) we need to know \(c_{q}\) which is the castle strength at the beginning of the day the castle was destroyed. To find it we next turn to finding \(q\), the number of days to destroy the castle.
Number of days to destroy the castle
Following the optimal strategy, the soldiers decrease the castle strength to \(s-n\) on the first day and every day (after the first), \(dpw\) of the soldiers kill \(dpw\) defenders and the remainder \(n-dpw\) soldiers decrease the castle strength by \(n-dpw\). The number of soldiers remains \(n\). That means that at the beginning of the day \(q\) in which the soldiers destroy the castle, the soldiers, castle strength and the remaining defenders are
\begin{align}s_{q}&=n\\ \\
c_{q}&= s-n-(q-1)(n-dpw)=s-nq+(q-1)dpw\\ \\
d_{q}&=x_{q}=dpw-(n-c_{q})=dpw-n+c_{q}=s+qdpw-(q+1)n\tag{8}\label{ref8}
\end{align}
The question for the soldiers is: should they attack the castle on day \(q\) or should they wait?
They should wait another day if the number of days to destroy the \(x\) remaining soldiers given by \ref{ref7} starting on day \(q+1\) plus one day is smaller than the number of days to destroy the \(x\) remaining soldiers given by \ref{ref7} starting on day \(q\) or in other words (using \ref{ref6})
\begin{align}
\frac{\log_{\phi}\frac{n+x_{q+1}\phi^{-1}}{n-x_{q+1}\phi}}{4}+1<\frac{\log_{\phi}\frac{n+x_{q}\phi^{-1}}{n-x_{q}\phi}}{4}
\end{align}
We can rewrite this as
\begin{align}
\log_{\phi}\frac{n+x_{q}\phi^{-1}}{n-x_{q}\phi}-\log_{\phi}\frac{n+x_{q+1}\phi^{-1}}{n-x_{q+1}\phi}>4
\end{align}
or combining the subtraction in the \(log\) and then removing the \(log\)
\begin{align}
\frac{n+x_{q}\phi^{-1}}{n-x_{q}\phi}\frac{n-x_{q+1}\phi}{n+x_{q+1}\phi^{-1}}>\phi^{4}
\end{align}cross multiplying leads to
\begin{align}
n^{2}-nx_{q+1}\phi+nx_{q}\phi^{-1}-x_{q}x_{q+1}>\phi^{4}[n^{2}+nx_{q+1}\phi^{-1}-nx_{q}\phi-x_{q}x_{q+1}]
\end{align}
rearranging and taking into account that
\begin{align}
\phi^{4} &=\frac{7+3\sqrt{5}}{2}=3\phi+2\\ \\
\end{align}
we arrive at
\begin{align}
(3\phi+1)n^{2}+(3+2\phi^{-1}+\phi)nx_{q+1}-(3\phi^{2}+2\phi+\phi^{-1})nx_{q}\phi-(3\phi+1)x_{q}x_{q+1}<0\tag{9}\label{ref9}
\end{align}
noticing that
\begin{align}
\phi^{-1}&=-\frac{1}{2}(1-\sqrt{5})\\ \\
\phi^{2}&=\frac{3+\sqrt{5}}{2}=\phi+1\\ \\
3+2\phi^{-1}+\phi&= 3\phi+1\\ \\
3\phi^{2}+2\phi+\phi^{-1}&=2(3\phi+1)
\end{align}
we can rewrite \ref{ref9} as
\begin{align}
(3\phi+1)[n^{2}+nx_{q+1}-2nx_{q}\phi-x_{q}x_{q+1}]<0
\end{align}
or
\begin{align}
n^{2}+nx_{q+1}-2nx_{q}\phi-x_{q}x_{q+1}<0\tag{10}\label{ref10}
\end{align}
we can see from \ref{ref7} or \ref{ref8} that
\begin{align}
x_{q+1}&=s+(q+1)dpw-(q+2)n=x_{q}+dpw-n\tag{11}\label{ref11}
\end{align}
so replacing this into \ref{ref10} we get
\begin{align}
x^{2}_{q}-ndpw+dpwx_{q}>0
\end{align}
solving this quadratic equation and keeping only the positive solution (since we are assuming \(x_{q}>0\)) we get
\begin{align}
x_{q}>\frac{-dpw+\sqrt{dpw^{2}+4ndpw}}{2}
\end{align}
replacing \(x_{q}\) with \ref{ref8} we get
\begin{align}
2s+2q(dpw-n)-2n>-dpw+\sqrt{dpw^{2}+4ndpw}
\end{align}
solving for \(q\)
\begin{align}
q=\left\lceil\frac{\sqrt{dpw^{2}+4ndpw}-dpw+2n-2s}{2(dpw-n)}\right\rceil\tag{12}\label{ref12}
\end{align}
This is the minimum number of days it takes for the soldiers to kill the castle.
We also point out that the optimal strategy followed by the soldiers of always killing all defenders each day and then attacking the castle is only possible if \(dpw<n\).
2.b The case \(n<s<2n, dpw\geq n, 2n<dpw+s<(\phi+1)n\)
On the second day, the soldiers have to split their fire on the castle and on the defenders. Otherwise if they just fire at the castle, they will be all killed by the end of the second day. They also have to kill enough defenders that they are not killed by the remaining defenders.
Lets write down the changes in the number of soldiers, defenders and castle hits as the days go by:
At the beginning of the 2nd day we have
\begin{align}
s_{2}&=n\\
d_{2}&=dpw\\
c_{2}&=s-n
\end{align}
Lets assume that the soldiers leave \(x_{2}\) defenders alive on the second day.
At the beginning of the 3rd day then
\begin{align}
s_{3}&=n-x_{2}\\
d_{3}&=dpw+x_{2}\\
c_{3}&=c_{2}-[n-(dpw-x_{2})]=s-2n+dpw-x_{2}=(s-2n)+dpw-x_{2}
\end{align}
Lets assume that the soldiers leave \(x_{3}\) defenders alive on the third day.
At the beginning of the 4th day then
\begin{align}
s_{4}&=n-x_{2}-x_{3}\\
d_{4}&=dpw+x_{3}\\
c_{4}&=c_{3}-[n-x_{2}-(dpw+x_{2}-x_{3})]=(s-2n)+(dpw-n)+dpw+x_{2}-x_{3}
\end{align}
Lets assume that the soldiers leave \(x_{4}\) defenders alive on the fourth day.
At the beginning of the 5th day then
\begin{align}
s_{5}&=n-x_{2}-x_{3}-x_{4}\\
d_{5}&=dpw+x_{4}\\
c_{5}&=c_{4}-[n-x_{2}-x_{3}-(dpw+x_{3}-x_{4})]=(s-2n)+ 2(dpw-n)+dpw + 2x_{2}+x_{3}-x_{4}\tag{13}\label{ref13}
\end{align}
A necessary condition for the soldiers to win is that on the last day of the battle, lets call it \(q\), the castle strength \(c_{q}=0\) but the number of soldiers \(s_{q}>0\).
If we follow the pattern in \ref{ref13} we have on the last day of the battle (\(x_{2}, x_{3},...,x_{q-1}\) is the number of defenders left alive by the soldiers on days 2,3,...,\(q-1\))
\begin{align}
s_{q}&=n-x_{2}-x_{3}-...-x_{q-1}\\
d_{q}&=dpw+x_{q-1}\\
c_{q}&=c_{q-1}-[n-x_{2}-x_{3}-...-x_{q-2}-(dpw+x_{q-2}-x_{q-1})]=(s-2n)+ (q-2)(dpw-n)+dpw+(q-3)x_{2}+(q-4)x_{3}+...-x_{q-1}
\end{align}
This result shows that if \(s\geq 2n, dpw\geq n\), \(c_{q}>0\), i.e. it is impossible for the soldiers to win because the castle strength can never become zero.
Therefore for the soldiers to have a chance the castle strength must be \(n\leq s<2n\).
Clearly the best strategy for the soldiers is not to only shoot at the defenders every day (as they should do if \(dpw<n\)). Since \(dpw\geq n\), if the soldiers only fire at the defenders and not at the castle, the castle will keep adding \(dpw\) defenders every round and it will win quickly.
The following table shows the values of \(x_{n-1},c_{n},d_{n},s_{n}\) if the castle is destroyed at the end of the 2nd, 3rd, 4th day. We simply set \(c_{3}=0\) above if the castle is destroyed on the second day, or \(c_{4}=0\) above if the castle is destroyed on the third day, etc.
Notice that because the castle is destroyed, it doesnt add \(dpw\) to the defenders on the day it is destroyed.
| Day castle killed | \(x_{n-1}\) | \(s_{n}\) | \(d_{n}\) |
|---|---|---|---|
| 2 (\(c_{3}=0\)) | \(x_{2}=(s-n)+(dpw-n)\) | \(s_{3}=n-x_{2}=n-(s-n)-(dpw-n)\) | \(d_{3}=x_{2}=(s-n)+(dpw-n)\) |
| 3 (\(c_{4}=0\)) | \(x_{3}=(s-n)+2(dpw-n)+x_{2}\) | \(s_{4}=n-x_{2}-x_{3}=n-(s-n)-2(dpw-n)\)-2x_{2} | \(d_{4}=x_{3}=(s-n)+2(dpw-n)+x_{2}\) |
| 4 (\(c_{5}=0\)) | \(x_{4}=(s-n)+3(dpw-n)+2x_{2}+x_{3}\) | \(s_{5}=n-x_{2}-x_{3}-x_{4}=n-(s-n)-3(dpw-n)-3x_{2}-2x_{3}\) | \(d_{5}=x_{4}=(s-n)+3(dpw-n)+2x_{2}+x_{3}\) |
Since \(s-n>0,dpw-n\geq 0, x_{2}\geq 0, x_{3}\geq 0\) it is obvious from this table that the number of soldiers on the day the castle is destroyed is largest and the number of defenders on that same day is the smallest if the castle is destroyed on the second day (i.e. \(s_{3} > s_{4} > s_{5}, d_{3} < d_{4} < d_{5}\)).
That means that the fastest way for the soldiers to win is by destroying the castle on the second day.
It is also clear from the table that:
- The higher \(s\) and \(dpw\) the smaller the number of soldiers and the higher the number of defenders on the day the castle is destroyed. This means that there is a narrow range of values of \(s\) and \(dpw\) for which the soldiers can win.
- The number of defenders and soldiers if the castle is destroyed on day 3 is dependent on \(x_{2}\) i.e. how many defenders where left alive by the soldiers on day 2. The higher \(x_{2}\) the higher the number of defenders on day 3 (i.e. the higher \(d_{4}\)) and the lower the number of soldiers (i.e. the lower \(s_{4}\)). Now notice that \(x_{2}\) is the highest when the castle is destroyed on day 2 because that is when most of the soldiers fire is directed towards the castle.
- \(x_{2}\) is the smallest when the soldiers shoot just at the defenders and not at all at the castle.
- The number of defenders if the castle is destroyed on day 4 is dependent on \(x_{2}, x_{3}\) i.e. how many defenders where left alive by the soldiers on day 2 and day 3. The higher \(x_{3}\) the higher the number of defenders on day 4 (i.e. the higher \(d_{5}\)). Now notice that \(x_{3}\) is the highest when the castle is destroyed on day 3 because that is when most of the soldiers fire is directed towards the castle.
- \(x_{3}\) is the smallest when the soldiers shoot just at the defenders and not at all at the castle.
It is quite tricky to find all possible solutions in which the soldiers win without an exhaustive search. For example if \(dpw=n\), there is always an infinite number of solutions in which the soldiers win: they can kill the castle on day 2, or day 3, or day 4 or day 5 or any day they want. How? For example if they want to destroy the castle on day 5 they kill the \(dpw=n\) defenders that the castle sent on days 2,3,4 and then on day 5 they destroy the castle. The same pattern can be repeated if the soldiers want to destroy the castle on any day.
Besides having to destroy the castle by the second day, the soldiers must be able to finish off the defenders. This can be accomplished in \(k\) days after the castle is destroyed with \(k\) given by \ref{ref6}. What is \(x\) in the expression \ref{ref6} for \(k\)? It is the number of defenders left at the end of the second day. We know that at the end of the first day the castle is down to \(s-n\) strength points and at the end of the second day \(s-n\) of the soldiers finish it of. The remaining \(n-(s-n)=2n-s\) then attack the \(dpw\) defenders leaving \(x=dpw-(2n-s)=dpw+s-2n\) defenders.
This agrees with the expression for \(x\) in \ref{ref7}.
From day 3 onward the soldiers and the defenders battle it out and their numbers change according with the logic above that led to \ref{ref7}. In particular the number of defenders and soldiers after \(2+i+1\) days is given by \ref{def} and \ref{sold}. The game progresses until the number of defenders is negative or zero while the number of soldiers is positive.
We already know that since \(dpw\geq n, n<s<2n\), that \(s+dpw>2n\) so obviously \(x=dpw+s-2n>0\). But \(x\) can not be arbitrarily large otherwise the defenders will overwhelm the soldiers and win the game. In other words we want the number of soldiers to be positive for all values of \(i\) in \ref{sold}. Since the soldiers number will be the smallest the larger the value of \(i\) this means we want the smallest possible value of the soldiers to still be positive. This happens when we take the limit \(i\rightarrow \infty\) i.e.
\begin{align}
n-x\lim_{i\to\infty}\frac{Fib(2i+2)}{Fib(2i+1)}>0
\end{align}
since \(\lim_{i \to \infty}Fib(2i+2)/Fib(2i+1)=\phi\) (see for example Wikipedia) this is the same as
\begin{align}
x\phi<n
\end{align}
or after replacing \(x=dpw+s-2n\)
\begin{align}
dpw+s<(2+\phi^{-1})n=(\phi+1)n
\end{align}
In other words the soldiers can win if \(dpw\geq n, n<s<2n\) only if \(2n<dpw+s<(\phi+1)n\) .
Recaping the ways the soldiers can win
It is time to summarize all the cases described in detail above.| Case | Condition | Soldiers minimum moves to win | Soldiers strategy |
|---|---|---|---|
| 1 | \(s\leq n \) | 1 | All soldiers fire their cannons at the castle. |
| 2a | \(s> n\) \( dpw < n\) |
\(q+max(0,k) days\) \begin{align} q&=\left\lceil \frac{\sqrt{dpw^{2}+4ndpw}-dpw+2n-2s}{{2(dpw-n)}}\right\rceil\\ \\ k&=\left\lceil\frac{\log_{\phi}\frac{n+(s+qdpw-(q+1)n)\phi^{-1}}{n-(s+qdpw-(q+1)n)\phi}}{4}\right\rceil\tag{14}\label{ref14}\\ \\ \end{align} |
Kill \(dpw\) defenders for the first \(q\) days until the castle strength vanishes. Afterwards just shoot at the defenders left and be done in \(k\) days. |
| 2b | \(n < s < 2n\) \( dpw \geq n\) \( 2n < dpw+s<(\phi+1)n\) |
\( 2 + max(0,k) days\) \begin{align} k&=\left\lceil\frac{\log_{\phi}\frac{n+(s+dpw-2n)\phi^{-1}}{n-(s+dpw-2n)\phi}}{4}\right\rceil\tag{15}\label{ref15}\\ \\ \end{align} |
Destroy the castle in two days and battle the defenders in the next \(k\) days. |
| 2c | \(n < s < 2n\) \( dpw \geq n\) \( 2n < dpw+s\geq(\phi+1)n\) |
Can not win | No winning strategy |
| 2d | \( s > 2n\) \(dpw\geq n\) |
Can not win | No winning strategy |
Minimum number of days for the castle to win
The general case is quite complicated and we will just describe a few cases.
If \(dpw+s\leq 2n, s>n,dpw<n\) the castle can not win. After the first day, \(dpw+castleStrength\leq n\) and since there are \(n\) soldiers and they attack first, the soldiers win on the second day.
If \(dpw+s> 2n, s>n, dpw<n\) the castle sometimes will not be able to win and when it can win it will need more than 2 days at a minimum to win because the number of defenders per day is not enough to kill the soldiers in one day (the maximum value of \(dpw=n-1\)).
At the end of the first day \(dpw+castleStrength>n, castleStrength=s-n\).
If \(dpw=n-1\) which is the maximum value of defenders to obey \(dpw<n\), the castle will take at least 3 days to win. It can win on the third day only if \(s>2n\) [the soldiers attack the castle only on the first two days leaving it with \(1\) strength point and leaving \(1\) soldier only standing. If that soldier then destroys the castle, it will be killed by the \(2n-2\) defenders on the third day.
If \(s=n+2, dpw=n-1, n>1\), the castle can not win. The soldiers on the first day reduce the castle strength to 2. On the second day the soldiers have two options: 1) they destroy the castle and kill \(n-2\) defenders leaving only one. That one kills a soldier and is then killed by the remaining soldiers on the third day. 2) If on the contrary the soldiers killed all defenders and 1 strength point, the third day would start with \(n-1\) defenders and the castle with \(1\) strength point, so the \(n\) soldiers would still win on the third day. If \(dpw<n-1\) the same arguments apply but to even less defenders. Besides \(s+dpw\leq 2n\). It follows that if \(s=n+2\) the castle can never win.
If \(s=n+3, dpw=n-1, n>2\), the castle can win under certain circumstances.
The soldiers on the first day reduce the castle strength to 3. They then have 3 options: 1) On the second day they destroy the castle and kill all but 2 defenders. These kill 2 soldiers leaving at least one. The third day starts with \(2\) defenders and at least one soldier. The castle wins on the third day only if there is one soldier (i.e. if \(n=3\)). If there are two or more soldiers, the castle can not win.
2) On the second day they leave the castle with 1 point and kill all but 1 defender which then kills 1 soldier. The third day starts with \(n-1\) soldiers, \(n\) defenders and 1 castle strength point. The castle can now always win if the soldiers always hit the defenders but not the castle. That way the castle keeps sending \(n-1\) defenders, while the soldiers decrease steadily. Following this approach the castle can only win on the third day if \(n=3\) [by destroying the castle and killing one defender, then the remaining two defenders kill the 2 soldiers] or on the fourth day if \(n=4\), etc.
3) On the second day they leave the castle with 2 points and kill all defenders. The third day starts with \(n-1\) defenders, \(n\) soldiers and 2 castle strength points. This is similar to what happens on the second day of the case \(s=n+2,dpw=n-1,n>1\) so we know there is no solution where the castle can win.
If \(s=n+3, dpw<n-1\) we have \(s+dpw\leq 2n+1\) which is the same case as \(s=n+2, dpw<n\) above and has no solutions.
2.c The case \(n\geq 2n, dpw\geq n, dpw+s\geq(\phi+1)n\)
Left as an exercise.
2.d The case \(s\geq 2n, dpw\geq n\)
If \(s\geq 2n, dpw\geq n\), the castle can always win in 2 days minimum if on both days the soldiers attack only the castle and never attack the defenders. The soldiers can not win but can delay the castle victory by attacking the castle and the defenders in the same wave.If \(dpw=n\) the soldiers can tie the game by always killing all defenders starting on day 2.
Lets recap all possibilities.
Recap
| Case | Condition | Soldiers minimum moves win | Castle minimum moves win |
|---|---|---|---|
| 1 | \(s\leq n\) | Win in one day | Can not win |
| 2a | \(s> n\) \( dpw < n\) |
\(q+max(0,k)\) days \begin{align} q&=\left\lceil \frac{\sqrt{dpw^{2}+4ndpw}-dpw+2n-2s}{2(dpw-n)}\right\rceil\\ \\ k&=\left\lceil\frac{\log_{\phi}\frac{n+(s+qdpw-(q+1)n)\phi^{-1}}{n-(s+qdpw-(q+1)n)\phi}}{4}\right\rceil\\ \\ \end{align} |
Win in two days if \(dpw+s > 3n\) Can not win if \(dpw+s\leq 3n\) |
| 2b | \(n < s < 2n\) \( dpw \geq n\) \( 2n < dpw+s<(\phi+1)n\) |
\( 2 + max(0,k) days\) \begin{align} k&=\left\lceil\frac{\log_{\phi}\frac{n+(s+dpw-2n)\phi^{-1}}{n-(s+dpw-2n)\phi}}{4}\right\rceil\\ \\ \end{align} |
Left as an exercise |
| 2c | \(n < s < 2n\) \( dpw \geq n\) \( 2n < dpw+s\geq(\phi+1)n\) |
Can not win | Left as an exercise |
| 2d | \( s > 2n\) \(dpw\geq n\) |
Can not win | Win in 2 days (soldiers attack the castle only) |
- If \(s\geq 2n, dpw\geq n\), the castle can always win in 2 days minimum (if the soldiers attack the castle and not the defenders). The soldiers can not win but can delay the castle victory by attacking the castle and the defenders in the same wave.
- If \(n<s<2n, dpw\geq n, (\phi+1)n<dpw+s\), the soldiers can not win but the castle might take more than 2 days to win at a minimum. Consider the following example
\(n=3819, s=5000, dpw=5000\)
The soldiers can not win. The castle can win in 3 rounds (but not in 2):At the end of the first day, the castle is down to 1181. If the soldiers on day 2 instead of destroying the castle kill 3819 defenders, the remaining 1181 defenders would fire back and leave 2638 soldiers at the start of day 3 with 6181 defenders. If all the soldiers then attacked the castle on day 3, the soldiers would be all killed and would lose on day 3.
On the other hand if we start with one extra soldier
\(n=3820, s=5000, dpw=5000\)
This falls into the second case above, since \(dpw+s=10000<(\phi+1)3820\). The soldiers can win in
\(2+k\) days where
\begin{align}
k&=\left\lceil\frac{\log_{\phi}\frac{3820+(10000-2\times 3820)\phi^{-1}}{3820-(10000-2\times 3820)\phi}}{4}\right\rceil=\left\lceil\frac{\log_{\phi}\frac{3820+2360\phi^{-1}}{3820-2360\phi}}{4}\right\rceil=5
\end{align}
I.e the soldiers can win in 7 waves:
At the end of the first day the castle strength is down to 1180, and there are 5000 defenders.
At the end of the second day, the castle is gone and 5000- 2640=2360 defenders remain. They then kill that many soldiers leaving 1460 soldiers.
At the end of the third day, there are 2360-1460=900 defenders and 1460-900=560 soldiers.
At the end of the fourth day, there are 900-560=340 defenders and 560-340=220 soldiers.
At the end of the fifth day, there are 340-220=120 defenders and 220-120=100 soldiers.
At the end of the sixth day there are 120-100=20 defenders and 100-20=80 soldiers.
At the end of the seventh day the soldiers win.
The castle can still win in 3 waves minimum if the soldiers attack the castle on the first day, attack the defenders on the second and attack the castle on the third day.
Notice that if the number of soldiers were \(n=3819\) and the soldiers followed the same strategy, we would have
End of first day: castle strength=1181 and 5000 defenders.
End of second day: castle strength=0, 5000-2638=2362 defenders, 3819-2362=1457 soldiers.
End of third day: 2362-1457=905 defenders and 1457-905=552 soldiers
End of fourth day: 905-552=353 defenders and 552-353=199 soldiers
End of fifth day: 353-199=154 defenders and 199-154=45 soldiers
End of sixth day: 154-45=109 defenders and all soldiers are dead.
The castle wins in six rounds. The soldiers can not win. What a difference a single soldier makes!
At the end of the first day the castle strength is down to 1180, and there are 5000 defenders.
At the end of the second day, the castle is gone and 5000- 2640=2360 defenders remain. They then kill that many soldiers leaving 1460 soldiers.
At the end of the third day, there are 2360-1460=900 defenders and 1460-900=560 soldiers.
At the end of the fourth day, there are 900-560=340 defenders and 560-340=220 soldiers.
At the end of the fifth day, there are 340-220=120 defenders and 220-120=100 soldiers.
At the end of the sixth day there are 120-100=20 defenders and 100-20=80 soldiers.
At the end of the seventh day the soldiers win.
The castle can still win in 3 waves minimum if the soldiers attack the castle on the first day, attack the defenders on the second and attack the castle on the third day.
Notice that if the number of soldiers were \(n=3819\) and the soldiers followed the same strategy, we would have
End of first day: castle strength=1181 and 5000 defenders.
End of second day: castle strength=0, 5000-2638=2362 defenders, 3819-2362=1457 soldiers.
End of third day: 2362-1457=905 defenders and 1457-905=552 soldiers
End of fourth day: 905-552=353 defenders and 552-353=199 soldiers
End of fifth day: 353-199=154 defenders and 199-154=45 soldiers
End of sixth day: 154-45=109 defenders and all soldiers are dead.
The castle wins in six rounds. The soldiers can not win. What a difference a single soldier makes!
Code Implementation
Using the mathematical logic above it is straightforward to write code that finds the minimum number of days for the soldiers to win, as well as the path/strategy the soldiers should follow to accomplish that feat.
The tests in the tests.py class are labeled according with whether they fall under cases 2a, 2b, 2c, 2d in the classification given in the tables above.
The code in CastleDefenseIIIMath.py uses the formulae we derived above to quickly find the minimum number of days solution for the soldiers to win.
There are now 54 tests as opposed to 27 in our previous two posts.
If you want to run just the previous 27 tests, make all_tests=old_tests in tests.py. This will run very quickly.
Some of the newer tests (like tests 37 and 46) take some time to execute but with some minutes of patience you will get the solution. Many of those newer tests would be impossible to run in a timely manner with our previous exhaustive search code.
The code in CastleDefenseIIIMath.py uses the formulae we derived above to quickly find the minimum number of days solution for the soldiers to win.
There are now 54 tests as opposed to 27 in our previous two posts.
If you want to run just the previous 27 tests, make all_tests=old_tests in tests.py. This will run very quickly.
Some of the newer tests (like tests 37 and 46) take some time to execute but with some minutes of patience you will get the solution. Many of those newer tests would be impossible to run in a timely manner with our previous exhaustive search code.
No comments:
Post a Comment