80
$\begingroup$

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 one 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.

  • 0
    I would intitutively like to answer like this : Assume that there is 100 boxes and 85,80,75,70 of color A,B,C,D balls. Now I want to put all the balls in the boxes. First put 85 balls from 1..85 positions of A. Then in the same continue to put B from 85..100 then 1..65. Then put C from 66 to 100 and then from 1..40. Then put D from 41..100 and then 1..10. You see only boxes 1..10 have four balls.2015-01-24

9 Answers 9

97

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

  • 3
    Perfect answer. I was looking for something like this.2012-04-02
63

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.

  • 0
    @LiamM (+1) for simplicity.2016-01-30
9

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

  • 0
    Good idea, I just reworded it to have less math and more natural language.2012-01-26
6

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

5

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.
3

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.

  • 0
    Other answers are even better. The next challenge how do we do this by pencil pushing. Something like D is guys that lost all 4 limbs and D is >=...>=...>=...>=102012-03-14
2

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

  • 2
    Vann diagram is not a proof!2012-02-01
1

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.

1

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 linear equation solver applet I found at http://vinci.inesc.pt/lp/ 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.

min: x1111;  c1: x0000>=0; c2: x0001>=0; c3: x0010>=0; c4: x0011>=0; c5: x0100>=0; c6: x0101>=0; c7: x0110>=0; c8: x0111>=0; c9: x1000>=0; c10: x1001>=0; c11: x1010>=0; c12: x1011>=0; c13: x1100>=0; c14: x1101>=0; c15: x1110>=0; c16: x1111>=0; c17: x0000 <= 100; c18: x0001<=100; c19: x0010<=100; c20: x0011<=100; c21: x0100<=100; c22: x0101<=100; c23: x0110<=100; c24: x0111<=100; c25: x1000<=100; c26: x1001<=100; c27: x1010<=100; c28: x1011<=100; c29: x1100<=100; c30: x1101<=100; c31: x1110<=100; c32: x1111<=100; c33: x1000 + x1001 + x1010 + x1011 + x1100 +x1101 + x1110 +x1111 = 70; c34: x0100 + x0101 + x0110 + x0111 + x1100 +x1101 + x1110 +x1111 = 75; c35: x0010 + x0011 + x0110 + x0111 + x1010 +x1011 + x1110 +x1111 = 80; c36: x0001 + x0011 + x0101 + x0111 + x1001 +x1011 + x1101 +x1111 = 85; c37: x0000 + x0001 + x0010 +x0011 + x0100 + x0101 + x0110 +x0111 + x1000 + x1001 + x1010 +x1011 + x1100 + x1101 + x1110 + x1111 = 100; 

solution:

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

all other variables (percentages) are 0