Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

clooneyisagenius
Member
Registered: 2007-03-25
Posts: 56

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

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!

Offline

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

pi man
Member
Registered: 2006-07-06
Posts: 251

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

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)

Offline

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

pi man
Member
Registered: 2006-07-06
Posts: 251

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

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)

Offline

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

pi man
Member
Registered: 2006-07-06
Posts: 251

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

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%.

Offline

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

Stanley_Marsh
Member
Registered: 2006-12-13
Posts: 345

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

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.


Numbers are the essence of the Universe

Offline

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

Stanley_Marsh
Member
Registered: 2006-12-13
Posts: 345

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

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


Numbers are the essence of the Universe

Offline

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

clooneyisagenius
Member
Registered: 2007-03-25
Posts: 56

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

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! smile 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!

Offline

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

Stanley_Marsh
Member
Registered: 2006-12-13
Posts: 345

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

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


Numbers are the essence of the Universe

Offline

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

Stanley_Marsh
Member
Registered: 2006-12-13
Posts: 345

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

The Function should be

  Thus you can generate all the elements of B .

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


Numbers are the essence of the Universe

Offline

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

clooneyisagenius
Member
Registered: 2007-03-25
Posts: 56

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

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?

wave

Offline

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

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

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

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. BA[sub]n+1[/sub] would be countable, completing the proof by induction.

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

Offline

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

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

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

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.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

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

whatismath
Member
Registered: 2007-04-10
Posts: 19

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

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.

Offline

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

clooneyisagenius
Member
Registered: 2007-03-25
Posts: 56

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

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

#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.

Offline

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

Stanley_Marsh
Member
Registered: 2006-12-13
Posts: 345

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

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


Numbers are the essence of the Universe

Offline

Board footer

Powered by FluxBB