Problem:

(From Alex Sierra, via fivethirtyeight.com). There are two warlords: you and your archenemy, with whom you’re competing to conquer castles and collect the most victory points. Each of the $10$ castles has its own strategic value for a would-be conqueror. Specifically, the castles are worth $1, 2, 3 \dots , 9$ and $10$ victory points. You and your enemy each have $100$ soldiers to distribute between any of the $10$ castles. Whoever sends more soldiers to a given castle conquers that castle and wins its victory points. If you each send the same number of troops, you split the points. Whoever ends up with the most points wins.

But now, you have a spy! You know how many soldiers your archenemy will send to each castle. The bad news, though, is that you no longer have 100 soldiers — your army suffered some losses in a previous battle. What is the value of the spy? That is, given a spy who can inform you of your enemy’s allocations, how many soldiers do you need to always be able to win?

Solution:

Theorem: You need exactly $56$ soldiers to always be able to win, so the value of so the value of the spy is $44$.

Proof.

Let $b(i)$ be the number of soldiers the enemy sends to caste $i$. First we show that you need at least 56 soldiers to always be able to win. Consider the case where the enemy makes the following allocations:

$$\begin{aligned} b(1) &= 1 \\ b(2) &= 3 \\ b(3) &= 5 \\ \vdots \\ b(10) &= 19 \\ \end{aligned}$$

Then we need two soldiers per point we win and since we need at least $28$ i.e. half of $1 + 2 + \dots + 10$ points to win, this will require $56$ soldiers.

Now the task is to show that $56$ always works. That is, for any allocation of the enemy’s $100$ soldiers, if we know the allocations, we should be able to win with $56$ soldiers.

Suppose for the sake of contradiction that this were not the case. Then for any choice of castles $a_1, \dots a_k$ that are sufficient to win the war i.e. $\sum_{i = 1}^k a_i \geq 28$, we must need more than 56 soldiers to win these castles. That is

$$\sum_{i = 1}^k \left( b(i) + 1 \right) \geq 57$$

or in other words:

$$\label{eq1}\tag{1} \sum_{i = 1}^k b(i) \geq 57 - k.$$

With this, we can generate some bounds on each $b(i)$. First note that we can assume $b(1) \leq b(2) \leq \dots \leq b(10)$ since any configuration where $b(n) > b(n + i)$ is strictly easier to win than one where this is not the case. This is because it allows us to win a higher valued castle with less soldiers than it would take to win the lower valued one.

Now we can create bounds for $b(1)$. Using Equation (\ref{eq1}) and castle combinations with high enough value, we have:

$$\begin{aligned} b(1) + b(8) + b(9) + b(10) &\geq 53 \\ b(1) + b(2) + b(3) + \dots + b(7) &\geq 50 \\ \end{aligned}$$

adding these together, we get

$$\begin{aligned} b(1) + b(1) + b(2) +\dots+ b(10) &\geq 103 \\ b(1) + 100 &\geq 103 \\ b(1) &\geq 3 \\ \end{aligned}$$

Already we are in a good place, since the warlord is forced to make a seemingly suboptimal allocation—sending three soldiers to a low valued castle. Now consider the following inequalities:

$$\begin{aligned} b(2) + b(7) + b(9) + b(10) &\geq 53 \\ b(2) + b(3) + b(4) + \dots + b(6) + b(8) &\geq 51 \\ \end{aligned}$$

which, when added, give

$$\begin{aligned} b(2) - b(1) + b(1) + \dots + b(10) &\geq 104 \\ b(2) - b(1) + 100 &\geq 104 \\ b(2) &\geq b(1) + 4 \geq 7\\ \end{aligned}$$

Similarly, for $b(3)$ we can look at

$$\begin{aligned} b(3) + b(6) + b(9) + b(10) &\geq 53 \\ b(1) + b(3) + b(4) + b(5) + b(7) + b(8) &\geq 51 \\ \end{aligned}$$

which, when added, gives

$$\begin{aligned} b(3) - b(2) + b(1) + \dots + b(10) &\geq 104 \\ b(3) - b(2) + 100 &\geq 104 \\ b(3) &\geq b(2) + 4 \geq 11\\ \end{aligned}$$

And lastly, for $b(4)$, we get

$$\begin{aligned} b(4) + b(5) + b(9) + b(10) &\geq 53 \\ b(1) + b(2) + b(4) + b(6) + b(7) + b(8) &\geq 51 \\ \end{aligned}$$

which gives

$$\begin{aligned} b(4) &\geq b(3) + 4 \geq 15\\ \end{aligned}$$

So we have,

$$\begin{aligned} b(1) &\geq 3 \\ b(2) &\geq 7 \\ b(3) &\geq 11 \\ b(4) &\geq 15 \\ \end{aligned}$$

and from our assuption that $b(1) \leq \dots \leq b(10)$, we have

$$\begin{aligned} b(1) + b(2) + \dots + b(10) &\geq 3 + 7 + 11 + 15 \cdot 7 \\ &= 126 \end{aligned}$$

which clearly contradicts the fact that $b(1) + \dots + b(10) = 100$. Thus our assumption that there is some enemy allcoation for which we cannot win with $56$ soldiers must be false. Therefore, we should always be able to win with exactly $56$ soldiers and so the spy is worth $44$ soldiers.