Transcript Counting Problems - Electrical and Computer Engineering

Counting Problems
A Lesson in the “Math + Fun!” Series
Feb. 2005
Counting Problems
Slide 1
About This Presentation
This presentation is part of the “Math + Fun!” series devised
by Behrooz Parhami, Professor of Computer Engineering at
University of California, Santa Barbara. It was first prepared
for special lessons in mathematics at Goleta Family School
during the 2003-04 and 2004-05 school years. The slides can
be used freely in teaching and in other educational settings.
Unauthorized uses are strictly prohibited. © Behrooz Parhami
Feb. 2005
Edition
Released
First
Feb. 2005
Revised
Counting Problems
Revised
Slide 2
Counting Is
Easy, Isn’t It?
How many tiles?
True, when the number of
things is small or the items
to count are neatly laid out
But it can be tricky or hard
How many animals
are there in this picture?
Feb. 2005
Counting Problems
Slide 3
How Not to Count
How many legs does
a cow have?
“A cow has 12 legs,
2 in front,
2 in back,
2 on each side, and
1 in each corner.”
– N.J. Rose
Feb. 2005
Counting Problems
Slide 4
Counting Squares: Easy Version
How many squares
can you find that
have four of these
dots in the corners?
Remove exactly
four dots so that
no square can be
formed with the
dots that remain.
Other answers?
Feb. 2005
Counting Problems
5 + 4 + 2 = 11
Slide 5
Counting Squares: Harder Version
How many
squares can you
find that have
dots in their
corners?
Remove exactly
six dots so that
no square can be
formed with the
dots that remain.
9 + 4 + 2 + 4 + 2 = 21
Feb. 2005
Counting Problems
Slide 6
How Many Squares Do You See?
4
1
4
4
1
4 + 4 + 4 + 1 + 1 = 14 squares
Feb. 2005
Counting Problems
Slide 7
Activity 1: How Many Triangles?
1
2
Hint: Count by side colors: 3 sides green (solid), 3 sides blue (dotted),
3 sides red (dashed), 2 sides green 1 side red, 2 sides green 1 side blue, . . .
Feb. 2005
Counting Problems
Slide 8
Activity 2: Counting Arrangements
In how many different ways can you arrange
the letters O, P, S, T? How many of these
arrangements form ordinary English words?
OPST
OPTS
OSPT
OSTP
OTPS
OTSP
POST
POTS
_____
_____
_____
_____
SOPT
SOTP
_____
_____
_____
_____
_____
_____
_____
_____
_____
_____
In how many different ways can you arrange
the letters O, P, T, T?
OPTT
OTPT
OTTP
_____
_____
_____
_____
_____
_____
_____
_____
_____
In how many different ways can you arrange
the letters O, T, T, T?
Feb. 2005
Counting Problems
The number of ways is:
4321
Can you explain this rule and
use it to find the number of
arrangements when there are
five distinct letters to arrange?
Explain your answer like the
previous puzzle and test it on
five letters with one repetition
(O, P, S, T, T)
Explain your answer like the
first puzzle and test it on
five letters with 2 repetitions
(O, P, T, T, T)
Slide 9
How Many Ways to Have 25¢ in Change?
5
and 5 
4
and 5 
3
and 10 
2
and 15 
1
and 20 
and 10 
and 15 
Feb. 2005
25 
13 different ways
Counting Problems
Slide 10
Activity 3: How Many Ways for 50¢ in Change?
10 
15 
5
5
4
5
and so on . . .
5
___ different ways
Feb. 2005
Counting Problems
Slide 11
Dividing Chocolate Bars
Interactive version at: http://www.cut-the-knot.org/ctk/memes/shtml
Divide an 8 x 4 chocolate bar into individual
pieces using the smallest number of breaks.
How many breaks did you need?
After 1
break
After 2
breaks
Feb. 2005
Counting Problems
After 3
breaks
After 4
breaks
Slide 12
A Couple of Smaller Examples
3
4
5
1
4
1
6
2
5
2
Each break increases the number
of pieces by 1.
So, to go from 1 piece to 6 pieces,
we need 6 – 1 = 5 breaks.
Feb. 2005
Counting Problems
3
7
Slide 13
Activity 4: Count the Digits
How many times does each digit 0-9 appears if we write down all
numbers from 1 to 20?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Two 0s, 3s, 4s, 5s, 6s, 7s, 8s , 9s
Three 2s
Twelve 1s
How many times does each digit 0-9 appears if we write down all
numbers from 1 to 100?
Answer the question without writing down all the numbers.
1 2 3 4 5 6 7 8 9 10
How many 0s?
How many 1s?
How many 2s?
How many 3s?
How many 4s?
Feb. 2005
____
____
____
____
____
.
.
How many 5s?
How many 6s?
How many 7s?
How many 8s?
How many 9s?
.
.
____
____
____
____
____
Counting Problems
.
.
.
.
.
.
100
Check your answers:
Add all the numbers,
and compare against
192. (Why 192?)
Slide 14
How Many Handshakes?
B
A
C
Three people can
shake hands in three
different ways.
A & B; A & C; B & C
What about
five people?
C
D
B
A
In how many
different ways
can four people
shake hands?
D
B
A&
B
B&
C&
6
Feb. 2005
E
A
C
C
D
C
D
D
The numbers
1, 3, 6, 10, ...
are known as
triangular
numbers
Counting Problems
A&
B
B&
C&
D&
10
C
D
E
C
D
E
D
E
E
Slide 15
Triangular Numbers
Pascal’s triangle
1
1
1
1
1
3
+
1
2
1
3
1
1
2
1
4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
Number of balls in each tier,
beginning from the top:
1, 4, 9, 16, 25, . . .
See if you can relate the numbers
shown on the right to numbers in
Pascal’s triangle above.
Feb. 2005
Total number of balls for
different numbers of tiers
1, 5, 14, 30, 55, . . .
Counting Problems
Slide 16
Routes on a Street Grid
A
Q
1
T
R
1
U
1
X
1
V
2
Y
1
3
AQUYZ B
AT UVZ B
AQR VWB
1
W
3
4
6
B
10
Z
AQRSWB
Feb. 2005
S
How many different ways are there
to get from point A to point B
if we want to use a shortest path?
Pascal’s triangle!
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Counting Problems
Slide 17
Activity 5: How Many Ways to Trace a Word?
N
(2) Do the same with the
word “SQUARES” below.
I
U
M
N
A
U
Q
S
Q
U
R
U
N
A
A
S
D
E
A
R
A
M
E
R
U
S
I
A
M
A
M
A
D
(3) Do the same with the word “MADAM,”
beginning from any of the four corners
and moving in any of the four directions.
A
M
D
Counting Problems
D
A
A
(4) Extra challenge: The same as (3), but
you can start from any of the seven Ms.
Feb. 2005
(1) Start from M on the left and
go to the S on the right, spelling
the word “MINUS.” In how many
different ways can you do this?
A
D
A
M
A
M
A
D
A
M
Slide 18
Counting by Estimation: Spectators in a Stadium
Feb. 2005
Counting Problems
Slide 19
Counting by Estimation: Cells Under a Microscope
Feb. 2005
Counting Problems
Slide 20
Tricky Counting: Count the Black Dots
Feb. 2005
Counting Problems
Slide 21
Next Lesson
Thursday, March 3, 2005
A problem to think about:
You have a 3-cup container and
a 5-cup container only. How do
you measure one cup of sugar?
Feb. 2005
Counting Problems
5
3
Slide 22