Sample questions for the midterm:
---------------------------------
1. How many bitstrings of length 10 have exaclty four zeros?
2. What is the coefficient of x^3*y^6*z^5 in (x+y+z)^14? Explain in
words why your answer is correct.
3. How many words of length 7 contain both ``a'' and ``b''?
4. In how many ways can 6 men and 8 women be lined up such that men
are not adjacent?
5. How many strings of 5 digits without repetitions contain 1 or 2 but
not both?
6. In how many ways can one travel from (0,0) to (8,11) going only
East or North, and while passing through (4,7) ?
7. How many strings of length 13, composed of the letters m, n, p, q
and no others, have exactly 3 p's and 4 q's?
8. How many words of length 6 are there when adjacent letters being
equal is not allowed?
9. How many solutions are there to x+y+z+w = 30 if x is between 5 and
10 and y is at least 6?
10. Find the probability of getting 3 of a kind but nothing better.
11. What is the probability that 2 people play poker against each
other and both get 4 of a kind?
12. On a die, 4 has probability 2/7, all others have 1/7. On a second
die, 3 has probability 2/7 and all others ahve 1/7. Find the
chance of rolling a 7 with this pair of loaded dice.
13. Toss a coin 10 times. Assume that head shows with 55 % in each
roll. Find the probability of getting at least 2 heads in the 10
rolls.
14. Imagine a casino has the following game.
Roll a fair die 3 times. You get $ 27 if you roll at least two
2's. Otherwise you get nothing.
Find the minimum price the casino should ask for playing this
game.
15. Find the recurrence for bitstrings that contain 0.
16. Find a recurrence for making a row of colored tiles, colors being
red, green, gray.
What if red tiles cannot be adjacent? What are the initial
conditions? (Note: how many strings are there of length zero?)
17. How many permutations of the English alphabet do contain ``fish''
but not ``rat''?
18. Prove by induction that 3*11^n + 2*6^n is divisible by 5.
19. Find a recurrence for the number of strings using the letters
a,b,c,d that do not have ``cd'' nor ``dd'' in them. (Hint: start
at the end.)
20. Solve a_n = 4*a_(n-1) -4*a_(n-2) with a_0=3, a_1=4.
21. Let f_i be the n-th Fibonacci number: f_0=0, f_1=1, f_2=1,...
Prove that f_1 + f_3 + f_5 + ... + f_{2n+1) = f_(2n+2).
22. Find the generating function for the sequence a_n where a_n is the
sum of the squares 1^2+...+ n^2.
23. Find the generating function for the Fibonacci sequence.
24. Prove or disprove: n^2-79n+1601 is a prime for all integral n.
25. Find all solutions to n^2-3n+3 mod 7. What about n^2-3n+5?
26. Find an inverse of 6 mod 53.
27. How many numbers between 1 and 10000 are not divisible by any of
5, 7, 11?
28. Solve the simultaneous congruences
a mod 17 =3,
a mod 5 =2
a mod 3 = 1.
29. Let p be a prime number, p>2. Prove that p(p-1)(p+1) is divisible
by 24.
30. Find the number of integers between 1 and 300 (including the ends)
whose gcd with 300 is 1. Repeat with "... is 2". (This is harder).
31. Find the gcd of x^6-9*x^5+28*x^4-30*x^3-11*x^2+39*x-18 and
x^6-13*x^5+69*x^4-191*x^3+290*x^2-228*x+72. (Coefficents are
allowed to be rational).
32. Find the gcd of 111 and 243 and express it as a linear combination
of 111 and 243.
33. Solve the simultaneous recurrence
a_n=3a_{n-1}+2b_{n-1}, b_n=a_{n-1}+2b_{n-1}, a_0=1, b_0-2.
34. A triangular number is t_n=1+2+...+n.
Find a recurrence for the sequence a_n given by
a_n=t_1+t_2+...+t_n.
35. Solve the recurrence from 34.
.