100 Soldiers riddle

One of my friends found this riddle.

There are 100 soldiers. 85 lose a left leg, 80 lose a right leg, 75
lose a left arm, 70 lose a right arm. What is the minimum number of
soldiers losing all 4 limbs?

We can’t seem to agree on a way to approach this.

Right off the bat I said that:

85 lost a left leg, 80 lost a right leg, 75 lost a left arm, 70 lost a right arm.
100 - 85 = 15
100 - 80 = 20
100 - 75 = 25
100 - 70 = 30
15 + 20 + 25 + 30 = 90
100 - 90 = 10

My friend doesn’t agree with my answer as he says not all subsets were taken into consideration. I am unable to defend my answer as this was just the first, and most logical, answer that sprang to mind.

Answer

Here is a way of rewriting your original argument that should convince your friend:

Let A,B,C,D\subset\{1,2,\dots,100\} be the four sets, with |A|=85,|B|=80,|C|=75,|D|=70. Then we want the minimum size of A\cap B\cap C\cap D. Combining the fact that |A\cap B\cap C\cap D|=100-|A^c\cup B^c\cup C^c\cup D^c| where A^c refers to A complement, along with the fact that for any sets |X\cup Y|\leq |Y|+|X| we see that |A\cap B\cap C\cap D|\geq 100-|A^c|-|B^c|-|C^c|-|D^c|=10.

You can then show this is optimal by taking any choice of A^c, B^c, C^c and D^c such that any two are disjoint. (This is possible since the sum of their sizes is 90 which is strictly less then 100.)

Attribution
Source : Link , Question Author : Pieter van Niekerk , Answer Author : Eric Naslund

Leave a Comment