Problem Solving Strategies : Complementary Counting

Check out Mathcounts here, the best competition math program for middle school students.

Download this year's Mathcounts handbook here.

Video to watch on complementary counting from "Art of Problem Solving"

Part 1

Part 2

Question: How many two-digit numbers contain at least one 9?

 At beginning level, kids start to write down all the numbers that contain 9. However, this turns into impossible task if it's a three-digit or four-digit number. So let's try other ways to do it.

9 _ , if 9 is placed as the tens digit, unit digit can be chosen from 0 -9, altogether 10 numbers.
A lot of kids think there are only 9. Be careful. To find how many consecutive terms from number a to b, you do (b-a) +1

_ 9, there will be 9 choices (1-9) this time as the tens digit.(Why?) Zero can't be placed other than unit digit.
So total you have 10 + 9 - 1 (you've counted 99 twice) = 18

This way is better than the first one, but once the numbers become large, you will easily lose track of those double-counting, triple-counting numbers and over count your answers.

Here is a better way to tackle this type of problem: Think about the case of numbers that contain no 9s, and subtracting this value from the total number of two-digit numbers will give you the answer.

There are 99-10 +1 =90 total two digit numbers. There are 8 (the tens digit) x 9 (unit digit) = 72 numbers that contain no 9s. So 90-72 = 18 gives you the answer.

Try this question: 
How many three-digit numbers contain at least one 9?
There are 999 - 100 + 1 or 999 - 99 = 900 three-digit numbers. 
Or 9 x 10 (you can use the digit "0" now" x 10 = 900 three-digit numbers
900 - 8 x 9 x 9 = 252 numbers 

This is called "complementary counting" and there are numerous problems that you can use this strategies to simplify the reasoning. 

Here is another harder problem from 2003 Mathcounts Chapter Sprint Round #29:
Each day, two out of the three teams in a class are randomly selected to participate in a MATHCOUNTS trial competition. What is the probability that Team A is selected on at least two of the next three days? Express your answer as a common fraction.

Solution:  
Use complementary counting. 
If each day two of the team will be chosen, there will be 3C2 = 3 ways to choose the team -- AB, BC, or AC, so 1/3 of the chance that team A won't be chosen and 2/3 of the chance that team A will be chosen. 

Case 1: Team A is not chosen on any of the three days. The probability is (1/3) ³= 1/27.
Case 2: Team A is chosen on one of the three days : The probability is (2/3) times (1/3)² times 3C1 = 6/27 (A - -, - A - or - - A, which is 3C1 = 3 ways)

Total possibilities - none - at least 1 time = at least two times Team A will be chosen 
so the answer is 1 - 1/27 - 6/27 = 20/27

Other applicable problems: (answer key below)

#1: 2006 AMC10 A: How many four-digit positive integers have at least one digit that is a 2 or 3? 

#2: What is the probability that when tossing two dice, at least one dice will come up a "3"? 

#3: If {x,y} is a subset of S={1,2,3,....50}. What is the probability that xy is even?















Answer key: 

#1:  9000 - 7 x 8 x 8 x 8 = 5416

#2:  The probability of the dice not coming up with a "3" is 5/6.
       1 - (5/6)² = 11/36

2. 1 - (25/50) (24/49) -- only odd times odd will give you odd product, the others will all render even product, so the answer is 37/49.



 

Games: logical puzzle: the wolf, the sheep and the cabbages

Logical games:

How to cross the river without the wolf eating the sheep, the sheep eating the cabbages.

Here is the link to the puzzle "the wolf, the sheep and the cabbages".












Two versions of "Leap Frog Puzzle".

Leap Frog Puzzle 

Frogs Game 

Rate, Time, and Distance Question

Question: Harder SAT question: Esther drove to work in the morning at an average speed of 45 miles per hour. She returned home in the evening along the same route and averaged 30 miles per hour. If Esther spent a total of one hour commuting to and from work, how many miles did Esther drive to work in the morning?

Solutions I:
Let t be the time it took Esther to drive to work and (1-t ) be the time it took him to return home.

Since rate times time = distance, we can set the equation as 45 t = 30 (1- t), 75t = 30 so
t = \(\frac{\Large{2}}{\Large{5}}\) Plug in t to the previous equation : 45 * \(\frac{\Large{2}}{\Large{5}}\) = 18 miles ,which is the answer.

Solution II: 
Let D be the distance from Esther's home to work. 

\(\frac{\Large{D}}{\Large{45}}\) +  \(\frac{\Large{D}}{\Large{30}}\) = 1 (hour)
Times 90 both sides to get rid of the denominator and you have 2D + 3D = 90 
D = 18 miles

Solution III:

The rate ratio between driving to work and returning home is 45 : 30 or 3 :  2.

Since rate and time are inversely related (rt = d), the time ratio between the two is 2 : 3. 
45*\(\frac{\Large{2}}{\Large{5}}\) * 1 (hour) = 18 miles

Solution IV: (from Varun in FL)
The average speed can be found by harmonic mean: \(\dfrac {2\times 45\times 30}{45+35}\) = 36 mph. She drives for a total of 1 hour, so she drives 36 miles. Since she drives the same distance both ways, the distance to work is \(\dfrac {36} {2}\)=18 miles.

Question 1991 Mathcounts National #28 : A man is running through a train tunnel. When he is \(\frac{\Large{2}}{\Large{5}}\) of the way through, he nears a train that is approaching the tunnel from behind him at a speed of 60 mph. Whether he runs ahead or runs back, he will reach an end of the tunnel at the same time the train reaches that end. At what rate, in miles per hour, is he running? (Assume he runs at a constant rate.)

Solution : When the man went back \(\frac{\Large{2}}{\Large{5}}\) of the length of the tunnel, the train is at the beginning of the tunnel. 

Same thing happened if the men went ahead \(\frac{\Large{2}}{\Large{5}}\) of the length of the tunnel. The time it took the train to run through the length of the tunnel, the man could only run \(\frac{\Large{1}}{\Large{5}}\) of the same distance. 

So the speed of the man is \(\frac{\Large{1}}{\Large{5}}\) of the train's speed, which is \(\frac{\Large{1}}{\Large{5}}\) * 60 or 12 mph.  










Question #3: Sally drives to her aunt's house, which is 84 miles away, at 40 miles per hour and comes back home at 60 miles per hour. What is her average speed? 
Solution I: 
To find average speed, you use total distance over total time it takes Sally to drive. 
It takes Sally \(\frac{\Large{84}}{\Large{40}}\) + \(\frac{\Large{84}}{\Large{60}}\), or total 3.5 hours 
to drive 84 * 2 = 168 miles. 
\(\frac{\Large{168}}{\Large{3.5}}\) = 48 mph

Solution II: 
Similar to dimensional change question, as long as the segments are constant, the distance Sally drives is extraneous. Thus, it's much easier to use \(\frac{\Large{2}}{\frac{\Large{1}}{\Large{40}} - \frac{\Large{1}}{\Large{60}}}\)or \(\frac{\Large{2*40*60}}{\Large{40+60}}\) = 48 mph


Question #4: If Sally drives to her work at 40 miles per hour, she will be 15 minutes late. If she drives to her work at 60 miles per hour, she will be 15 minutes early, what speed will she arrive at her work on time?  How far away is her office ? 
Solution I: 
Let t be the time (hpm) Sally drives to her work on time. According to the given, we can set up 
the following equation: 
40 (t + \(\frac{\Large{1}}{\Large{4}}\)) = 60 ( t- \(\frac{\Large{1}}{\Large{4}}\) )
40 t + 10 = 60 t - 15 ;      25 = 20t ;       t = 1.25
Plug in to get the distance as 40 (1.25 + 0.25) = 60 miles

To get the average, use total distance over total time she spent \(\rightarrow\) \(\frac{D}{T}\) = \(\frac{\Large{120}}{\Large{1.5 + 1}}\) = 48 mph

Solution II :
Again, have you noticed that if  both time (late or early) to arrive to the destination is the same, the easiest
method is to still use the harmonic mean. \(\rightarrow\) \(\frac{\Large{2*a * b}}{\Large{a + b}}\)
a and b are the rates. \(\frac{\Large{2*40*60}}{\Large{40+60}}\) = 48 mph
 

Some Articles to Read and Ponder after Mathcounts state competition

For those students who really love problem solving, who care and are inquisitive but are disappointed at their chapter's/state's performance, I want to let you know that it's an honor meeting you online and learning from/along with you.

I know no matter how sincere I write here, it won't help much, so I'll just shut up.

However, I'm also disappointed at some students who said they need to take a break for the foreseeable future.

Well, if you love ___ (fill in the blank), you won't stop if you don't get to the chapter/state/nationals.
So there...

Here are some articles that after your taking a break from problem solving (I hope it's not too long), hope to see you come back and read them. Best of luck !!  Keep me posted !!

Pros and Cons of Math Competitions

Dealing with Hard Problems

Life After Mathcounts

Great Mathematicians on Math Competitions and "Genius"

Math Contests Kind of Suck from Mathbabe

TEDxCaltech -Jordan Theriot- The Pleasure of Finding Things Out

Why Physics? Skateboarding Physicist and Educator Dr. Yung Tae Kim

Richard Feyman --The Pleasure of Finding Things Out

Hope it helps !! 

2015 Mathcounts State/National Prep

Harder concepts from Mathcounts Mini :
Also try the follow-up problems with detailed solutions. Don't do every question. Just the ones you think is hard.

Geometry :
#27 : Area and Volume 

#30: Similar Triangles and Proportional Reasoning

#34: Circles and Right Triangles

#35: Using Similarity to Solve Geometry Problems

#41: Analytic Geometry : Center of Rotation

More questions to practice from my blog post. 

From Mathcounts Mini : Video tutorials on counting and probability for Mathcounts state/national prep concepts are in the of difficulty.

Counting the Number of Subsets of a Set

Constructive Counting

More Constructive Counting 

Probability and Counting

Probability with Geometry Representations  : Oh dear, the second half part is hilarious.

Probability with Geometry Representations : solution to the second half problem from previous video

Try this one from 1998 AIME #9. It's not too bad.

From Mathcounts Mink : Center of rotation, equal distance from a point to other two points or two lines, angle bisector (last problem on the follow-up worksheet)

Mathcounts Mini : #41 - Analytic Geometry