Sample questions for the 375 Final
* 11.1: 28,31,47 | 11.4: 1,9,33,39,44 | 11.5: 8.
* Give a recurrence and initial condition for the number of ternary
strings that contain 3 or more consecutive zeros.
* Solve a_n = 5*a_{n-1} - 4*a_{n-2} +3*2^n with a_0=1, a_1=10.
* 100 lottery tickets are distributed, only 2 of them have a
prize. Rupert Murdoch buys n of these tickets (n of course is some
number between 0 and 100). What is the probability that Murdoch wins
both prizes?
* Suppose G is a strongly connected directed graph. Prove that there
is a directed path in the graph that passes through all vertices.
* Let f_n be the n-th Fibonacci number: f_1=f_2=1, f_n=f_{n-1} +
f_{n-2}. For any given natural number m, express f_1+f_2+...+f_m in
terms of exactly _one_ Fibonacci number. (You have to find out,
_which_ one.)
* How many binary strings start with 011, or end with 110, or have 0
as both first and last digit, or have any combination of these
properties?
* Atlantic City has introduced the following game: the casino randomly
draws a permutation of the number 1,...,n. Then the casino counts
the "number of fixed points" of this permutation. (A fixed point is
a number that does not move under the permutation. For example, if
the permutation is (1,3,5,4,2) then fixed points are 1 and 4 because
1 remains in position 1 and 4 remains in position 4).
For each fixed point you will get one dollar.
What should the casino charge as fee for the game in order to
balance win and loss?
* What is the coefficient of a^5*b^3*c^2 in (a+b+c)^10?
* I roll a pair of fair dice 20 times. You get $3 if at least 3 times
of the 20 a sum of 5 is rolled. You pay $4 if a sum of 5 shows
never, once, or twice.
Should you play this game?
* A slot machine can display the numbers 1, 2 or 3. 1 has probability
0.1, 2 has probability 0.3, and 3 has probability 0.6.
The machine is run 10 times, and the numbers that show are added. At
the end you get as many dollars as the sum indicates. What are the
expected winnings?
* Use induction to prove that if n is at least 2 then
(1 - 1/4)*(1 - 1/9)*...*(1 - 1/n^2) = (n+1)/(2*n).
* Legend has it that the king of India wanted to reward the man who
invented chess. He offered to him 20000 pounds of wheat. The man
replied humbly that he would be content to receive 1 grain of wheat
for the first square of the chessboard, 2 for the second, 4 for the
third, 8 for the fourth, and so on.
The king replied that in this case he would in addition give the man
2 elephants.
However, instead of receiving the reward, the man was thrown to the
tigers. Why?
* Find a graph with 6 vertices whose degrees are 5,5,3,3,2,1.
* Find two graphs that are not isomorphic but that do have the same
number of vertices, and for which the sequence of degrees is the
same.
* If you are given the adjacency matrix of a graph and a computer, but
no paper to draw the graph, how can you test whether the graph is
connected or not?
* Repeat the previous question with a directed graph.
* Suppose G is simple with n vertices and more than N=(n-1)(n-2)/2
edges. Prove that G is connected. (Hint: suppose it splits into 2
pieces. Estimate the number of edges in each component, and play it
off against N.)
* Suppose you place two tetrahedra of slightly different sizes inside
each other. Then link the corresponding vertices that are "above
each other". Is there an Euler circuit in this graph? If "yes", find
one. Repeat the question, replacing "tetra" by "octa".
* Suppose G is a bipartite graph on 61 vertices. Show that G does not
have a Hamilton circuit.
* Show that in a simple graph with at least 2 vertices there is a pair
of vertices with equal degree..
* Prove that a simple graph with 15 vertices and 40 edges cannot be
planar.
* Prove that a bipartite simple graph with 15 vertices and 27 edges
cannot be planar.
* Give an example of a bipartite simple planar graph with 15 vertices
and 26 edges. Give an example of a simple planar graph with 15
vertices and 39 edges.
* Find the chromatic polynomials of the graph of exercise 1 on
page 703.
* What can you say about the chromatic polynomial of a graph that
contains K_n?
* Take the edge graph of an icosahedron, number the edges in any way
you like, interpret the numbers as weights, and then find a minimal
weight spanning tree in the resulting weighted graph.
* Using the weights you used in the previous exercise, find a shortest
path from the north pole to the south pole on the icosahedron.