This week’s Riddler is about the value of perfect information in a simplified war game. There are 10 castles, worth 1, 2, 3, … , 9, and 10 points each, and two players each assign a certain number of troops to each castle. If one player has more troops at any given castle, they win the points for that castle, and the player with the most points wins the game.
The twist in this version is that one player gets a second-mover advantage, by getting to see the first player’s allocation before making their own. Clearly that information is very valuable, but the challenge is quantify exactly how much it’s worth. Specifically, if Player 1 has 100 soldiers, find the smallest k so that if Player 2 has k soldiers and knows Player 1’s distribution, they can always win the game.
The first thing I did in exploring this problem was think about what a well-defended allocation would look like. You might be able to get this part in a flash of inspiration (especially since the answer is neat for the specific values in the question), but my muse was out for lunch, so I tried an algorithmic approach instead.
First, I wanted to find all the ways that you could overcome any particular troop allocation (so that I could find the ‘cheapest’ one). In other words, I needed all the possible subsets of the 10 castles which together would be worth at least 28 points, or just over half of the total points available. To do that, I listed all 2^10 = 1024 subsets of the 10 castles*, removed the ones worth <28 points (which is half of them, since a subset adds up to >28 if and only if its complement doesn’t), and then removed the ones that had redundancy (i.e. the ones where you could remove at least one castle and still be over 28 points). This left 77 possible minimal configurations, one of which must be the cheapest way to defeat the starting allocation.
Next, I used a simple greedy algorithm to incrementally allocate troops. I started with no troops allocated, and at each step I worked out which castle was included in the greatest number of the possible low-cost attacks, and added one troop to that castle. For example, if there were eight different attacks that could defeat the starting allocation with 20 troops (and that was the lowest number that could work), and all of them included castle 10, I would reinforce castle 10. If there was a tie for the most common castle among attacks with the lowest cost, I would use how often each castle occurred in the next-lowest-cost attacks as a tie-breaker (e.g. how often each castle occurred in attacks that took 21 troops, in the above example). The animation below shows the results:
A greedy algorithm to determine the best defensive configuration with n troops. (GIF made with gifcreator.me)
As you might expect, the best-defended allocation favors the most valuable castles, but leaves nothing uncovered (although the 1-point castle doesn’t get a troop allocated until ~70 have already been deployed elsewhere). With 100 troops allocated, the numbers on each castle are 1, 3, 5, …, 17, and 19 – in other words, castle n is allocated 2n-1 troops for each n.
This makes sense, since this means that conquering n points always requires 2n troops regardless of where you do it, so you can never conquer 28 points with fewer than 56 troops regardless of where you put them, and it’s where you might have had a flash of inspiration if you realized at the start that the average number of troops required to conquer each point must be 2, since there are 55 points, and winning them all will take 110 troops (100 to match the opponent’s allocation, plus one for each castle). It also hints at a way to prove that 56 is always enough: if the average ‘cost per point’ is 2, then we should be able to find a subset whose cost per point is no higher than average, and which is big enough to win.
My initial thought was to sort the castles in order of the ratio (# of troops to take) / (# of points for taking) and conquer in increasing order until you win. Unfortunately, while that will guarantee you a conquest with an average cost-per-point of no more than 2, it won’t guarantee that you don’t skip right past 28 points and end up on a higher number (so e.g. if you have 25 points and the next castle by ratio is worth 7, you end up taking 32 points, so even if your ratio is <2, you might still need >56 troops).
So instead, we consider only the subsets worth exactly 28 points. What we would like is to find a collection of 28-point subsets which between them contain each castle the same number of times – then we would know that the average cost-per-point across them all is the same as the overall average (2), and hence at least one has an average no greater than 2.
Finding such a collection is not too hard with the help of a spreadsheet. First note that, if each castle appears x times in the collection, then the sum of the point value of each collection is 55x. But if there are y subsets in the collection, then the total point value is 28y. The smallest positive integer solution to 55x=28y is x=28, y=55 (since 28 and 55 have no common divisors), so we’re looking for a collection of 55 subsets. There are 40 distinct ones, so I started from that list, then added ones that ‘filled the gaps’ for castles that were least represented until I got to a complete set of 55 with the desired property.
A collection of subsets of the castles which (i) are each worth 28 points, and (ii) together include each castle the same number of times.
Since this collection uses each castle 28 times, and the cost to take over every castle is 110 for any allocation of 100 troops, the total cost to take over all 55 configurations must be 28×110, and hence the average must be 28×110/55 = 56. But if the average of some numbers is 56, they can’t all be greater than 56, so we have proved that there is always a way to win with a spy and no more than 56 troops (in fact, we’ve proved a slightly stronger result, that you can always do this by capturing exactly 28 points-worth of castles). And since we already found an allocation that always costs 56 troops to defeat, we know that’s the best possible outcome.
A quick housekeeping note: the last two posts notwithstanding, this isn’t intended to be a particularly puzzle-focused blog (although I do find exploring puzzles a great way to build some non-traditional Excel skills) – they’re just a bit shorter / easier to write, and they come with a natural deadline when the solution is released a week later, which turns out to be important for procrastinator like myself… I hope to resume ‘normal’ activity shortly.
*I’m glazing over draws here… it turns out they don’t matter, and there’s already more detail in this post than you probably wanted…
Cover image: Castelo da Feira, picture by Wikipedia user Keaneu.
The Excelements 