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.