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

$\endgroup$
9
  • 1
    $\begingroup$ There are 100 soldiers. 85 is the highest injured list. so only 15 are left to be potentially injured of all or neither of any of them. They might have not lost anything at all. In this case, you can say the least non-trivial minimum is 1 , considering the question might guarantee that there are people who lost all 4 limbs. The highest possible number should be 15. adding up the remaining from each injury isn't logical because it doesn't guarantee what you are trying to do. $\endgroup$
    – King
    Jan 26, 2012 at 17:39
  • 16
    $\begingroup$ I may be going out on a limb here, but it seems like a rather unlikely situation to have 10% limbless - unless their rules of engagement only allow for amputation. $\endgroup$
    – User3910
    Jan 26, 2012 at 17:49
  • 3
    $\begingroup$ This is from Lewis Carroll's A Tangled Tale, a collection of mathematical puzzles loosely woven into stories. $\endgroup$
    – Peter Shor
    Jan 27, 2012 at 13:33
  • 2
    $\begingroup$ This reminds me of the gory version of the pigeonhole principle: if you have more holes than pigeons, then at least one pigeon has more than one hole in it. $\endgroup$
    – Nate Eldredge
    Feb 1, 2012 at 21:42
  • 4
    $\begingroup$ There is a funny way to solve this if you think the other way around: 85 left leg loss means there are 15 right legs remaining, 80 right leg loss results in 20 remaining left legs and so on. At the end you end up in a situation where you want to distribute 90 limbs among 100 limbless soldier in a way that you want to minimize limbless soldiers after the distribution :) It is easy to see that in the best scenario there will be 10 limbless soldier remaining after the distribution, so the answer is 10. $\endgroup$
    – Hari
    Aug 24, 2012 at 12:30

10 Answers 10

Reset to default
105
$\begingroup$

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

$\endgroup$
2
  • 20
    $\begingroup$ +1: For proving optimality of the value 10, and showing how OP implicitly has shown that. $\endgroup$
    – Aryabhata
    Jan 26, 2012 at 18:44
  • 4
    $\begingroup$ Perfect answer. I was looking for something like this. $\endgroup$
    – user4951
    Apr 2, 2012 at 7:56
67
$\begingroup$

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.

$\endgroup$
9
  • 38
    $\begingroup$ Another way to say the same thing: "Since there are 310 injuries and 100 people, by the pigeon hole principle at least 1 person has 4 injuries. Since noone has more then 4 injuries, the pigeon hole principles guarantees that at least 10 people have 4 injuries." $\endgroup$
    – Eric Naslund
    Jan 26, 2012 at 14:05
  • 15
    $\begingroup$ A quibble: you don't necessarily have 100 soldiers losing 3 limbs. Imagine 70 soldiers losing 4 limbs, 5 soldiers losing 3 limbs, 5 soldiers losing 2, and 5 more losing 1. And 15 completely injury free. @Eric Naslund's reformulation is cleaner. $\endgroup$
    – Willie Wong
    Jan 26, 2012 at 15:12
  • 8
    $\begingroup$ (Hint hint: the nature of this website means you should feel free to incorporate Eric's reformulation and edit your answer to make it better!) $\endgroup$
    – Willie Wong
    Jan 26, 2012 at 15:51
  • 1
    $\begingroup$ I really like this answer, even a child could understand it. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Jan 26, 2012 at 20:37
  • 2
    $\begingroup$ @EricNaslund: What if the soldiers were Centaurs! $\endgroup$
    – aslum
    Jan 27, 2012 at 16:28
9
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ I like this answer for its use of common language. I'd like it even more without the percentages. $\endgroup$
    – madth3
    Jan 26, 2012 at 16:33
  • $\begingroup$ Good idea, I just reworded it to have less math and more natural language. $\endgroup$
    – Xonatron
    Jan 26, 2012 at 17:30
6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.
$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 >=...>=...>=...>=10 $\endgroup$
    – user4951
    Mar 14, 2012 at 10:40
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ +1 for referencing the trendy Venn diagram $\endgroup$
    – filiprem
    Jan 27, 2012 at 14:41
  • 2
    $\begingroup$ Vann diagram is not a proof! $\endgroup$
    – Lrrr
    Feb 1, 2012 at 9:09
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.