September 9, 2022
From Mike Strong comes a brief return to last week’s battle:
In last week’s Battle for Riddler Nation, you had to assign 100 phalanxes of soldiers to 10 castles, each worth a distinct number of points. For example, you could assign all 100 phalanxes to a single castle (and none to the others), split them evenly so that there were 10 phalanxes at every castle or arrange them in some other way.
What was the total possible number of strategies you could have submitted?
\(\binom{109}{9} = \binom{109}{100} = 4,263,421,511,271\) different strategies
Explanation:
One way of going after the puzzle is to consider placing the 100 phalanxes into 10 "zones" that represent castles. This way, we can re-interpret the placement as placing bars among stars, where each star represents a phalanx and the bars determine the boundaries for each castle. Therefore, we would have 100 stars and 9 bars (to mark 10 castles). For example, if we place all 100 phalanxes into the 10th castle, we would have the following arrangement:
|||||||||****...*** (100 stars)
If we place 1 phalanx in castle 1, 2 phalanxes in castle 2, and remaining in castle 10, we would then have:
*|**||||||||****...*** (97 stars)
As a reminder, the spaces between the bars represent castles 1 to 10, respectively going left to right.
Therefore, the original puzzle reduces down to: given 109 slots, with 9 bars and 100 stars, how many ways are there to place the 9 bars (or 100 stars) among the 109 slots? The answer is simply:
\begin{align} \binom{109}{9} = \binom{109}{100} = 4,263,421,511,271 \\ \end{align}
In general, if we were to place \(n\) phalanxes into \(k\) different castles, we would have in total this many distinct strategies:
\begin{align} \binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n}\\ \end{align}
Since we would have \(k-1\) bars demarcating the \(k\) castles in which separates the \(n\) phalanxes, and \(n + k - 1\) slots in total.