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

| cite | improve this question | |
$\endgroup$
  • 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 '12 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 '12 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 '12 at 13:33
  • 1
    $\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 '12 at 21:42
  • 1
    $\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 '12 at 12:30
102
$\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$.)

| cite | improve this answer | |
$\endgroup$
  • 20
    $\begingroup$ +1: For proving optimality of the value 10, and showing how OP implicitly has shown that. $\endgroup$ – Aryabhata Jan 26 '12 at 18:44
  • 4
    $\begingroup$ Perfect answer. I was looking for something like this. $\endgroup$ – user4951 Apr 2 '12 at 7:56
65
$\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.

| cite | improve this answer | |
$\endgroup$
  • 35
    $\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 '12 at 14:05
  • 14
    $\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 '12 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 '12 at 15:51
  • 1
    $\begingroup$ I really like this answer, even a child could understand it. $\endgroup$ – BlueRaja - Danny Pflughoeft Jan 26 '12 at 20:37
  • 2
    $\begingroup$ @EricNaslund: What if the soldiers were Centaurs! $\endgroup$ – aslum Jan 27 '12 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%).

| cite | improve this answer | |
$\endgroup$
  • 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 '12 at 16:33
  • $\begingroup$ Good idea, I just reworded it to have less math and more natural language. $\endgroup$ – Xonatron Jan 26 '12 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

| cite | improve this answer | |
$\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.
| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\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 '12 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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 for referencing the trendy Venn diagram $\endgroup$ – filiprem Jan 27 '12 at 14:41
  • 2
    $\begingroup$ Vann diagram is not a proof! $\endgroup$ – Lrrr Feb 1 '12 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.

| cite | improve this answer | |
$\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 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

| cite | improve this answer | |
$\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.