3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

clooneyisagenius · 2007-04-03 11:42:56

1. Let A1, A2, ... be a sequence of sets, each of which is countable. Prove that the union of all the sets in the sequence is a countable set.

2. When rolling n dice, what is the probability that the sum of the numbers obtained is even. (Note: this does not assume any number of dice in particular. More importantly, not 2 dice.)

3. Use Pascal's Formula to prove by induction on n that (n choose k) = n!/(k!(n-k)!) when 0<=k<=n and (n choose k)=0 otherwise. Assume that (0 choose 0)=1 and (0 choose k)=0 when k is not 0.

Help on any or all of them would be great! I appreciate it! Thanks!

pi man · 2007-04-03 15:35:11

2. When rolling n dice, what is the probability that the sum of the numbers obtained is even. (Note: this does not assume any number of dice in particular. More importantly, not 2 dice.)

EDIT: You can just skip to post #4 if you want. Posts #2 and #3 are my ramblings while trying to figure it out.

Rather than trying to compute the actual odds, let's think it through first. It helps to know that the sum of opposites sides of a die always total 7. Thus, 1 and 6 are on opposite sides of a die. So are 5 and 2. And 3 and 4.

Let's say we have n dice. Imagine you've listed all of the different ways of rolling a sum of T using those n dice. Now think about the sums on the bottom. The sum of the bottoms would be 7n - T. So the odds of rolling a sum of T would be the same as rolling a sum of 7n - T. Let's take a simple example of 3 dice for a total of 18. There's only 1 way to roll an 18 and that's 6-6-6. What's the sum on the bottom? We know that on the opposite side of a 6 is a 1 so the sum would be 3 which is also 7n - T (21-18). The odds of rolling a 3 is the same as rolling an 18.

Likewise, and still using 3 dice, the probability of rolling a 4 is the same as rolling a 17. Same goes for 5 and 16, 6 and 15, 7 and 14, 8 and 13, 9 and 12 and 10 and 11. So for each odd sum, there is an even sum (7n-t) with the same probabilty. Notice that for each set of numbers, one of the sums is even and one of them is odd. So the chances of rolling an even sum is equal to rolling an odd sum? Yes, but only if your using an odd number of dice.

If you're using an even number of dice, this won't work. For 2 dice, the odds of rolling a 2 is the same as rolling a 12. But both of those sums are even so they don't "cancel" each other out nicely like they do for an odd number of dice.

Hopefully my explanation for the odd number of dice makes sense. I'm too tired to think about rolling an even number of dice right now.

Last edited by pi man (2007-04-03 16:59:24)

pi man · 2007-04-03 15:50:59

I'm convinced the probabilty of rolling an even sum is 50% but I'm not sure how to prove it yet.

Even + Even = Even
Odd + Odd = Even
Even + Odd = Odd

The only way to roll an odd sum, regardless of the number of dice, is if the number of odd numbers you rolled is also odd. What's the odds of rolling an odd number of odd numbers? This may be an easier way to figure out the problem. I'll have to sleep on it.

Last edited by pi man (2007-04-03 16:56:59)

pi man · 2007-04-03 16:56:27

Okay, here's a reasonable "proof" that the probabilty of the sum of n dice is even is 50%.

Roll n dice. We're going to compute a "rolling sum", i.e. adding the dice together one at a time. Look at the first die. It has a 50% chance of being even (2, 4, or 6). Add the second dice to it. In the 50% of cases where the first die was even, there is a 50% chance that the sum will remain even (the second die is even) and 50% chance the sum will become odd (the second die is odd). In the 50% of cases where the first die was odd, there is a 50% chance the the sum will remain odd (the second die is even) and 50% chance the sum will become even (the second die is odd). So there is a 50% chance the sum of the first 2 dice will be even.

Add the 3rd die to the sum of the first 2. Follow the same logic. There is a 25% of changing the running sum from even to odd, 25% chance of the changing the running sum from odd to even, 25% chance of the running sum remaining even and 25% chance of the running sum remaining odd. So there is a 50% chance the sum of the first 3 dice is even.

You can keep repeating this process of adding another die to the running sum until you reach n dice. The probabilty of the sum being even will always be 50%. You could expand this to say that the probability of the sum of any n random numbers being even is 50%.

Stanley_Marsh · 2007-04-03 17:04:26

I think the probability is 1/2 , cuz , there are only two option either even or odd , and the number of odds is equal to that of even.

Stanley_Marsh · 2007-04-03 17:16:58

Last edited by Stanley_Marsh (2007-04-03 17:21:24)

clooneyisagenius · 2007-04-03 19:45:32

I agree with you all that the probability is 50% but I was not sure how to prove it exactly. What pi man said looks good to me. I'm not sure if it is exactly what I'm supposed to find; the chapter we are on is about "counting" and "binomial coefficients" and the such. But I think it to be proof enough, and very helpful! Thanks!

I consider #2 done then! Thanks!

For #1 I think Stanley_Marsh's response is golden. I understand it completely and actually had most of it. I was unable to get to/past this part:

Stanley_Marsh wrote:

I'd say I'm about 90% sure on this now though. Still more advice/help is welcome.

Thanks for the help Stanley_Marsh and Pi Man!

Stanley_Marsh · 2007-04-03 20:04:10

But I am not sure , because I am learning this part too.

Stanley_Marsh · 2007-04-03 21:56:41

The Function should be

Thus you can generate all the elements of B .

Last edited by Stanley_Marsh (2007-04-03 21:59:49)

clooneyisagenius · 2007-04-04 04:08:43

For #1:

If I assume:
A1={a11,a12,...}
A2={a21,a22,...}
.
.
.
Ak={ak1,ak2,...}
.
.
.

Then there must be a function f(aij) = (j,i) where (j,i) is in NxN (which I have already proven to be bijective. I think I would need to show that f is a bijection too though?

JaneFairfax · 2007-04-04 06:20:24

For #1, I think the best approach is not to be too ambitious and just try to prove that the union of just two countable sets is countable. The proof by induction for n sets will then follow from this.

For, suppose for induction that the union of n countable sets is countable. Then, for the union of n+1 countable sets,

where

is countable by the inductive hypothesis. So if you can prove that the union of just two countable sets is countable. B∪A[sub]n+1[/sub] would be countable, completing the proof by induction.

Last edited by JaneFairfax (2007-04-04 06:23:13)

Ricky · 2007-04-04 06:30:22

And to do as Jane suggested, one may wish to reflect on the fact that all the positive evens are countable, and all the positive odds are countable, and that the union of the two forms the natural numbers.

whatismath · 2007-04-10 10:18:01

Hi everyone,

I am sorry I cannot type special characters just with my keyboard.

#1. Try this "diagonal method of counting":
a_11 -> a_12 -> a_21 -> a_13 -> a_22 -> a_31 -> a_14 -> ...
With this indexing, a_ij appears in count # i+((i+j-1)(i+j-2)/2).
In case any of these sets are indeed finite, then we could count any fixed element, say a_11
when the set is already exhausted since if f:X->Y is surjective and X is countable, then so is Y.

#2. We could try induction starting with n=1.
Prob_1(sum is odd) = Prob_1(sum is even) = 3/6 = 1/2.
Assume for n dice, Prob_n(sum is odd) = Prob_n(sum is even) = 1/2 for n >= 1.
Prob_(n+1) (sum is odd) = Prob_(n+1)(sum of first n dice is odd AND (n+1)st die is even)
+ Prob_(n+1)(sum of first n dice is even AND (n+1)st die is odd)
= Prob_n(sum of first n dice is odd)XProb_1((n+1)st die is even)
+ Prob_n(sum of first n dice is even)XProb_1((n+1)st die is odd)
throwing dice being independent events, and now apply induction assumption
= (1/2)X(1/2) + (1/2)X(1/2)
= 1/2
Similarly, Prob_(n+1) (sum is even) = 1/2.
So the assertion is true for all n >= 1 by induction.

#3. I think we just need to look into the meaning of "n choose k". Let's label n objects
A_1, A_2, ... A_n. Let's choose k objects out of these n. If k = 0 or k = n, there is 1 way
(even for choosing nothing). Assume k > 1. A combination of k objects is either but not both
(i) k-1 objects from A_1, A_2, ..., A_(n-1) AND A_n or
(ii) k objects from A_1, A_2, ..., A_n-1 (and A_n not chosen)
By induction ON n+k, namely the sum of # of objects and # to be chosen,
there are (n-1 choose k-1) combinations of type (i) and (n-1 choose k) combinations of type (ii).
We finish with Pascal's formula.

Thanks.

clooneyisagenius · 2007-04-10 10:38:00

Thanks everyone, I got #3; and got it correct on the test!

#1 I got wrong, I attempted to not directly copy anyones work here, but instead tried to use advice from different posts and I was wrong and have to try and fix it now, but I appreciate all the help.

I didn't actually understand #2 really until WHATISMATH posted. I appreciate it

Thanks for the help everyone.

Stanley_Marsh · 2007-04-10 10:44:17

#2 , see my post here http://www.mathsisfun.com/forum/viewtopic.php?id=6786 , maybe it will help you.

Math Is Fun Forum

#1 2007-04-03 11:42:56

3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#2 2007-04-03 15:35:11

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#3 2007-04-03 15:50:59

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#4 2007-04-03 16:56:27

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#5 2007-04-03 17:04:26

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#6 2007-04-03 17:16:58

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#7 2007-04-03 19:45:32

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#8 2007-04-03 20:04:10

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#9 2007-04-03 21:56:41

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#10 2007-04-04 04:08:43

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#11 2007-04-04 06:20:24

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#12 2007-04-04 06:30:22

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#13 2007-04-10 10:18:01

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#14 2007-04-10 10:38:00

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

#15 2007-04-10 10:44:17

Re: 3 discrete math problems: 1. countable sets, 2. probability, 3. pascal

Board footer