1 Problems - University of California, Berkeley

Math 10B with Professor Stankova Worksheet, Midterm #1; Wednesday, 2/27/2019 GSI name: Roy Zhao

1 Problems

1. How many ways can you rearrange the letters in BERKELEY?

Solution: There are 8 letters but 3 E's and no other letters repeat. So the answer

is

8! 3!

.

2. There are 72 students trying to get into 3 of my sections. There are 27, 20, 25 openings respectively. How many ways are there for these students to enroll?

Solution:

72 27

72-27 20

72-27-20 25

=

72 27

45 20

.

3. Prove that for all n 1.

1 + 3 + 9 + ? ? ? + 3n = 3n+1 - 1 2

Solution:

The base case is true since 1 =

3-1 2

.

Then assuming the inductive hy-

pothesis for some n 1, we see that

1+

3

+

???+

3n

+

3n+1

=

3n+1

-

1

+

3n+1

=

3

?

3n+1

-1

=

3n+2

-1 .

2

2

2

Thus, by mathematical induction, the result is shown for all n 1.

4. How many ways can I put 20 Tootsie rolls into 5 goodie bags so that each goodie bag has at least 2 Tootsie roll?

Solution: Put one in each then there are 15 rolls left and 5 bags and everything is indistinguishable so p5(15).

Math 10B with Professor Stankova

Wednesday, 2/27/2019

5. Show that when you place 9 coins on an 8 ? 10 boards, at least two coins must be on the same row.

Solution: PP, 9/8 > 1.

6. How many different three-letter initials contain A?

Solution: We use complementary counting to get 263 - 253.

7. How many license plates with 3 digits followed by 3 letters do not contain the both the number 0 and the letter O (it could have an O or a 0 but not both).

Solution: Complementary counting. Bad cases are if it has an O and a 0. There are 263 - 253 ways to have a O, there are 103 - 93 ways to have a 0. So the final

answer is 103 ? 263 - (103 - 93)(263 - 253).

8. Prove that

n-1 r-1

+

n-1 r

=

n r

in two different ways.

Solution: We can first prove it algebraically by

n-1

n-1

(n - 1)!

(n - 1)!

+

=

+

r-1

r

(r - 1)!(n - r)! r!(n - r - 1)!

1

(n - 1)!

1

(n - 1)!

=

+

n - r (r - 1)!(n - r - 1)! r (r - 1)!(n - r - 1)!

r+n-r

(n - 1)!

=

r(n - r) (r - 1)!(n - r - 1)!

n!

n

=

=.

r!(n - r)! r

Then, to prove it combinatorially, we see that the right side is just choosing a team

of r people out of n total people. We can do this by first distinguishing one person

out, say Zvezda. Then, if she is on the team, out of the remaining n - 1 people, we

still need to choose r - 1 which can be done in

n-1 r-1

ways. Otherwise, if she is not

on the team, we still need to choose r people which can be done in

n-1 r

ways. Since

both count the number of ways, the left and right side are equal.

Math 10B with Professor Stankova

9. Prove that

n k=0

5k

n k

= 50

n 0

+ 51

n 1

+ ? ? ? + 5n

n n

= 6n.

Wednesday, 2/27/2019

Solution: Use the Binomial theorem and plug in x = 1, y = 5.

10. How many ways can I split up 30 distinguishable students into 6 groups each of size 5?

Solution:

30! 5!5!5!5!5!5!

.

11. Find a formula for 1 + 2 + 4 + ? ? ? + 2n and prove it.

Solution: The answer is 2n+1 - 1 and use induction to prove it.

12. How many 5 digit numbers have strictly increasing digits (e.g. 12689 but not 13357).

Solution:

9 5

.

13. How many permutations of the letters ABCDEF G contain the string ABC and GF E? What about containing ACB and CBE?

Solution: We block them together so we need to permute (ABC), (GF E), D which is 3! = 6 ways.

For the second, if it contains ACB and CBE, it must contain ACBE so we then need to sort (ACBE), D, F, G which can happen in 4! = 24 ways.

14. How many 5 digit numbers have increasing digits (you can have repeats e.g. 12223 or 22222)?

Solution:

13 5

.

15. A 7 phone digit number d1d2d3 - d4d5d6d7 is called memorable if d1d2d3 = d4d5d6 or d1d2d3 = d5d6d7. How many memorable phone numbers are there?

Math 10B with Professor Stankova

Wednesday, 2/27/2019

Solution: We use PIE. There are 103 ? 10 for each way and then we need to subtract the intersection. If d1d2d3 = d4d5d6 = d5d6d7, then d4 = d5 = d6 = d7 = d1 = d2 = d3 and so the intersection is if its a phone number with everything repeating. Therefore, there are 10 numbers in the intersection. This gives a total of

2 ? 103 ? 10 - 10

ways.

16. How many 6 element RNA sequences end with GU?

Solution: Once the GU is fixed, there are 4 more elements to choose and 4 choices for each so 44.

17. How many people do you need in order to guarantee that at least 3 have the same birthday?

Solution: 366 2 + 1.

18. How many 5 letter words have at least two consecutive letters are the same?

Solution: We need to use complementary counting. The bad ways is if there are no two consecutive letters the same. There are 26 ? 254 ways to do this. So the answer is 265 - 26 ? 254.

19. Prove that 1 + 3 + 5 + ? ? ? + (2n - 1) = n2 for all n 1.

Solution: Induction.

20.

Prove

that

1 ? 2 + 2 ? 3 + 3 ? 4 + ? ? ? + n ? (n + 1) =

n(n+1)(n+2) 3

for

all

n

1.

Solution: The result is true for n = 1. Now assume true for some n. Then

n(n + 1)(n + 2)

1 ? 2 + ? ? ? + n ? (n + 1) + (n + 1)(n + 2) =

+ (n + 1)(n + 2)

3

n(n + 1)(n + 2) + 3(n + 1)(n + 2) (n + 3)(n + 1)(n + 2)

=

=

.

3

3

Thus by mathematical induction, the result is true.

Math 10B with Professor Stankova

Wednesday, 2/27/2019

21. How many ways can I put 60 seeds in 10 indistinguishable boxes so that each box has at least 3 seeds?

Solution: First put two seeds in the 10 boxes which leaves 40 left and each box needs to have at least one. So there are p10(40) ways.

22. How many positive integers between 1 and 1000 are divisible by 3 but not by 4?

Solution: There are a total of

1000 3

= 333 numbers divisible by 3. Then we

subtract the ones divisible by 3 and 4 which are the ones divisible by 12 to get

1000 12

= 83 and a total of 333 - 83 = 250 numbers.

23. I have 4 indistinguishable blue coins and 4 indistinguishable gold coins. How many ways can I stack them?

Solution:

8 4

.

24. What is the coefficient of x7y9 in the expansion of (2x - 5y)16?

Solution: The term is

16 7

(2x)7(-5y)9

=

16 7

27(-5)9x7y9.

25. When I go to CREAM, I order 4 scoops of ice cream out of 10 possible flavors (I can get more than one scoop of a flavor)?

Solution:

13 4

.

26. About 1 in a million Americans play in the NBA. Suppose that 90% of NBA players are very tall and 2% of all other Americans are very tall. What is the probability someone is in the NBA given that they are very tall?

Solution: We have that

P (T all|N BA)P (N BA) P (N BA|T all) =

P (T all|N BA)P (N BA) + P (T all|N otN BA)P (N otN BA)

0.9 ? 1/106

=

0.0045%.

0.9 ? 1/106 + 0.02 ? (1 - 1/106)

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download