HW7MA375S10 - Due Thursday, March 4th

6.4 - 6, 8, 12, 16 | 7.1 - 12, 24, 30, 36, 42, 44, 46

Section 6.4

6.

does the order of winning numbers set matter?

I don't think so. Typically, in a lottery, it's just a combination of numbers, not a permutation. For example, the combination "5, 10, 15, 20, 25, 30" would be the same as "30, 25, 20, 15, 10, 5."

So would it just be the 1 over the number of ways that we can make a 5 bit string out of 50 numbers?

Yes, but you also have to consider the expected lost. And sum both of it.

8.

12.

I figured out the probability, but got a little confused about the expectation. Any hints? thanks

Hint: it's a geometric distribution. See pages 433-434 - specifically, Theorem 4 on page 434.

16.

Section 7.1

12.

Is there really ANY way to do this with counting principles? If we look at the total number of bit strings of length n with 3 consecutive zeros, for n = 3, 4, 5, and 6, we see 1, 3, 8, and 20. (It's 0 for any n < 3, of course.) Is there really a pattern there? Even if you look at the increments, it goes +1, +2, +5, +12; there is no discernible pattern, unless I'm just missing it. Any help?

Are you referring to problem 24 in section 7.1? Problem 12 does not refer to any bit strings. I take it you wish to solve the problem of finding a recurrence that describes the number of bit strings of length n which have three zeros in a row.

You are exactly right that there is no discernible pattern. That is exactly the point. In problems like these we ordinarily run a few experiments and try to figure out the pattern, but we can't do that here. You need to take an alternative route to figuring out the pattern, which is where recursion comes into play. It is generally easier to figure out how the present configuration of the system dictates the subsequent state, rather than coming up with a general rule that gives you the state of the system for any iteration.

For this problem you need to construct a tree. You wish to discover a_n. Consider investigating the first digit of the sequence. There are only two possibilities: either the bit is a zero or it is a one. If it is a one, then imagine snipping that digit off. You now have a sequence of length n-1, and you are asking yourself the same question: how many sequences of this length (n-1) have 3 consecutive zeros? This is a_(n-1). On the other hand, if the digit is a zero, then you must snip it off and move onto the next digit. Repeat and exhaust all the possibilities.

^ Thank you very much! I had forgotten that he had done something very similar in class, but with 2 consecutive 0's instead of 3. Makes sense to me!

24.

See #12, cuz I'm a dumbass and put my question about #24 up there instead. ^^

30.

36. I'm totally lost, help please.

I broke down how many ways can 10 cents, 15 cents, and 20 cents be paid using tree diagram. Then, find the recurrence relation of a20 with respect to the others.

42.

Does anyone have any advice for this one?

When the top right domino is horizontal, you have a_(n-1) ways to permute. When it is vertical, you have a_(n-2) ways. This partitions all the possibilities so it should be clear what to do from there.

Did you mean when the top right domino is VERTICAL, you have a_(n-1) ways, and when it is HORIZONTAL you have a_(n-2) ways? That's what I seem to be seeing anyway... (Obviously, it doesn't affect the solution of the problem, just the theory behind it; the recurrence relation is the same.)

44. any idea about showing f5n is divisible by 5?

Use induction

I don't know if induction would work here, but you can do it like listing out fn, f(n-1), f(n-2), f(n-3) and substitute from those backwards. And you should see what you wanted to prove. And that's the first part.

Then you list out f(n=5), and you have f5 = 5f1 + 3f0, you get the result. then you list f10, and f15. you see that in f10, it's 5f(6) + 2f(5), but you already know f(5) is divisle by 5 the first try. Then 5f(6), you don't care what f(6) is but it is a multiple of 5 so obviously is divisible by 5, then the sum of both is f10, and f10 is divisible by 5 too. As you move along, you will notice that it is also using a previous value which you already know is divisible by 5 and summing that up with a multiple of 5. Then you know all of them are divisible by 5.

46. i got 9 ways to parenthize x_0-x_4. is this correct because part B is confusing.

I don't think that's right. You can use the explicit formula in the example to find the correct number (part c).

I got 9 ways to parenthize also, so help us out. The example isn't working for us or we wouldn't ask. Thanks!

I'm getting 12 ways. 4 of them end with an x_4 outside of all parentheses; four of them start with an x_0 outside of all parentheses; 2 of them involve (x_0 * x_1); and 2 of them involve (x_3 * x_4). I don't know if I'm right, but hopefully I am, and hopefully that helps!

^ EDIT: Just did part b, and if I did it right, the answer is 14. That means I originally missed two ways in part a. I think I found them, though. There should be a total of 5 ways that end with an x_4 outside of all parentheses, and 5 ways that start with an x_0 outside of all parentheses.