Pathfinder

From Mathcounts Mini :

Counting/Paths Along a Grid

From Art of Problem Solving

Counting Paths on a Grid 

Math Principles : Paths on a Grid : Two Approaches 

Question #1: How many ways to move the dominoes on a 6 by 6 checker board if you can only move the dominoes to the right or to the bottom starting from the upper left and you can't move the dominoes diagonally? 

Solution :
You can move the dominoes 5 times to the right at most and 5 down to
the bottom at most, so the answer is \(\dfrac {\left( 5+5\right) !} {5! \times 5!}\) = 252 ways

Question # 2: How many ways can you  move from A to B if you can only move downward and to right? 

Solution : There are \(\dfrac {\left( 4+4\right) !} {4!\times 4!}\) * 2 * \(\dfrac {\left( 4+4\right) !} {4!\times 4!}\) = 9800 ways from A to B

Unit digit, Tenth digit and Digit Sum

Word problems on unit digit, tenth digit or digit sum.

#1: How many digits are there in the positive integers 1 to 99 inclusive? 

Solution I:  From 1 to 9, there are 9 digits.
From 10 to 99, there are 99 - 10 + 1 or 99 - 9 = 90 two digit numbers. 90 x 2 = 180
Add them up and the answer is 189.

Solution II:  ___ There are 9  one digit numbers (from 1 to 9).
___ ___ There are 9 * 10 = 90 two digit numbers (You can't use "0" on the tenth digit but you
can use "0" on the unit digit.) 90 * 2 + 9 = 189

# 2: A book has 145 pages. How many digits are there if you start counting from page 1?

There are 189 digits from page 1 to 99. (See #1, solution I)
From 100 to 145, there are 145 - 100 + 1 or 145 - 99 = 46 three digit numbers.
189 + 46*3 = 327 digits.

#3: "A book has N pages, number the usual way, from 1 to N. The total number of digits in the page number is 930. How many pages does the book have"?  Similar to one Google interview question.

Read the questions and others here from the Wall Street Journal.

Solution I: 

930 - 189 (digits of the first 99 pages) =741
741 divided by 3 = 247. Careful since you are counting the three digit numbers from 100 if the book has N
pages N - 100 + 1 or N - 99 = 247. N = 346 pages.

Solution II: 

930 - 189 (total digits needed for the first 99 pages) = 741
741/3 = 247 (how far the three digit page numbers go).
247 + 99 = 346 pages

#4: If you write consecutive numbers starting with 1, what is the 50th digit you write? 

Solution I:
50 - 9 = 41, 9 being the first 9 digits you need to use for the first 9 pages.

Now it's 2 digit. 41/2 = 20.1 , which means you will be able to write 20 two digit numbers + the first digit of the next two digit numbers.

10 to 29 is the first 20 two digit numbers so the next digit 3 is the answer. (first digit of the two digit number 30.)

Solution II: (50 - 9 ) / 2 = 20. 5 ; 20.5 + 9 = 29.5, so 29 pages + the first digit of the next two digit numbers, which is 3, the answer.


#5: What is the sum if you add up all the digits from 1 to 100 inclusive?

00  10  20  30  40  50  60  70  80  90

01  11  21  31  41  51  61  71  81  91

02  12  22  32  42  52  62  72  82  92

03  13  23  33  43  53  63  73  83  93

04  14  24  34  44  54  64  74  84  94

05  15  25  35  45  55  65  75  85  95

06  16  26  36  46  56  66  76  86  96

07  17  27  37  47  57  67  77  87  97

08  18  28  38  48  58  68  78  88  98

09  19  29  39  49  59  69  79  89  99

Solution I:
Do you see the pattern?  From 00 to 99 if you just look at the unit digits.
There are 10 sets of ( 1+ 2 + 3 ... + 9) , which gives you the sum of 10 * 45 = 450
How about the tenth digits? There are another 10 sets of (1 + 2 + 3 + ...9) so another 450
Add them up and you have 450 * 2 = 900 digits from 1 to 99 inclusive.
900 + 1 ( for the "1" in the extra number 100) = 901 

Solution II:
If you add the digits on each column, you have an arithmetic sequence, which is
45 + 55 + 65 ... + 135  To find the sum, you use average * the terms (how many numbers)
\(\dfrac {45+135} {2} * \left( \dfrac {135-45} {10}+1\right)\) =900
900 + 1 = 901

Solution III :
2*45*10¹ + 1 = 901


Problems to practice: Answers below.

#1: A book has 213 pages, how many digits are there?

#2: A book has 1012 pages, how many digits are there?

#3: If you write down all the digits starting with 1 and in the end there are a: 100, b: 501 and c: 1196 digits, what is the last digit you write down for each question?

#4: What is the sum of all the digits counting from 1 to 123? 

Answers: 

#1: 531 digits. 

#2: 2941 digits.

#3: a. 5, b. 3, c. 3

#4: 1038 

Notes to Sunday Nights' Problem Solving Group Lessons

This week's work : Please review the last 8 hardest AMC-8 problems from 2005 to 2011 + finish the last 8 hardest AMC-8 problems from 2012 and 2013 if you haven't done that.

Some notes and questions.

Question #1 : How many ways can you climb up a ten-step staircase if you climb only one or two steps at a time ?

Solutions I :
Make a chart, starting with a smaller case.
one-step staircase -- 1 way, which is 1.
two-step staircase -- 2 ways, which is 1, 1 or 2.
three-step staircase -- 3 ways, which is 1 1 1, 1 2 or 2 1.
four-step staircase -- 5 ways, which is 1111, 211, 121, 112, 2222.

Notice the pattern - - 1 , 2, 3, 5, 8, 13, 21, 34, 55, 89, which is the answer; it also happens that it's
part of the Fibonacci numbers.

Why does it work that way ?

Well, if you climb the 3-step staircase, there are two cases :
You either take one step at first, and there are 2-step left, which leaves you two ways to climb the remaining staircase.
Or you take two step at first, and there are 1 step left, which leaves you one way to climb the remaining staircase.
If you climb the 4-step staircase, again, there are two similar cases :
You either take one step at first, and  then there are 3-step left, which leaves you 3 ways to climb the remaining staircase.
Or you take two step at first, and there are 2 step left, which leaves you 2 way to climb the remaining staircase.

Thus, it's always the sum of the previous two terms for the next staircase steps.
This concept is called recursion.

Now try another question :
2010 AMC-8 #25 : Every day at school, Jo climbs a flight of 6 stairs. Joe can take the stairs, 1, 2 or 3 at a time. For example, Jo could climb, 3, then 1, then 2. In how many ways can Jo climb the stairs ?

Solution I :
List out all the possible ways.
111111  -- 1 way
21111 -- 5C1 = 5 ways to arrange the steps
2211 -- 4!/2! x 2! = 6 ways to arrange the steps
222-- 1 way
3111 -- 4C1 or 4 ways to arrange the steps
123 -- 3! or 6 ways
33 -- 1 way
Sum them up and the answer is 24.

Solution II :
Using recursion, starting with the smallest case.
1 step -- 1 way
2 steps-- 2 ways (11, or 2)
3 steps -- 4 ways (111, 21, 12, or 3)
4 steps -- 1 + 2 + 4 = 7 ways (why??)
5 steps -- 2 + 4 + 7 = 13 ways.
6 steps -- 4 + 7 + 13 = 24 ways, which is the answer.

Besides these, please review the following questions.

Answer key below.

Q #1  1988 AMC-8 #25 : A palindrome is a whole number that reads the same forwards as backwards. If one neglects the colon, certain times displayed on a digital watch are palindromes. Three examples are 1: 01, 4: 44 and 12: 21. How many times during a 12-hour period will be palindromes?

Q#2  2004 Mathcounts sprint  #21: If |-2a + 1| < 13, what is the sum of the distinct possible integer values of a?

Q#3  2004 Mathcounts sprint #30 : A particular right square-based pyramid has a volume of 63,960 cubic meters and a height of 30 meters. What is the number of meters in the length of the lateral height (AB) of the pyramid? Express your answer to the nearest whole number.










Answer key :

#1 : 57

#2 : 6

#3 : 50

Counting I : Ways to Avoid Over Counting or Under Counting

Check out Mathcounts here, the best competition math program for middle school students.
Download this year's Mathcounts handbook here.

Question #1: How many ways to count a triple of natural numbers whose sum adds up to 12 
if  A. order doesn't matter? B. if order matters?

Solution I:
A. Find a systematic way to solve this type of problem in an organized manner.
We can start with the smallest natural number "1".
(1, 1, 10), (1, 2, 9), (1, 3, 8), (1, 4, 7), (1, 5, 6)  Since (1, 5, 6) is the same as (1, 6, 5) so stop.
(2, 2, 8), (2, 3, 7), (2, 4, 6), (2, 5, 5)
(3, 3, 6), (3, 4, 5)
(4, 4, 4) so total there are 12 ways.

B. Since in this case order matters so if you add up all the possible ways, for example, there are "3" ways to arrange (1, 1, 10) -- 3!/2! = 3
This is similar to "how many ways to arrange the letters 'odd'.
If all letters/numbers are different, you have 3! ways to arrange them; however, in this case, the two numbers 1, 1 are indistinguishable and there are 2! ways to arrange them, thus 3!/2! = 3

There are 3! or 6 ways to arrange triples such as (1, 2, 9).
Add all the possible ways and there are total 55 ways.

Solution II:
B.There is a much easier way to tackle this question, using bars and stars or sticks and stones method.
There are 11 spaces between 12 stones. @__@__@__@__@__@__@__@__@__@__@__@
If you places the two sticks on two of the spaces, you'll split the stones into three groups.
For example, if you have @ | @@@@@ | @@@@@@
The triples are 1, 5, and 6.
If it's @@@@@@@@ | @@ | @@ , the triples are 8, 2, and 2.
So 11C2 = 55 ways

Let me know if you are still confused.  Have fun problem solving !!

Counting II : Practice Counting Systematically

Counting Coins 
Lots of similar questions appear on Mathcounts tests. Be careful when there are limits, for example, the sum of the coins do not exceed ___ or you have to have at least one for each type, etc...

Partition 

The Hockey Stick Identity from Art of Problem Solving
Same as "Sticks and Stones", or "Stars and Bars" methods

Applicable question: Mathcounts 2008 Chapter #9--During football season, 25 teams are ranked by three reporters (Alice, Bob and Cecil). Each reporter assigned all 25 integers (1 through 25) when ranking the twenty-five teams. A team earns 25 points for each first-place ranking, 24 points for each second-place ranking, and so on, getting one point for a 25th place ranking. The Hedgehogs earned 27 total points from the three reporters. How many different ways could the three reporters have assigned their rankings for the Hedgehogs? One such way to be included is Alice - 14th place, Bob - 17th place and Cecil - 20th place.

Solution I :
Let's see how it could be ranked for Hedgehogs to get 27 points from the three reporters.

A          B         C

1           1        25     1 way for C to get 25 points and the other two combined to get 2 points

1           2        24

2           1        24    2 ways for C to get 24 points and the other two combined to get 3 points.

1           3        23

3           1        23

2           2        23    3 ways for C to get 23 and the other two combined to get 4 points.

.

.

25        1         1     25 ways for C to get 1 point and the other two combined to get 26 points.

1 + 2 + 3 + ...25 = \(\dfrac {25\times 26} {2}=325\)

Solution II:

Use 26C2. Look at this questions as A + B + C = 27 and A, B C are natural numbers. To split the objects into three groups (for Alice, Bob, and Cecil), we must put 2 dividers between the 27 objects. (You can't grant "0" point.) There are 26 places to put the dividers, so 26C2 and the answer is \(\dfrac {26\times 25} {2}=325\)

2013 Mathcounts State Prep: Counting and Probability

Question #1: Rolling two dice, what is the probability that the product is a multiple of 3?
Solution I :
As long as one of the two numbers turn up as 3 or multiple of 3 (in this case, a "6"), the product of the two numbers will be a multiple of 3.
There are 6 * 6 = 36 ways to get 2 numbers. Out of the 36 pairs, you can have
3 - 1
3 - 2
3 - 3
3 - 4
3 - 5
3 - 6, 6 ways.
However, there are only 5 ways left if the other die has a 3 since 3 - 3 only counts as once.
1 - 3
2 - 3
4 - 3
5 - 3
6 - 3
Next we look at "at least one number is "6".
6 - 1
6 - 2
6 - 4 (We already used 6 - 3)
6 - 5
6 - 6 so 5 ways.
The other way around, we have
1 - 6
2 - 6
4 - 6
5 - 6  Total 4 ways, so the answer is \(\frac{\Large{( 6 + 5 + 5 + 4 )}}{\Large{36}}\) = \(\frac{\Large{ 20}}{\Large{36}}\) = \(\frac{\Large{5}}{\Large{9}}\).

Solution II: 
The easiest way to solve this problem is to use complementary counting, which is 1 (100% or total possible way) - none of the the multiples of 3 showing up, so 1 - \(\frac{\Large{4}}{\Large{6}}\) *\(\frac{\Large{4}}{\Large{6}}\) = 1 - \(\frac{\Large{2}}{\Large{3}}\) * \(\frac{\Large{2}}{\Large{3}}\)=  \(\frac{\Large{5}}{\Large{9}}\)

Question #2: [2002 AMC-12B #16] Juan rolls a fair regular eight-sided die. Then Amal rolls a fair regular six-sided die. What isthe probability that the product of the two rolls is a multiple of 3?
Solution:
Using complementary counting (see solution II of the previous question), 1 - \(\frac{\Large{6}}{\Large{8}}\) *\(\frac{\Large{4}}{\Large{6}}\) = 1 - \(\frac{\Large{3}}{\Large{4}}\) * \(\frac{\Large{2}}{\Large{3}}\)=  \(\frac{\Large{1}}{\Large{2}}\)