100 Soldiers riddle

Question

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 1

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$.)

Answer 2

If you add up all the injuries, there is a total of 310 sustained. That means 100 soldiers lost 3 limbs, with 10 remaining injuries. Therefore, 10 soldiers must have sustained an additional injury, thus losing all 4 limbs.

The manner in which you've argued your answer seems to me, logical, and correct.

Answer 3

I agree with your answer. To have the minimum number lose all four limbs, you want everybody else to lose 3. You have organized it this way-by adding 15,20,25, and 30 you have argued these sets are distinct.

Answer 4

agree with 10:

minimum number of amputees with both legs missing: ( 100 - (100 - 85) + (100 - 80) ) = 65 minimum number of amputees with both arms missing: ( 100 - (100 - 75) + (100 - 70) ) = 45

now use the same "venn" analysis to find minimum overlap between the previously calculated #s

minimum number of amputees with all limbs missing: (100 - (100 - 65) + (100 - 45) ) = 10

Answer 5

Your answer is right. Think of it like this: How many people are free of not losing each limb? Make sure these people do not overlap, to create a group of people who are guaranteed to have at least one limb and to maximize the size of this group. The remaining people unfortunately do not have this "one limb is safe" guarantee. Calculate their percentage (10%).

Answer 6

You can easily do it visually with a Venn diagram with the four sets of soliders with each limb. For mimimum number of soliders losing all four limbs, none of the inner sets overlap. So $100 - (15+20+25+30) = 10$.

Answer 7

10 and this is why.

• The smallest set of injured soldiers (ones who lost their right arm) were 70 in number. That leaves 30 out of 100 who kept their right arm. Therefore, the largest number of soldiers without the left arm and with the right arm can only be 30 at most. This means that the sets of 70 and 75 must overlap by at least 45.
• We now have a set of 45 soldiers who are missing both arms. That leaves 55 who haven't lost both arms. The largest number of soldiers who have lost their right leg and haven't lost both arms can only be 55 at most. This means that the sets of 45 and 80 must overlap by at least 25.
• We now have a set of 25 soldiers who are missing both arms and their right leg. The sets of 85 and 25 must overlap by at least 10.

Answer 8

80, 85, 70, 75

Let's do this

How many lost both legs?

Well, 80+85= 165. So at least 65 people lost both legs.

How many lost both arms? Well 70+75= 145. So 45 people lost both arms and legs.

Now how many lost all legs and arms?

At the minimum 45 people lost both legs. At the minimum 65 people lost both arms.

So total there are 110 people that lost both arms and legs if no body lost all. Given that there are only 100 people, then we figure that 10 must have lost all.

Answer 9

if your friend has sufficiently mathematical knowledge there are ways to convince your friend by using a computer program :-)

Some time ago i saw a similiar problem where the numbers were percentages https://groups.google.com/group/de.rec.denksport/browse_thread/thread/aa7dde6a6043d7c4. So the solution does not have to be an integer. Then one can formulate the problem as linear programming problem. The meaning of the variable $x1110$ for example is: it is the percentage of soldiers that have the first property "lost a left leg" (first index of variable $x$ is $1$), the second property "lost a right leg" (second index of variable $x$ is $1$), the third property "lost a left arm" (third index of variable $x$ is $1$) but not the fourth property "lost a right arm" (fourth index of variable $x$ is $0$). The four statements paritions the set of all soldiers in $2^4$ subsets and the following holds: the percentages are between 0 and 100 (c1 ... c32) , the percentages of soldiers with the first,...,fourth property is 70,75,80,85 (c33,...,c34) and the sum of all percentages is 100. we are interested in the case where the number of soldiers that have lost all four limbs is minimal (min). We can use this input directly in the online linear optimization solver I found and get the expected solution. If all calculation are done in exact arithmetic (I think the applet does not) then 10 is the minimal integer solution.

var x0000>=0;
var x0001>=0;
var x0010>=0;
var x0011>=0;
var x0100>=0;
var x0101>=0;
var x0110>=0;
var x0111>=0;
var x1000>=0;
var x1001>=0;
var x1010>=0;
var x1011>=0;
var x1100>=0;
var x1101>=0;
var x1110>=0;
var x1111>=0;

minimize z: x1111; 

subject to c17: x0000 <= 100;
subject to c18: x0001<=100;
subject to c19: x0010<=100;
subject to c20: x0011<=100;
subject to c21: x0100<=100;
subject to c22: x0101<=100;
subject to c23: x0110<=100;
subject to c24: x0111<=100;
subject to c25: x1000<=100;
subject to c26: x1001<=100;
subject to c27: x1010<=100;
subject to c28: x1011<=100;
subject to c29: x1100<=100;
subject to c30: x1101<=100;
subject to c31: x1110<=100;
subject to c32: x1111<=100;
subject to c33: x1000 + x1001 + x1010 + x1011 + x1100 +x1101 + x1110 +x1111 = 70;
subject to c34: x0100 + x0101 + x0110 + x0111 + x1100 +x1101 + x1110 +x1111 = 75;
subject to c35: x0010 + x0011 + x0110 + x0111 + x1010 +x1011 + x1110 +x1111 = 80;
subject to c36: x0001 + x0011 + x0101 + x0111 + x1001 +x1011 + x1101 +x1111 = 85;
subject to c37: x0000 + x0001 + x0010 +x0011 + x0100 + x0101 + x0110 +x0111 + x1000 + x1001 + x1010 +x1011 + x1100 + x1101 + x1110 + x1111 = 100;

end;

solution:

x1111 = 10.0
x0111 = 30.0
x1011 = 25.0
x1101 = 20.0
x1110 = 15.0

all other variables (percentages) are 0

Answer 10

Don't ask how many soliders have lost all limbs at least, but how many have saved a limb, at most.

There are 100 soldiers. 15 saved the left leg, 20 saved the right leg, 25 saved the left arm, 30 saved the right arm. Together they have only 90 limbs left, so at most 90 can have one.

That means at least 10 have lost all 4 limbs.