Contents
MA375: Midterm Page
Fall 2008, Prof. Walther
The midterm is Tuesday, October 28th. Here is a list of example midterm questions.
Discussion
What did everyone think of the exam? --Djallen 20:41, 28 October 2008 (UTC)
I didn't know how to do the last one in one line. I think I gave a valid explanation, but it took a lot more than one line. Anyone have any ideas? --Dakinsey 14:05, 29 October 2008 (UTC)
- Mine took about three lines... I don't know what that means. --Kduhon 16:33, 29 October 2008 (UTC)
- You could prove that a_n = 3 * a_n-1 by induction (a_1 = (1 choose 1)(1 choose 1) + (1 choose 1)(1 choose 0) + (1 choose 0)(0 choose 0) = 1 + 1 + 1 = 3, etc.), with the initial condition a_0 = 1. Then you can solve the simple homogeneous recurrence and obtain a_n = 3^n. Another way is to notice that for each fish you either don't catch it, catch it and don't eat it, catch it and eat it: 3 choices. There are n fish, hence, the total # ways to do that is 3^n (number of permutations with repetitions). --Asuleime 17:21, 29 October 2008 (UTC)
- I started a midterm solutions page if anyone wants to contribute. If it already exists somewhere, just delete it and stick it somewhere else.
I thought the exam was pretty good. It was nice a lot of the difficult recurrence relations stuff wasn't on there.
My guess is his one line response would go something like ("Each fish is either eaten, caught but not eaten, or uncaught") but that would ignore significant details.--Norlow 18:10, 31 October 2008 (UTC)
Questions and Solutions to Sample Problems
Question: For the midterm we are allowed to complete one page with notes. Does anyone know if this must be hand written or can it be typed?
Answer: As mentioned today in class(10/21), we are allowed to complete one full page, 8.5x11", worth of cheat sheet. This can be typed, handwritten, crayon, etc. In addition, we may use any sort of calculator.
Question 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).
By the sequence, we initially see f_(2n+2) = f_(2n+1) + f_(2n). Since we are asked to prove something of the form f_(2n+2) = f_(2n+1) + [blah], we will assume the objective is true, and try to iron out f_(2n) to match. So, let's expand f_(2n): f_(2n) = f_(2n-1) + f_(2n-2). So, we have f_(2n+2) = f_(2n+1) + f_(2n-1) + f_(2n-2). We begin to see a pattern -- expanding an even-numbered subscript gives us an odd-numbered subscript and another even-numbered subscript to expand later. It would seem like we would end up with something like what we are trying to prove.
How can we prove this, though? The first thought that comes to mind would just be to write a sequence of expansions out as we were doing, add a couple of dots ("..."), and toss the solution at the end. However, that's not terribly rigorous. So, let's try to use induction instead:
Base case: Let n = 0. f_2 = f_1 + f_0 = f_1 (since f_0 = 0) by the definition of Fibonacci numbers, and f_2 = f_1 by the proposed recursion.
Inductive step: Assume that for a given integer n that f_1 + f_3 + f_5 + ... + f_(2n+1) = f_(2n+2). We want to show that f_1 + f_3 + f_5 + ... + f_(2n+1) + f_(2n+3) = f_(2(n+1)+2) = f_(2n+4). f_(2n+4) = f_(2n+3) + f_(2n+2) (by the Fibonacci sequence [Remember a couple of paragraphs ago? This was our initial plan.]) = f_(2n+3) + f_(2n+1) + ... + f_5 + f_3 + f_1 (by assumption [...and this is what makes the proof mathematically rigorous instead of "here's some '...'s, you get the idea"-based]).
Thus, for all integer n ≥ 0, f_1 + f_3 + f_5 + ... + f_(2n+1) = f_(2n+2).
Question 5
Can someone verify that I'm interpreting/doing this question right? I assume without repetitions means we can't have 11111, 22222, 11134, 23359 etc. The number of strings with 1 but not 2 is equal to the number of strings with 2 but not 1, so you just find one answer and double it. The number of strings with 1 but not 2 should be the number of ways to arrange the the digits 3-9 and 0 in the 4 remaining places. But since the 1 can go in any place, we multiply this by 5. So my answer is 2*5*(8*7*6*5) = 16800. Anyone else get this? --Mkorb 20:56, 26 October 2008 (UTC)
Question 5 Yes... your answer is right. This question is exactly like #40c on the second assignment (section 5.1). I say exactly but you have to look at it for a moment to realize that you are essentially doing the same thing. The way I did that problem was by thinking: There is (8 choose 3)5! ways for both 1 & 2 to occur together. This is counted in both of these as well: (9 choose 4)5! ways for 1 to occur and (9 choose 4)5! ways for 2 to occur. Soo, it must also be subtracted twice(9 choose 4)5! + (9 choose 4)5! - [2*(8 choose 3)5!] = 16800. The h/w problem i referred to was the bride/groom/photographer question: how many ways can photographer arrange 6 people from 10 when the bride & groom are members of the 10 & one of the 2 must be in the arrangement? Change this to how many ways can photographer arrange 5 people from 10 when 1 & 2 are members of 0-9 & 1 or 2 must be in the arrangement?--Ehanna 22:52, 26 October 2008 (UTC)
Question 17
Question 17 asks how many permutations of the alphabet contain "fish" but not "rat." I think the simplest way to do this is count the number of permutations that contain "fish" and subtract the number that contain both "fish" and "rat." Treating "fish" like it is one letter, we get 23! permutations of "fish" and the remaining 22 letters. For the intersection, treat "fish" as one letter and "rat" as one letter, so there are 21! permutations of fish, rat, and the remaining 19 letters. My answer is 23! - 21!. Did I do this right? --Mkorb 18:39, 27 October 2008 (UTC)
Yes I believe this is the correct method and solution. --ysuo 22:59, 27 October 2008 (UTC)
Is there going to be a review session for this midterm? --Podarcze 12:06, 26 October 2008 (UTC)
Wasn't the review session during thursday's class?
-I meant study session. I know people have been getting together to do homework on monday's and I was wondering if they are doing it this week. --Podarcze 21:05, 26 October 2008 (UTC)
Materials to Study
Would it be enough to study the HW and the sample questions? -Wooi-Chen Ng
I think we still have to read and study the notes that the professor gave us during class. I think it's helpful too since many examples were done during class time.--hussaini 19:48, 26 October 2008 (UTC)
Question 16
I'm a bit confused on the wording of this problem. What does it mean to find a recurrence for the colored tiles? Is it just $ a_n = 3^n $ for the first part? And does anyone know how to go about doing the second part, where you can't have red tiles adjacent?
