Sunday, February 10, 2013

Solution to Sphere Problem (Problem # 433)

Here is a statement of the problem:

A sphere of radius 1 is cut by two parallel planes into three parts. The volume of the part between the two planes is exactly half the volume of the whole sphere. What is the smallest possible distance between the two planes?


I attempt to use calculus to solve this problem. I make the approach of setting up a triple integral in spherical coordinates to find the volume of the region sandwiched between the two planes and the unit sphere in order to find the distance between the two planes.

Recall that in spherical coordinates a point, (x,y,z),  in R^3 is represented by the parameters (ρ,φ,Ө). ρ is just the distance between the origin and (x,y,z), φ the angle the red line makes with the positive z-axis (see figure below), and Ө the angle the blue line makes with the positive x-axis in the x-y plane. In spherical coordinates the equation of a plane must be written using the three parameters (ρ,φ,Ө). For example, the plane z = h (where h is any nonzero real number) is defined by ρ*cos φ = h. In terms of ρ, the equation of the plane in spherical coordinates is ρ = h/cos φ. This will prove helpful when I set up the first triple integral. I explain my approach below.


Tuesday, September 11, 2012

The Empty Set

In my previous post I talked about counting the total number of subsets of sets with a finite number of elements. In order to get all possible subsets we had to include the empty set, the set with nothing in it.

It turns out that the empty set is a subset of any set no matter what that set is. In this post I will provide a proof of this. But first let me tell you what I mean by subset.


Let A and B be two nonempty sets. A is a subset of B if all elements of A are also elements of B. For example let A = {1,3,5,7} and B = {0,1,2,3,4,5,6,7}. A is a subset of B, because every element of A is also an element of B. Now consider the set C = {1,3,5,7,9}. C is not a subset of B, because there is an element of C that is not an element of B. C is an example of a set that is not a subset of B. This will be an important part of the proof to show that the empty set is a subset of any set.

 
For those of you who are confused by the proof of statement (ii) let me put it in words.
 
Let A be any nonempty subset of U. By way of contradiction suppose the empty set is not a subset of A. It follows that there exists an element x in the empty set such that x is not an element of A. But the empty set has nothing in it; therefore x cannot be an element of the empty set. [By the definition of the empty set] It follows that for all x in U, x cannot be in the empty set. Therefore there are no elements in the empty set that are not in the set A (this is our equivalent definition of what it means to be a subset). Thus the empty set must be a subset of A.
 
I've probably made this proof more complicated than it should be, but once you understand it, it is truly an elegant proof!

Finite Power Sets

Consider the set A = {0,1,2,3,4,5,6,7}. How many subsets of A are there? You can list all possible subsets of A and then count your list, but this isn't very efficient. Remember, any subset of A can only contain elements from A. A subset of a set cannot have elements that are not in the original set otherwise it wouldn't be a subset of that set.

For example {1,2,3,9} is not a subset of A, because 9 is not in A.

Let's think about how we can count all the subsets more efficiently. Consider all subsets of A with a single element. Immediately you should think 8, because there are 8 elements in A. That makes 8 subsets with a single element.

How about all subsets with two elements? How do we figure out how many there are without listing them all? Let S = {_,_}. The first empty spot in S can filled with 1 of 8 elements. Once we fill the first spot with an element from the original set we can't use that same element again. That leaves us 7 more elements to chose from to fill the second empty spot. Therefore, there are 8*7/2! = 28 subsets that have 2 elements.


The subsets S1 = {6,7} and S2 = {7,6} are the same since they have the same elements, therefore S1 and S2 are same. The order in which the elements of a subset appear does not matter. That's why we divide 8*7 by 2! to get 28, where 2! represent the number of ways two objects can be arranged.

Let's move on to counting subsets with 3 elements. Let S = {_,_,_}. Using the same argument we see that the first empty spot can be filled with 8 possible elements from the original set, the second empty spot has 7 possibilities and the third spot 6 possibilities. There are 8*7*6/3! = 56 subsets with 3 elements.

We keep doing these simple calculations until we find the number of subsets with 8 elements, because we cannot make subsets of A with more than 8 elements. Without doing any calculations we know that there is only 1 set containing all 8 elements, namely A. Any set is a subset of itself that's why we include the original set.

We end up getting 8 + 28 + 56 + 70 + 56 + 28 + 8 + 1 = 255. Did we get all of the subsets of A? No! Those of you who have taken a course in discrete math or basic set theory know that all possible subsets of a finite set must be a power of 2. Our result, 255 is an odd number and is not a power of 2. What did we do wrong?

We didn't do anything wrong we just forgot to consider the possibility of having a subset with nothing in it. This is the same as asking, "How many possible subsets of A are there with no elements?" The answer is 1. There is only 1 way to select a subset with nothing in it. We do not select anything from the original set and move on. This is called the empty set and we can write it as { }.

This brings the total number of subsets to 256, which is a power of 2.

Is there a quicker way to do this? Yes! We can use combinations to count all possible subsets. For any two nonnegative integers n and r where n r, the total number of ways of selecting r objects from a collection of n objects is C(n,r) = n!/r!(n-r)!

Going back to our original problem of counting all possible subsets from A we get

C(8,0) + C(8,1) + ... + C(8,7) + C(8,8) = 1 + 8 + ... + 8 + 1 = 256, where n = 8 and r ranges from 0 to 8.

There is an even quicker way to do this. Notice that for each element of A we have 2 possibilities; it is either in our subset or it is not in our subset. Therefore the total number of subsets of A is 2*2*2*2*2*2*2*2 = 2^8 = 256. This is why the total number of subsets of a set with a finite number of elements must be a power of 2. The set of all subsets of a set is called the power set, hence the name of this post. If your set contains n elements where n ≥ 0, then there are 2^n possible subsets.

What about infinite sets? How do you count the number of subsets of a set with an infinite number of elements? Technically you can't, because you cannot count to infinity. For example, the set of natural numbers N = {1,2,3, ...} is a countably infinite set. We call it a countably infinite set, because we can place all the elements of N on a list and be confident that all of them are on our list. Our list will be infinitely long, but mathematicians are used to dealing with lists that are infinitely long.

So how many subsets of N are there? Without thinking too hard about this question your gut should tell you the number of subsets is infinite. You would be right in this case, but this is where things get tricky. Remember how I said N is a countably infinite set? There is such thing as an uncountably infinite set. If I tried to make a list of a set that is uncountably infinite I couldn't do it. No matter how meticulous I am about creating this list there will always be something that is not on my list. In other words there is no way to list everything from a set that is uncountably infinite. In fact the power set of N is a classic example of a set that is uncountable. I cannot make a list of every subset of N and be 100% certain that every subset is on my list. I will always find something that I don't have on my list.

Why not add to my list that which was not on my list, you ask. That is where the problem lies! Once you update your list with the new item you will always find another one. And you will keep finding more and more items that weren't there before. You will keep finding new items until the end of time, but your list will never be complete. You cannot call such a set a countable set. Countable implies that you can find a way to list every element from that set (without actually listing every element) and be 100% certain that list you made is complete.

There is a way to prove this, but I will save it for another post on another day!

Friday, March 30, 2012

Playing the Mega Millions Lotto? Please Read! (part 2)

In my last post I talked about calculating the expected value of playing the Mega Millions lotto by purchasing a single ticket. I discovered that the expected value is positive. This means the Mega Millions lotto is in your favor and you should go purchase a ticket. As I explained the expected value is a concept; it has no meaning in reality. It tells you how much you can expect to gain or lose by playing the lotto; it does not tell what you will actually gain or lose.

For example, a census might say the average family in California has 2.4 children. The word average as it is used in this context has no physical meaning in reality since you cannot have a fraction of a child. It can be interpreted to mean that a typical family in California has either 2 or 3 children.

If you are familiar with basic probability theory and calculating expected values you can continue reading this post. If not I suggest you to read my previous post.

http://mikebibbygrigsby83.blogspot.com/2012/03/playing-mega-millions-lotto-please-read.html

In this post I will talk about what happens to the expected value when you purchase more than one lotto ticket for the Mega Millions jackpot. The results are surprising. Let me start by constructing a probability table for different values of 'n'. The letter 'n' will represent the number of tickets an individual may purchase without regard to the total number tickets purchased by other individuals.

Probability Table

----------------------------------------------------------------
n         | Probability of Having a Winning Ticket
----------------------------------------------------------------
1         | 0.00000000569
2         | 0.00000001138
5         | 0.00000002846
10        | 0.00000005691
25        | 0.00000014228
50        | 0.00000028456
100       | 0.00000056911
250       | 0.00000142279
500       | 0.00000284557
1,000     | 0.00000569115
5,000     | 0.00002845573
10,000    | 0.00005691146
50,000    | 0.00028455730
100,000   | 0.00056911460
1,000,000 | 0.00569114597
----------------------------------------------------------------



When I calculated the probability of having a winning ticket for each value of 'n' I made the following assumptions about the tickets:


1.) All tickets have only one set of numbers. This is not the case in reality since you can purchase more than one play (and hence have more than one set of numbers) on a single ticket.

2.) All tickets purchased by an individual are unique. In other words you cannot have two tickets (or three, or four, etc.) where the first 5 numbers and the 6th 'mega' number are the same.


For example, consider the following two tickets with the following 6 numbers:

Both tickets have the same set of numbers and only the order of the first 5 numbers are different. Therefore, both tickets are the same and two or more tickets like this are not allowed for this particular scenario.

-----------------------
|Ticket 1              |
-----------------------
|                mega  |
|45 12 07 25 39    40  |
-----------------------

-----------------------
|Ticket 2              |
-----------------------
|                mega  |
|12 39 25 45 07    40  |
-----------------------


This table tells us that when you buy more tickets you increase your chances of winning. You don't need to do all these tedious calculations to figure that out :-P

Even if you buy 1,000 or 10,000 tickets your odds are no better than 1 in 175,000 or 1 in 17,500 respectively. Now, let's look at what happens to your expected net winnings. I assume that each ticket costs $1.


Expected Net Winnings


----------------------------------------------------------------
n         | Expected Net Winnings ($)
----------------------------------------------------------------
1         | 2.07 
2         | 1.07
5         | -1.93
10        | -6.93
25        | -21.93
50        | -46.93
100       | -96.93
250       | -246.93
500       | -496.93
1,000     | -996.93
5,000     | -4,996.78
10,000    | -9,996.36
50,000    | -49,982.70
100,000   | -99,940.02
1,000,000 | -994,305.78
----------------------------------------------------------------

According the table above your expected net winnings decrease as you buy more tickets. This would be a strong suggestion against buying more tickets even though your chances increase. I wouldn't buy a ton of tickets, because you are more likely to lose a lot of money if none of your tickets have the winning combination!



Let's look at the scenario from the perspective of the total number of plays purchased for the Mega Millions jackpot. In this case I will relax the two assumptions above and add one more assumption.


1.) People can purchase more than one play on a single ticket (i.e. you can have more than one combination of numbers on a single ticket).

2.) The plays themselves do not have to be unique. So it is possible for two or more people to have the winning combination.

3.) The combination of numbers selected for each play are independent of one another (i.e. the combination of numbers for one play does not effect the combination of numbers for another).


For this scenario I am still assuming that there are only two possible outcomes; either someone has a ticket with the winning combination or no one has a ticket with the winning combination. Therefore, someone either wins the jackpot or no one wins anything at all. And each play costs $1.

Given the three assumptions above we will use the binomial probability distribution to construct a table like those above. If you don't know what the binomial probability distribution is google it!

Let us first introduce the following parameters:

N - total number of plays purchased
p - probability of a play matching the winning combination
q - probability of a play not matching the winning combination

p = 1/175,711,536 = 0.00000000569
q = 1 - 1/175,711,536 = 0.9999999943

*Note: the values of 'p' and 'q' do not change and are fixed


Probabilities and Expected Net Winnings for all who Play the Mega Millions Lotto


----------------------------------------------------------------
N             | Probabilities | Expected Net Winnings ($)
----------------------------------------------------------------
1             | 0.00000000569 | 2.07
2             | 0.00000001138 | 4.15
5             | 0.00000002846 | 10.37
10            | 0.00000005691 | 20.73
25            | 0.00000014228 | 51.83
50            | 0.00000028456 | 103.66
100           | 0.00000056911 | 207.32
250           | 0.00000142279 | 518.30
500           | 0.00000284557 | 1,036.61
1,000         | 0.00000569113 | 2,073.22
5,000         | 0.00002845573 | 10,366.02
10,000        | 0.00005691146 | 20,731.88
50,000        | 0.00028451682 | 103,653.31
100,000       | 0.00056895268 | 207,291.34
1,000,000     | 0.00567498209 | 2,070,165.31
10,000,000    | 0.05532229244 | 20,427,260.84
100,000,000   | 0.43397362257 | 177,743,118.44
540,000,000   | 0.95372802684 | 490,026,268.99
1,000,000,000 | 0.99662427778 | 534,801,387.78
----------------------------------------------------------------


The probabilities in this table represent the chance that someone has a ticket with the winning combination given that the total number of plays purchased is 'N'. This allows the possibility that more than one person has a winning ticket. The figures in the second column represent the expected net winnings for all who play the lotto. We are not concerned with individual players here! As we saw in the previous table the expected net winnings for an individual become negative once they purchase more than three plays.

The table suggests that as the total number of plays purchased increases the likelihood that someone will win the jackpot. The expected net winnings for all players also increases as more tickets are purchased. Furthermore, the probability that someone has a winning ticket approaches 1.00 and the expected net winnings approaches the jackpot of $540 million. This means that it is very likely that some will win the big jackpot tonight. I hope it's me!


Thanks again for reading part 2 of my post about the Mega Millions Lotto. I spent the entire night on this and my previous blog (probably more time than I should have).


Even though I know a lot of probability theory I should say that I make no guarantees as to the accuracy of the numbers and the methods I used to obtain those numbers. I am only human.

Upon scrutinizing these results if you should find any errors in my calculations or methods, please let me know. I can always revise these blogs or post future blogs with more accurate information.

Thanks again :-)

Playing the Mega Millions Lotto? Please Read!

Here is a nice video by Salman Kahn, the founder of Kahn's Academy, that shows how you calculate the probability of winning the Mega Millions jackpot. Probability is just a fancy word for chance.

http://www.youtube.com/watch?v=gyqodNhM3EU&feature=share

If you buy one lottery ticket your chance or probability of winning is 1 in 175,711,536! That's pretty slim if you ask me!!! That's why I haven't bought a lottery ticket until last night; one of my buddies on Facebook convinced me to.


So I got thinking about this a little more. Because I know a little probability theory, I wanted to play with this a little. Okay, scratch that. I probably know more probability theory than most people. I am just being modest :-)


Since I did buy one lottery ticket I wanted to know what my expected value is. In other words I want to know the amount I can expect to win (or lose) by playing the Mega Millions lotto one time. I am assuming that I and everyone else playing can win or lose. By this I mean two things:


1.) If all the numbers on my ticket match the winning combination I win the big jackpot. If they don't match I win nothing. Even if 5 out of 6 of the numbers on my ticket match the winning combination I still win nothing (I don't think this is the case in reality).

2.) Only one person can win the jackpot. In other words no more than one person can have a winning ticket. If I buy more than one ticket I cannot have more than one winning ticket.

Now let me explain the concept of expected value. If all the numbers on your ticket match the winning combination you expect to be $540 million richer. If not, you don't expect to win anything. Simple, right? Not so fast.

The expected value of playing the Mega Millions Lottery is just the weighted average of all possible outcomes. As I have outlined it in this blog I am only allowing two possible outcomes for playing the Mega Millions lotto; winning the big jackpot or winning nothing at all.

I am going to label the two outcomes with a capital letter for convenience.

W: winning the big jackpot
L: not winning anything ('L' for losing)

I said the expected value is just the weighted average of all possible outcomes. This just means I multiply the value of each outcome by its corresponding probability and sum them up. If all outcomes are equally likely (i.e. each outcome has the same probability) I just add the values of all possible outcomes together and divide the total by the number of outcomes. If there were 5 possible outcomes with the same probability, I just sum up the values for the 5 outcomes and divide by 5. This is how you normally calculate the average.

Whenever the outcomes are not equally likely (i.e. at least one of the outcomes has a probability different from the others) I instead calculate the weighted average of all those outcomes. This will give me the expected value.

To see how to do this let's make a table for the two outcomes in question.

----------------------------
W | 0.00000000569           |
----------------------------
L | 0.99999999431           |
----------------------------

This table just lists all possible outcomes for the Mega Millions lotto and their corresponding probabilities. Notice the probabilities are not the same, which is why I calculate the weighted average.

Remember, a probability is just the number of ways that a particular outcome can occur divided by the total  number of ways for all possible outcomes (as explained in the video). Whenever the probability of an event is 0 that means the event has no chance of occurring. If the probability of an event is 1 the event has every chance of occurring (i.e. the event will happen). The closer the probability of an event is to zero the less likely that event is going to occur. Likewise, the closer the probability of an event is to 1 the more likely it is going to occur. Probabilities are usually expressed as decimals or fractions and they can never be negative or bigger than one.

Continuing with our example, if I buy only one ticket and it is a winning ticket then the probability of winning is 1/175,711,536 (the slash '/' stands for dividing). If I buy only one ticket and it is not a winning ticket the probability of losing is 175,711,535/175,711,536. You should notice the number 175,711,535 is one less than 175,711,536. The decimals in the table were obtained using a calculator.

In case you missed the video the number 175,711,536 represents the total number of ways of generating the first 5 numbers and the 6th 'mega' number. The 6 numbers on your lotto ticket are generated in a similar fashion. I will not explain how to calculate 175,711,536 in this blog!

The only thing I need now is the value for each outcome. The value represents my net winnings after buying one ticket. This is just the amount of money I win minus the amount of money I spend to buy a single lotto ticket. Here is a table showing each outcome, its value and its corresponding probability.

------------------------------------------
W | 539,999,999 | 0.00000000569           |
------------------------------------------
L | -1          | 0.99999999431           |
------------------------------------------

If I win I win $540 million minus $1. This is because I spend $1 to buy the ticket so my net winnings are $539,999,999. If I lose I win $0 minus $1. For the same reason my net winnings are -$1. I use the term net winnings loosely here. Whenever my net winnings are negative I am really losing something. Confusing, huh?

Therefore, my expected value is going to be $2.07. That's right, I can expect to win $2.07 by playing the Mega Millions lotto. I emphasize expect, because that does not mean I will actually win $2.07. The expected value does not accurately reflect what I will win if I buy a single lotto ticket. It tells me how much on average I can win if I play one ticket. In reality (as I have outlined it in this blog) I either walk away with the jackpot or I walk away with nothing, minus the $1 I spend on the ticket.

The message to take home from this blog is that you should play the Mega Millions lotto and buy one ticket. Why? Because the expected value of buying one ticket is positive. This means the lotto is in your favor. So, please go out and buy a ticket before tonight. You have nothing to lose!

Thank you for reading my blog! I will create a second blog shortly where I will explain what happens to the expected value when you buy more than one ticket.