Junior High Student Question for Parent - Algebra Word Problem

Sal has 210 pumpkins and eery second pumpkin is either too big or too small. Every third pumpkin is too oblong. Every fifth pumpkin is too fat. If the remaining pumpkins are perfect, how many perfect pumpkins are in Sal's pumpkin patch?

I understand that Good + Bad = 210, and Good = 210 - Bad.

I cannot define bad, as 2x, 3x, and 5x are not mutually exclusive.

Re: Junior High Student Question for Parent - Algebra Word Problem

You're exactly right about they're not being mutually exclusive.

This is the technique of counting by inclusion-exclusion.

----------------------------------------

That's seems to be a demanding problem for a junior high school level algebra class. (Unless the teacher expects them to do it by hand out to 210?) Hey - if the students are up to it - fantastic!

----------------------------------------

There's a trick you can use that's not ideal, in that it's exploiting that 210 is evenly divisible by 2 and 3 and 5. I'll show you how to do it the general correct way, but here's the trick:

Do it "by hand" for pumpkins #1-30 (You'll get Good are 1, 7, 11, 13, 17, 19, 23, 29, for a total of 8). Notice that "every 2nd", "every 3rd", and "every 5th" all stop on pumpkin #30, and then begin to repeat their pattern exactly as if you started counting at 1 again. In other words, the number of bad pumpkins from 1-30 is the same as the number of bad pumkins from 31-60. And also for 61-90, and 91-120, and 121 - 150, and 151-180, and 181-210. Thus the number of Good pumpkins between 1 and 210 is 7 times the number of good pumpkins between 1 and 30. (So the number of Good pumpkins of those 210 is 7x8 = 56.)

----------------------------------------

Here's the proper way to do it:

Let X = {1, 2, 3, ... , 210}

Let M2 = the set of multiples of 2 in X = {2, 4, 6, ..., 210}

Let M3 = the set of multiples of 3 in X = {3, 6, 9, ..., 210}

Let M5 = the set of multiples of 5 in X = {5, 10, 15, ..., 210}

Then Bad = |M2 union M3 union M5| (the notation |Z| means the number of things in set Z).

Here's how inclusion-exclusion counting works:

$\displaystyle |M_2 \cup M_3 \cup M_5|$

$\displaystyle = |M_2| + |M_3| +|M_5| - [ \ |M_2 \cap M_3| + |M_2 \cap M_5| + |M_3 \cap M_5| \ ] + |M_2 \cap M_3 \cap M_5|.$

$\displaystyle \text{Now } M_2 \cap M_3 = \text{ the multiples of BOTH 2 and 3 in X. That's the multiples of 6 in } X,$

$\displaystyle \text{which is the set } \{6, 12, 18, ..., 210 \}.$

$\displaystyle \text{Being consisitent with this naming pattern, call that } M_6,$

$\displaystyle \text{so } M_6 = M_2 \cap M_3 = \{6, 12, 18, ..., 210 \}.$

$\displaystyle \text{Likewise } M_{10} = M_2 \cap M_5, M_{15} = M_3 \cap M_5, M_{30} = M_2 \cap M_3 \cap M_5.$

$\displaystyle \text{So Bad }= |M_2 \cup M_3 \cup M_5|$

$\displaystyle = |M_2| + |M_3| +|M_5| - [ \ |M_2 \cap M_3| + |M_2 \cap M_5| + |M_3 \cap M_5| \ ] + |M_2 \cap M_3 \cap M_5|.$

$\displaystyle \text{Thus Bad }= |M_2| + |M_3| +|M_5| - [ \ |M_6| + |M_{10}| + |M_{15}| \ ] + |M_{30}|.$

You can count each of those sets by dividing into 210. All of those numbers (2, 3, 5, 6, 10, 15, 30) are divisors of 210, so you don't even have the complications from rounding down.

$\displaystyle \text{Thus Bad }= \frac{210}{2} + \frac{210}{3} + \frac{210}{5} - \left[ \ \frac{210}{6} + \frac{210}{10} + \frac{210}{15} \ \right] + \frac{210}{30}$

$\displaystyle = 105 + 70 + 42 - [ \ 35 + 21 + 14 \ ] + 7 = 217 - 70 + 7 = 224 - 70 = 154.$

$\displaystyle \text{Thus Good } = 210 - \text{ Bad } = 210 - 154 = 56.$

----------------------------------------

Counting by inclusion-exclusion:

$\displaystyle |A \cup B| = |A| + |B| - |A \cap B|.$

That's because anything that's in the intersection was counted twice in the initial $\displaystyle |A| + |B|$, so you has to subtract it once so that it gets counted a net of only 1 time.

If in a room, 5 people raise their hands to say they like football, 3 people raise their hands to say they like basketball, and exactly 2 people raised their hands both times, then how many people in that room like football or basketball? Try 5 + 3 = 8, but then remember that 2 people raised their hands both times, and so those two people were double counted, so the actual correct answer is 8-2 = 6.

$\displaystyle \text{With } A \cup B \cup C, \text{ it's the exact same idea, except is more complicated:}$

$\displaystyle |A \cup B \cup C| = |A| + |B| +|C| - [ \ |A \cap B| + |A \cap C| + |B \cap C| \ ] + |A \cap B \cap C|.$

$\displaystyle \text{Something in A and B, but not C, gets counted in } |A|, |B|, - |A \cap B|,$

$\displaystyle \text{and so in total would be counted exactly 1 time, as the sum gives: 1+1-1 = 1.}$

$\displaystyle \text{If something was in A, but not B or C, then it would be counted in just } |A| \text{ and so count to 1.}$

$\displaystyle \text{If something was in A and B and C, then it would be counted in every term there, hence sum to 1: 1+1+1-[1+1+1]+1 = 1.}$

Re: Junior High Student Question for Parent - Algebra Word Problem

Quote:

Here's how inclusion-exclusion counting works:

$\displaystyle |M_2 \cup M_3 \cup M_5|

= |M_2| + |M_3| +|M_5| - [ \ |M_2 \cap M_3| + |M_2 \cap M_5| + |M_3 \cap M_5| \ ] + |M_2 \cap M_3 \cap M_5|.$

Just to be curious, how do you know how to calculate the number of elements in unison of various sets?

Is it something that is stated in the textbooks?Or is it just came up by you at the very instant?

Re: Junior High Student Question for Parent - Algebra Word Problem

I am the OP, so I am not answering jonwen97's question for johnsomeone, but I will say that I came to this realization when I manually solved this problem for the first 30 pumpkins and noted a Venn diagram with intersecting circles. Once I realized that, the above mathematical presentation makes sense. Keep in mind that the Venn diagram may have been different if the original problem was changed with different parameters.

With a nudge of prodding confidence, the Junior-High student was able to solve this extra credit problem using the first intuitive method. The intuitive pattern method was presented as training, but the mathematical solution was retained by myself.

Johnsomeone, your three-tier solution (intuitive, intuitive with a pattern , then mathematical) was very elegant - my hat's off and full bow to you.

Re: Junior High Student Question for Parent - Algebra Word Problem

With hindsight now, I should have realized that a factor of 2, 3, and 5 is common at 30, thus the union of three sets.

Re: Junior High Student Question for Parent - Algebra Word Problem

I'd assume it's in a course/text on discrete math or combinatorics - probably probability, maybe "computer math" courses too.

It's been so long that I don't recall if I "found it" or read it. It's not hard "to find" if you're good at this stuff and are looking for it.

I believe it's called the Principle of Inclusion-Exclusion (yup - google - there it is).

1 Attachment(s)

Re: Junior High Student Question for Parent - Algebra Word Problem

Since you gave such a warm thanks, I'll throw in a few more tidbits about it.

1) It's on the internet if you google inclusion-exclusion principle.

2) It generalizes. If you have n sets, then to find the cardinality (count) of their union, you first add the cardinalities of ALL of those n sets (think of that as taking them "1 at a time"), then subtract the cardinalities of ALL their "2 at a time" intersections, then add the cardinalities of ALL of their "3 at a time" intersections, then subtract the cardinalities of ALL of their "4 at a time" intersections, ... etc... until you end by adding or subtracting (depending on if n is even or odd) the cardinalities of ALL of their "n at a time" intersections (there's only 1 "n at a time" intersection, which is the intersection of all of the sets).

3) Here's a picture, for what it's worth: Attachment 25542

4) Here's a proof for the n=3 case. I'll assume it's already known for the n = 2 case.

$\displaystyle \text{We already know that }|X \cup Y| = |X| + |Y| - |X \cap Y| \text{ for all finite sets }X, Y.$

$\displaystyle \text{Claim: If A, B, and C are finite sets, then }$

$\displaystyle |A \cup B \cup C| = |A| + |B| + |C| - [ \ |A \cap B| + |A \cap C| + |B \cap C| \ ] + |A \cap B \cap C|.$

$\displaystyle \text{Proof:}$

$\displaystyle \text{Will first show that } |A \cap (B \cup C)| = |A \cap B| + |A \cap C| - |A \cap B \cap C|.$

$\displaystyle \text{By general properties of intersections and unions, have: }$

$\displaystyle A \cap (B \cup C) = (A \cap B) \cup (A \cap C).$

$\displaystyle \text{Then apply }|X \cup Y| = |X| + |Y| - |X \cap Y| \text{ using } X = A \cap B , Y = A \cap C,$

$\displaystyle \text{getting }|(A \cap B) \cup (A \cap C)| = |A \cap B| + |A \cap C| - |(A \cap B) \cap (A \cap C)|.$

$\displaystyle \text{But }(A \cap B) \cup (A \cap C) = A \cap (B \cup C), \text{ and } (A \cap B) \cap (A \cap C) = A \cap B \cap C,$

$\displaystyle \text{so }|A \cap (B \cup C)| = |(A \cap B) \cup (A \cap C)| = |A \cap B| + |A \cap C| - |A \cap B \cap C|.$

$\displaystyle \text{With that hand, apply }|X \cup Y| = |X| + |Y| - |X \cap Y| \text{ using }$

$\displaystyle X = A, Y = B \cup C.$

$\displaystyle \text{That gives }|A \cup (B \cup C)| = |A| + |B \cup C| - |A \cap (B \cup C)|$

$\displaystyle = |A| + |B \cup C| - [ \ |A \cap B| + |A \cap C| - |A \cap B \cap C| \ ]$

$\displaystyle = |A| + |B \cup C| - \ |A \cap B| - |A \cap C| + |A \cap B \cap C|$

$\displaystyle = |A| + [ \ |B| + |C| - |B \cap C| \ ] - \ |A \cap B| - |A \cap C| + |A \cap B \cap C|$

$\displaystyle \text{(that used the n=2 case again, with }X = B, Y = C)$

$\displaystyle = |A| + |B| + |C| - |B \cap C| - |A \cap B| - |A \cap C| + |A \cap B \cap C|$

$\displaystyle = |A| + |B| + |C| - [ \ |A \cap B| + |A \cap C| + |B \cap C| \ ] + |A \cap B \cap C|,$

$\displaystyle \text{thus proving that }$

$\displaystyle |A \cup B \cup C| = |A| + |B| + |C| - [ \ |A \cap B| + |A \cap C| + |B \cap C| \ ] + |A \cap B \cap C|.$