It's not often that humour can be extracted from a subject matter as heavy as World War 2, but there you go...
Sunday, November 25, 2007
Monday, November 12, 2007
Saturday, November 10, 2007
4D combinations
Ok. You see the number plate flashes by, and the gambler in you immediately wonders how many permutations of 4D can you buy with that 6 digit combinations - 378953.
Easy. It's 6P4 ( order matters here), and then to account for the double occurence of 3, we divide by 2. 6P4 being 360, the answer is 180.
Right? Wrong. Though the actual answer, 192, is close, the thought process is more tedious than is first suspected. What's more, should any of the 12 more numbers which you miss out strike top prize, you will be left cursing your high school math teacher.
Let's examine what happens with 6P4. It's fundamentally similar to 6C4 (where ordering does not count), and then multiply by 4! ways of reordering the 4 numbers you choose.
6C4 = 15. Let's list down all 15 cases.
Since there are 2 occurence of 3, I shall denote them by 3 and 3.
7895
3789
3895
3795
3785
3789
3895
3795
3785
3378
3379
3375
3389
3385
3395
Let's denote the 15 occurences into 3 groups:
Group 1: No occurence of 3.
Only 7895 here.
4C4 x 4! = 1 x 24 = 24 ways
Group 2: 1 occurence of 3.
8 groups here, but since 3 and 3 are similar, we shall deal only with 4 groups.
4 groups, in which there are 4! ways to order each group:
4C3 x 4! = 4 x 24 = 96 ways
*why 4C3? Since 3 is already selected, we have 4 more numbers 7,8,9,5 vying for 3 places.
Group 3: 2 occurence of 3.
6 groups here.
Since the 3 and 3 are similar, it is no longer 4! to order with each group.
(Remember, 3378 and 3378 are exactly similar.) We do 4!/2! = 12 ways.
4C2 x 4!/2! = 6 x 12 = 72 ways.
*Why 4C2? Since 33 is already selected, we have 4 more numbers 7,8,9,5 vying for 2 places.
Total number of ways = 24 + 96 + 72 = 192 ways.
What if now the 6 sets of numbers is changed to 337789?
We have to split our tasks into 9 groups:(think of trinary system 3^2).
Luckily for us, some groups are mathematically impossible.
Total number of ways = 78 ways.
Imagine if you had used 6P4, and then divide by 2(to account for 3 presumably) and then divide by 2 again (to account for 7), ending up with 360/2/2 = 90. With more careful math, you can actually save yourself from buying 12 repeat combinations!
Monday, November 05, 2007
Great Songs that met their Video Match
Celebrating the simplicity of it all...
...or contemplating the fragility of it all.
...or contemplating the fragility of it all.
Friday, November 02, 2007
Binary Model and Inclusion-Exclusion Theory
A dice is rolled t times. What is the probability that all sides appear at least 2 times?
Sounds like a simple question. We have to be cautious though, for "what is the meaning of life?" is too a simple question that has stumped humanity.
First up, we search for an opening to the problem that is at once accessible to us.
Consider this: if all sides were to appear at least 2 times, the smallest value for t has to be 12. One possible set for t=12 would be {1,1,2,2,3,3,4,4,5,5,6,6}. In fact, this is the only set possible.
We see that for t<12, P = 0. And we can calculate the probability for t=12 by means of simple combinatorics:
This approach may not be useful, but the answer comes in handy to allow us to verify whatever complicated equations we may derive later.
(Or we can build from this approach, evaluating 13 throws as having 1 extra throw to distribute among the 6 sides. 6 choose 1 = 6. Hence, ans = 6*P12.
For t=14, we have extra 2 throws to distribute among 6 sides = 2 balls to distribute among 6 urns. 7 choose 5 = 21. But it is not so simple to evaluate now, as the number of ways is not all the same probablity.)
Where do we go from here? Introduce the binary system! And one that is symmetric in event space. Let each bit represent one side of the dice: A1 A2 A3 A4 A5 A6.
Now, how shall we define 1 and 0?
Consider that we want to find probability of "at least 2 times". In other words, we can find 1 - P(0) - P(1). With this in mind, we define bit 1 as occurence of 1 or 0 times, and bit 0 as occurence of 2 and above times, so that we can do something like 1 - P(...).
Now we can construct the Binary Table!
Let us inspect the meaning of each row.
The first row means all the numbers must appear at least 2 times. Hey! This is the case we want to find! Now things becomes apparent. To find the probability of this row, all we have to do is to sum up the probability of the rest of the rows, and do a 1 - P(prob of the rest of all the rows). Note that all the rows of the Binary Table are mutually exclusive.
The second row. It would mean Number 1 appears once or 0 times, and the rest all appear at least 2 times.
The last row. It means that all sides appear at most 1 time, hence giving a maximum of t=6 (or a minumim of 0). As earlier established, t has to be >=12, so the probability of this happening is 0. We shall not consider this case.
So there are a total of 2^6= 64 cases for us to sweat on.
(actually 63, as we discount 111111....)
Let's start evaluating the probability of Row 2. (Row 1 is 000000. There is very little information we can get from that.)
How can we find the probability that the Number 1 appears only once or none WHILE ensuring that the rest appear at least 2 times? Unfortunately it is too difficult.
Imagine t=12.
For 1 to appear 0 times(NONE): we need to find the number of ways to solve A2+A3+A4+A5+A6 = 12...a case of 12 balls distributed among 6 urns.
For 1 to appear 1 time: we need to solve for the number of ways to solve
A2+A3+A4+A5+A6 = 11...
Mind boggling stuff. And that's only for the 1 out of 62 cases we need to establish.
Instead, for that row, I am forced to consider a variation of it:
Here, I introduce a 3rd state x to mean Don't Care. I do not care what happens to the rest of the number as long as Number 1 appears 0 or 1 time in t throws. The probability of the case I just mentioned is actually humanely possible:
Why the term
Because we still need to account for the fact that this appearance of Dice Number 1 can occur at the first throw, or at the second throw,...up till the t throw. For lack of a better term, let's call this the t Loop.
The formula can now be combined:
Now we shall generate the full table, which I shall call the Don't Care Table.
One very important point to note is that the table is a truncated form. I left out the rows xxxx1x, xxx1xx, xx1xxx, x1xxxx, 1xxxxx, whose calculation is similar to the one we did for xxxxx1. Please bear this in mind! Also note that the rows of this table aren't mutually exclusive!
But how does the Don't Care table help when all we want is to sum up all the 62 rows of the Binary table. Ah....Poincare has this figured out. He found that to calculate the probability of the whole table minus the case of 000000 (we cannot include 000000, else the Probabilty is unity), for example, we must do:
As mentioned, the rows are not mutually exclusive. xxxxx1 and its 5 cousins (xxxx1x, xxx1xx,xx1xxx,x1xxxx,1xxxxx) contain all of what we want from the Binary Table...and more. We have some subtraction on our hands.
Consider the last row 111111. This row is exactly the same whether in the Don't Care or Binary Table. It is the simplest element in a recursive algorithm.
Now consider the second last row x111111. It can either be 0111111 or 1111111.
Hence, to get 0111111, all we have to do is to compute x111111 - 111111.
Therein lies the recursive algorithm, which we use to work back all the way to the top.
If you are not convinced, work out the next row 001111 (which is going to be a bit more tedious.) First we evaluate xx1111:
xx1111=001111+011111+101111+111111
Hence, 001111 = xx1111-(011111+111111)-101111
Knowing x111111=011111+111111, the equation becomes 001111 = xx1111-x11111-101111
We now need to break down 101111 into its elements.
We consider 1x1111 = 111111 + 101111
101111 is then equal to 1x1111 - 111111.
Since 1x1111 = x11111 in absolute value, we get 101111 = x11111 - 111111
We get 001111 = xx1111 - x11111 - 101111 = xx1111 - x11111 - x11111 + 111111
= (2C0)xx1111 - (2C1)x11111 + (2C2)111111
Finally, we can set up this equation:
(6C1)000001 + (6C2)000011 + (6C3)000111 + (6C4)001111 + (6C5)011111 + (6C6)111111
= (6C1)xxxxx1 - (6C2)xxxx11 + (6C3)xxx111 - (6C4)xx1111 + (6C5)x11111 - (6C6)111111
This is basically the inclusion-exclusion theory, now cast in a different light with my binary model. Bear in mind that it is EXACTLY of the form:
Let's take a look at the next row.
If you realise here, we are going to introduce another binary system. Take stock for a moment what is happening: A binary system and a t Loop inside another binary system which has been modified to a Don't Care system. That's rhetoric you can ignore.
The internal binary arises from having 2 Numbers now combining to give 00, 01, 10 and 11. The equation is now:
Why the term
The t Loop that was mentioned a while earlier has gotten a bit sticky. When there was only 1 event, now there are 2 events A1 and A2 to account for, resulting in a total of 3 distinct groups to arrange: A1,A2 and the rest (t-2). Rearranging the term, we get:
We now revise the Row 2 equation:
We do the same for all rows, and come to a general ROW equation:
Now comes the defining moment.
We are going to loop through all the rows, executing
xxxxx1 - xxxx11 + xxx111-xx1111+x11111
(ignoring 111111 of course),
which is equal to the summation of the probability of all the rows in the Binary Table except 000000.
Summation of the probability of all the rows in Binary Table except 000000=
Alternating inclusion exclusion of Dun Care Table =
Hence, our answer to the question posed right at the beginning is:
I have not verified the answers yet. Remember at the beginning, we solved for t=12. This is a good start to verify the formula.
Note that the internal binary loop would become Trinary (0,1,2) if the question is rephrased:
A dice is rolled t times. What is the probability that all sides appear at least 3 times?
Sounds like a simple question. We have to be cautious though, for "what is the meaning of life?" is too a simple question that has stumped humanity.
First up, we search for an opening to the problem that is at once accessible to us.
Consider this: if all sides were to appear at least 2 times, the smallest value for t has to be 12. One possible set for t=12 would be {1,1,2,2,3,3,4,4,5,5,6,6}. In fact, this is the only set possible.
We see that for t<12, P = 0. And we can calculate the probability for t=12 by means of simple combinatorics:
This approach may not be useful, but the answer comes in handy to allow us to verify whatever complicated equations we may derive later.
(Or we can build from this approach, evaluating 13 throws as having 1 extra throw to distribute among the 6 sides. 6 choose 1 = 6. Hence, ans = 6*P12.
For t=14, we have extra 2 throws to distribute among 6 sides = 2 balls to distribute among 6 urns. 7 choose 5 = 21. But it is not so simple to evaluate now, as the number of ways is not all the same probablity.)
Where do we go from here? Introduce the binary system! And one that is symmetric in event space. Let each bit represent one side of the dice: A1 A2 A3 A4 A5 A6.
Now, how shall we define 1 and 0?
Consider that we want to find probability of "at least 2 times". In other words, we can find 1 - P(0) - P(1). With this in mind, we define bit 1 as occurence of 1 or 0 times, and bit 0 as occurence of 2 and above times, so that we can do something like 1 - P(...).
Now we can construct the Binary Table!
Let us inspect the meaning of each row.
The first row means all the numbers must appear at least 2 times. Hey! This is the case we want to find! Now things becomes apparent. To find the probability of this row, all we have to do is to sum up the probability of the rest of the rows, and do a 1 - P(prob of the rest of all the rows). Note that all the rows of the Binary Table are mutually exclusive.
The second row. It would mean Number 1 appears once or 0 times, and the rest all appear at least 2 times.
The last row. It means that all sides appear at most 1 time, hence giving a maximum of t=6 (or a minumim of 0). As earlier established, t has to be >=12, so the probability of this happening is 0. We shall not consider this case.
So there are a total of 2^6= 64 cases for us to sweat on.
(actually 63, as we discount 111111....)
Let's start evaluating the probability of Row 2. (Row 1 is 000000. There is very little information we can get from that.)
How can we find the probability that the Number 1 appears only once or none WHILE ensuring that the rest appear at least 2 times? Unfortunately it is too difficult.
Imagine t=12.
For 1 to appear 0 times(NONE): we need to find the number of ways to solve A2+A3+A4+A5+A6 = 12...a case of 12 balls distributed among 6 urns.
For 1 to appear 1 time: we need to solve for the number of ways to solve
A2+A3+A4+A5+A6 = 11...
Mind boggling stuff. And that's only for the 1 out of 62 cases we need to establish.
Instead, for that row, I am forced to consider a variation of it:
Here, I introduce a 3rd state x to mean Don't Care. I do not care what happens to the rest of the number as long as Number 1 appears 0 or 1 time in t throws. The probability of the case I just mentioned is actually humanely possible:
Why the term
Because we still need to account for the fact that this appearance of Dice Number 1 can occur at the first throw, or at the second throw,...up till the t throw. For lack of a better term, let's call this the t Loop.
The formula can now be combined:
Now we shall generate the full table, which I shall call the Don't Care Table.
One very important point to note is that the table is a truncated form. I left out the rows xxxx1x, xxx1xx, xx1xxx, x1xxxx, 1xxxxx, whose calculation is similar to the one we did for xxxxx1. Please bear this in mind! Also note that the rows of this table aren't mutually exclusive!
But how does the Don't Care table help when all we want is to sum up all the 62 rows of the Binary table. Ah....Poincare has this figured out. He found that to calculate the probability of the whole table minus the case of 000000 (we cannot include 000000, else the Probabilty is unity), for example, we must do:
As mentioned, the rows are not mutually exclusive. xxxxx1 and its 5 cousins (xxxx1x, xxx1xx,xx1xxx,x1xxxx,1xxxxx) contain all of what we want from the Binary Table...and more. We have some subtraction on our hands.
Consider the last row 111111. This row is exactly the same whether in the Don't Care or Binary Table. It is the simplest element in a recursive algorithm.
Now consider the second last row x111111. It can either be 0111111 or 1111111.
Hence, to get 0111111, all we have to do is to compute x111111 - 111111.
Therein lies the recursive algorithm, which we use to work back all the way to the top.
If you are not convinced, work out the next row 001111 (which is going to be a bit more tedious.) First we evaluate xx1111:
xx1111=001111+011111+101111+111111
Hence, 001111 = xx1111-(011111+111111)-101111
Knowing x111111=011111+111111, the equation becomes 001111 = xx1111-x11111-101111
We now need to break down 101111 into its elements.
We consider 1x1111 = 111111 + 101111
101111 is then equal to 1x1111 - 111111.
Since 1x1111 = x11111 in absolute value, we get 101111 = x11111 - 111111
We get 001111 = xx1111 - x11111 - 101111 = xx1111 - x11111 - x11111 + 111111
= (2C0)xx1111 - (2C1)x11111 + (2C2)111111
Finally, we can set up this equation:
(6C1)000001 + (6C2)000011 + (6C3)000111 + (6C4)001111 + (6C5)011111 + (6C6)111111
= (6C1)xxxxx1 - (6C2)xxxx11 + (6C3)xxx111 - (6C4)xx1111 + (6C5)x11111 - (6C6)111111
This is basically the inclusion-exclusion theory, now cast in a different light with my binary model. Bear in mind that it is EXACTLY of the form:
Let's take a look at the next row.
If you realise here, we are going to introduce another binary system. Take stock for a moment what is happening: A binary system and a t Loop inside another binary system which has been modified to a Don't Care system. That's rhetoric you can ignore.
The internal binary arises from having 2 Numbers now combining to give 00, 01, 10 and 11. The equation is now:
Why the term
The t Loop that was mentioned a while earlier has gotten a bit sticky. When there was only 1 event, now there are 2 events A1 and A2 to account for, resulting in a total of 3 distinct groups to arrange: A1,A2 and the rest (t-2). Rearranging the term, we get:
We now revise the Row 2 equation:
We do the same for all rows, and come to a general ROW equation:
Now comes the defining moment.
We are going to loop through all the rows, executing
xxxxx1 - xxxx11 + xxx111-xx1111+x11111
(ignoring 111111 of course),
which is equal to the summation of the probability of all the rows in the Binary Table except 000000.
Summation of the probability of all the rows in Binary Table except 000000=
Alternating inclusion exclusion of Dun Care Table =
Hence, our answer to the question posed right at the beginning is:
I have not verified the answers yet. Remember at the beginning, we solved for t=12. This is a good start to verify the formula.
Note that the internal binary loop would become Trinary (0,1,2) if the question is rephrased:
A dice is rolled t times. What is the probability that all sides appear at least 3 times?
Thursday, November 01, 2007
Analogy of binary systems in probability
Probability is a tricky subject. Often we confuse the sub-branch of counting, which is concerned with the number of ways to perform a certain task with the science of probability. We often forget that each number of ways to perform a certain task does not necessarily share the same probability, or in math-speak, they do not share a symmetric event space.
For example, if you are tasked to find the number of ways to arrange 5 identical balls in 2 urns. The formula for such a scenario is given as below:
As an aside, an ingenious way (unfortunately not mine) of interpreting the formula goes as follows:
I line up all 5 balls in a row. There are 2 urns, so I utilise an imaginary stick and place it between the 5 balls, creating effectively 2 partitions (one left of the stick, and one right). Each partition denotes an urn, so 1 stick is enough to denote 2 partitions. If there are 3 urns, 2 sticks are needed...and so on, giving:
No of sticks needed = No of urns - 1.
Then I simply find the number of ways to order all the sticks and balls, giving me:
(since the balls are themselves indistinguishable and the stick is indistinguishable, so we divide by 5! and 1! respectively.)
What if you are now told that each urn must now contain at least 1 ball each?
Simple. Using the same values, 1 ball is first distributed to each urn to ensure that each urn must now contain at least 1 ball each. That leaves us with 5-2=3 balls left to arrange with the same number of sticks (r-1), giving:
Now comes THE question:
Let the no. of ways of arranging 5 balls in 2 urns given each urn must have at least 1 ball = P1(5,2).
Let the no. of ways of arranging 5 balls in 2 urns given each urn has no restrictions on the number of balls = P0(5,2).
Is the probability of having each urn containing at least 1 ball ( which can be rephrased as the probability of having no empty urn) equal to:
No!
The number of ways to arrange 5 balls in 2 urns is not all equal in probability.
A better way to view the problem uses the analogy of states (like binary states, tri-states that electrical engineers are comfortable with).
The 2 urns represent 2 states, giving us the familiar binary system. Each ball represent one bit. Hence there are a total of:
2^5=32 possible states.
(Of course, we are now simply viewing the problem as putting n distinguishable balls into r distinguishable urns, which is also the number of ways to draw n balls from r unique types(each unique type is an urn!) with replacement, where order counts. Just like a mountaineer who always tries to find new ways to climb the same mountain, mathematicians are always trying to view the same problem from different angles, hoping to gain further insights or discover something which was previously hidden. Back to the problem:)
Breaking up the problem:
The probability of distribution of balls such that we end up with no empty urns becomes relatively clear. It is simply:
Note that 00000 and 11111 all denote 1 empty urn.
The analogy of binary system helps bring probability problem into sharp focus. Another question illustrates its power.
Cards were dealt face down from a deck of 52. What is the probability that the 1st ace encounterd occurs on the nth draw?
We now imagine a binary system of 1 (Ace) and 0 (no ace) with a total of 52 bits.
Picture the table with headers as below:
The meaning of the curly braces, which divide up the table into 2 groups, will be apparent later. But first, we define the sample space, noting that each way has equal probability of occurence.There are a total of 4 aces, to be scattered among all 52 bits. So for every row, there are 4 1s, and 48 0s. So how many rows are there?
Total number of rows possible:
Now, we introduce the restrictions. The 1st ace must occur on the nth draw.
We divide up the group into A1 to An, and An+1 to A52.
In the first group, only 1 ace resides in it, specifically in the An position.
In the second group, 3 aces are distributed among An+1 to A52.
The problem is now reduced to a matter of throwing out unwanted rows and retaining those that we want. So which are the rows that we have to throw out?
1) All those with more than 1 Ace in the group A1 to An.
2) All those with only 1 Ace in the group A1 to An, but whose 1 Ace does not reside in the nth position.
There are quite a lot of rows to throw out here. Instead of throwing out rows, we can think of the rows that we must keep. There is only one group we must keep, which is:
1) All those with 1 Ace in the group A1 to An, and whose 1 Ace resides in the nth position.
For this group, how many ways are there to arrange them? The answer lies in the other group An+1 to A52. Considering that 3 aces are to be found among An+1 to A52, and that there are 52 - n bits from An+1 to A52, we get the final answer:
Now what is the significance of multiplying the answer found above by n? Essentially it gives us the probability of finding 3 Aces in the group An+1 to A52. Without the binary system, these angles may not be so readily apparent.
Lastly, the binary system has made light of an unnecessarily complicated problem: The issue of drawing 4 Venn circle diagrams. I believe most of us were introduced to the Venn diagrams from young, first with 2 circles, then 3 circles. It is a very elegant and simple solution to many probability questions involving many intersections. Put it simply, without John Venn and his marvellous invention, my head would spin like a gyroscope everytime I encounter probability. So if 3 circle Venns have been useful, then 4 circle Venns must be even more useful. I chanced upon this diagram at Wikipedia:
http://en.wikipedia.org/wiki/Image:Inclusion_exclusion_diagram.JPG
The diagram is flawed as soon as I counted the number of states in it. Using the binary system, for each circle we denote it as ONE bit. There are 4 circles, hence 4 bits. In a 4 bit system, there are supposed to be 2^4 = 16 mutually exclusive regions marked out by the intersections of the 4 circles. (The last region is 0000, representing the area outside of all 4 circles.) But I counted only 13.
So I present my own model in which care was taken to include all 15 different regions as spelt out by the binary system.
A brief explanation:
The 4 events are depicted by their colours:
Red, Blue, Black and Green.
While Red, Blue and Black are the usual 3 circle Venn,
I added Green...modified to resemble a doughnut with a hole in the middle and an extension outside of the 3 circles.
This model is useful for anyone who wishes to understand the inclusion-exclusion theories and other theories based on this, e.g. Waring's Theorem, and also to visualise the De Montmort's Problem of Coincidences better. Now I wonder how did the Wikipedia poster manage to get inclusion-exclusion theory correct with a flawed model.
An alternative model was offered by my brother. (See below). Basically all you have to do is to make sure the new region(Green)splits every other existing region into two...a truly intuitive illustration of the Binary Model indeed! Maybe not too symmetrical though...
Now the problem comes alive when you try to add more and more regions. In adding the regions, we are supposed to cross the boundaries of each existing region one and only one time. Now, is this problem vaguely similar to the famous Bridge of Konigsberg Problem as proposed by Euler?
For example, if you are tasked to find the number of ways to arrange 5 identical balls in 2 urns. The formula for such a scenario is given as below:
As an aside, an ingenious way (unfortunately not mine) of interpreting the formula goes as follows:
I line up all 5 balls in a row. There are 2 urns, so I utilise an imaginary stick and place it between the 5 balls, creating effectively 2 partitions (one left of the stick, and one right). Each partition denotes an urn, so 1 stick is enough to denote 2 partitions. If there are 3 urns, 2 sticks are needed...and so on, giving:
No of sticks needed = No of urns - 1.
Then I simply find the number of ways to order all the sticks and balls, giving me:
(since the balls are themselves indistinguishable and the stick is indistinguishable, so we divide by 5! and 1! respectively.)
What if you are now told that each urn must now contain at least 1 ball each?
Simple. Using the same values, 1 ball is first distributed to each urn to ensure that each urn must now contain at least 1 ball each. That leaves us with 5-2=3 balls left to arrange with the same number of sticks (r-1), giving:
Now comes THE question:
Let the no. of ways of arranging 5 balls in 2 urns given each urn must have at least 1 ball = P1(5,2).
Let the no. of ways of arranging 5 balls in 2 urns given each urn has no restrictions on the number of balls = P0(5,2).
Is the probability of having each urn containing at least 1 ball ( which can be rephrased as the probability of having no empty urn) equal to:
No!
The number of ways to arrange 5 balls in 2 urns is not all equal in probability.
A better way to view the problem uses the analogy of states (like binary states, tri-states that electrical engineers are comfortable with).
The 2 urns represent 2 states, giving us the familiar binary system. Each ball represent one bit. Hence there are a total of:
2^5=32 possible states.
(Of course, we are now simply viewing the problem as putting n distinguishable balls into r distinguishable urns, which is also the number of ways to draw n balls from r unique types(each unique type is an urn!) with replacement, where order counts. Just like a mountaineer who always tries to find new ways to climb the same mountain, mathematicians are always trying to view the same problem from different angles, hoping to gain further insights or discover something which was previously hidden. Back to the problem:)
Breaking up the problem:
The probability of distribution of balls such that we end up with no empty urns becomes relatively clear. It is simply:
Note that 00000 and 11111 all denote 1 empty urn.
The analogy of binary system helps bring probability problem into sharp focus. Another question illustrates its power.
Cards were dealt face down from a deck of 52. What is the probability that the 1st ace encounterd occurs on the nth draw?
We now imagine a binary system of 1 (Ace) and 0 (no ace) with a total of 52 bits.
Picture the table with headers as below:
The meaning of the curly braces, which divide up the table into 2 groups, will be apparent later. But first, we define the sample space, noting that each way has equal probability of occurence.There are a total of 4 aces, to be scattered among all 52 bits. So for every row, there are 4 1s, and 48 0s. So how many rows are there?
Total number of rows possible:
Now, we introduce the restrictions. The 1st ace must occur on the nth draw.
We divide up the group into A1 to An, and An+1 to A52.
In the first group, only 1 ace resides in it, specifically in the An position.
In the second group, 3 aces are distributed among An+1 to A52.
The problem is now reduced to a matter of throwing out unwanted rows and retaining those that we want. So which are the rows that we have to throw out?
1) All those with more than 1 Ace in the group A1 to An.
2) All those with only 1 Ace in the group A1 to An, but whose 1 Ace does not reside in the nth position.
There are quite a lot of rows to throw out here. Instead of throwing out rows, we can think of the rows that we must keep. There is only one group we must keep, which is:
1) All those with 1 Ace in the group A1 to An, and whose 1 Ace resides in the nth position.
For this group, how many ways are there to arrange them? The answer lies in the other group An+1 to A52. Considering that 3 aces are to be found among An+1 to A52, and that there are 52 - n bits from An+1 to A52, we get the final answer:
Now what is the significance of multiplying the answer found above by n? Essentially it gives us the probability of finding 3 Aces in the group An+1 to A52. Without the binary system, these angles may not be so readily apparent.
Lastly, the binary system has made light of an unnecessarily complicated problem: The issue of drawing 4 Venn circle diagrams. I believe most of us were introduced to the Venn diagrams from young, first with 2 circles, then 3 circles. It is a very elegant and simple solution to many probability questions involving many intersections. Put it simply, without John Venn and his marvellous invention, my head would spin like a gyroscope everytime I encounter probability. So if 3 circle Venns have been useful, then 4 circle Venns must be even more useful. I chanced upon this diagram at Wikipedia:
http://en.wikipedia.org/wiki/Image:Inclusion_exclusion_diagram.JPG
The diagram is flawed as soon as I counted the number of states in it. Using the binary system, for each circle we denote it as ONE bit. There are 4 circles, hence 4 bits. In a 4 bit system, there are supposed to be 2^4 = 16 mutually exclusive regions marked out by the intersections of the 4 circles. (The last region is 0000, representing the area outside of all 4 circles.) But I counted only 13.
So I present my own model in which care was taken to include all 15 different regions as spelt out by the binary system.
A brief explanation:
The 4 events are depicted by their colours:
Red, Blue, Black and Green.
While Red, Blue and Black are the usual 3 circle Venn,
I added Green...modified to resemble a doughnut with a hole in the middle and an extension outside of the 3 circles.
This model is useful for anyone who wishes to understand the inclusion-exclusion theories and other theories based on this, e.g. Waring's Theorem, and also to visualise the De Montmort's Problem of Coincidences better. Now I wonder how did the Wikipedia poster manage to get inclusion-exclusion theory correct with a flawed model.
An alternative model was offered by my brother. (See below). Basically all you have to do is to make sure the new region(Green)splits every other existing region into two...a truly intuitive illustration of the Binary Model indeed! Maybe not too symmetrical though...
Now the problem comes alive when you try to add more and more regions. In adding the regions, we are supposed to cross the boundaries of each existing region one and only one time. Now, is this problem vaguely similar to the famous Bridge of Konigsberg Problem as proposed by Euler?
GMAT AWA Samples
All articles here were timed under exam conditions of 30min. So please excuse the typos, grammaticals, and sometimes convoluted logic.
1. Some believe that students are less well-equipped for college than they used to be. They say that present-day students are inadequately prepared to express themselves in writing or perform tasks that entail quantitative thinking. But they do not realise that college-bound students are trained to think creatively, and use resources, like computers, which did not even exist a generation ago.
Which argument do you find more compelling?
A school of thought believes that students are not as good as they used to be in previous generations. They are unable to match up with their previous generations both in language and logic, and are thus not as prepared for college. Instead, I find the counter-argument, that students are actually more creative than ever before, more logical and compelling, for reasons I will elaborate on.
We live in a defining era--the age of Information, heralded by the birth of the Internet. History has shown that whenever there was a breakthrough in the proliferation and dessimination of information, culture and society would blossom. For example, the invention of the printing press in the 1400s by Johannes Guthenburg resulted in the Renaissance. The Age of Information, where we are now, is no less momentous. With such a wealth of resources at the tips of our students fingers, it is natural that they should be more creative and resourceful than ever before. The Internet, together with the immensely rich content of witty blogs, cutting-edge videos and anthemic music, is testament to this fact.
Secondly, we cannot compare between different generations, and then judge them on subjective skills like thinking and writing. It is true the previous generations seemed to be more prolific and creative, but possibly we are looking into the past with rose-tinted glasses. The Jack-Keroac inspired Beat Generation was a movement in response to the 'hippie' culture, but the main reason there is no equivalent Jack Keroac in our present generation is we do not need one. We have instead, technological whiz-kids and scientists who continually define the new frontiers of science. The quantitative demands of a physicist is more gruelling than ever before. It is difficult to argue that the previous generation of students was possessed of better quantitative thinking skills.
In conclusion, the present generation of students are equally, if not more creative than students of the previous generations. And rightly so, for they have so much more resources and information to tap from, unthinkable only one decade ago. Also, we cannot compare between different generations. Each generation had their own demands, the baby boomers with the social issues, and now, our generation, with technology. Certainly, our present generation are well-equipped to tackle college and life after college.
2. Human nature, no matter how selfless is appears, is selfish. Discuss.
The author asserts that there is no such thing as altruism in human nature, and that we are inherently selfish in everything we do. Human nature is too complex an issue to make such generalisations, but upon deeper analysis, with support from philosophy and neuroscience, I agree with the author.
People tend to struggle with an emptiness in life. Philosophers from the school of thought of Kiekegaard term this inherent emptiness "existential loneliness". Some immerse themselves in a religion, start a family, embark on world adventures, while others seek solace in volunteering. All these are alleged to be manisfestations of the phenomonon of "existential loneliness". When we observe a selfless act, we can trace its roots back to the person struggling to find a meaning in life. His act of volunteering or committing altruism is his way of filling that emotional void.
Doing good and selfless often makes one feel good about himself. Developments in neuroscience has discovered that the act of committing altruism may release certain chemicals into the brain which can get people hooked, much like what romantic love does to the brain. So if you need a rush of high, you can always go out and do something good. These chemical reactions are inherent in us, and we are often unaware of them. Once the scientists have pointed this fact, it becomes clear why people are addicted to altruism.
But how about Mother Theresa? Hasn't she dedicated her whole life to helping the underpriveleged in India, so far away from her safe haven in Ireland? Mother Theresa is invariable a shining example of altruism. But people look no further than the 2nd hand accounts given by what the media wants us to believe. Some scholars who have studied her life have controversially pointed out that she was obsessed with her public image, so much so that she only granted interviews to "cordial" reporters. She made timely public appearances in a show of ultimate devotion to her cause. In short, she knew the world needed a "Mother Theresa" figure, and she boldly set out to claim her role as that aforementioned "Mother Theresa", thus writing herself into world history.
In conclusion, there are lots of basis to claim that human nature, no matter how selfless it appears, are inherently selfish. It is difficult, and understandably so, to break away from how we are wired up in our mind and body. Still, altruism can be considered to be a form of benevolent selfishess, definitely more welcome than the strain of selfishness we normally encounter. Be selfish, and help save the world!
3. The study of history is largely a waste of time because it prevents us from focusing on the challenges of the present.” Discuss the extent to which you agree or disagree with the opinion expressed above. Support your point of view with
reasons and/or examples from your own experience, observations, or reading.
The author asserts that the study of history detracts us from our present problems, and is thus largely an exercise in time wasting. While it is true that our attention and resources should be focused on the problems of now, nevertheless there are much to learn from our history. Therefore, I disagree with the strong stance of the author.
History repeats. Much of history is littered with amazing stories and lessons from which our present society has much to learn. The success of UN stems largely from the failures of the League of Nations. Ronald Reagan, probably aware of the doomed appeasement policy to Adolf Hitler, refused to stand down to the Soviet Union's arms race in the 1980s, ultimately culminating in the arms treaty pact signed between the two superpowers.
On the other hand, politicians who refuse to heed history's lessons too often find themselves walking down the slippery path of failure and doom. Geroge Bush has been forewarned of the problems caused by an invasion of Iraq by Vietnam war veterans who knew better. Despite international condemnation and warnings of another Vietnam in the making, he went ahead, and got the US stuck in a largely unsuccessful and costly operation. Ethnic cleansing in history have always been shown to be a disastrous policy, yet in our modern society, we are still forced to witness the horrors of mass slaughter based on racial prejudice from Serbia to Rwanda.
In conclusion, the study of history is still largely relevant in our modern world. A leader who is astute and wise would do well to listen to history lessons and forge policies with history in mind. Otherwise he risks committing the mistakes of his forefathers. For the sake of progress, history is still an important part of our modern world.
1. Some believe that students are less well-equipped for college than they used to be. They say that present-day students are inadequately prepared to express themselves in writing or perform tasks that entail quantitative thinking. But they do not realise that college-bound students are trained to think creatively, and use resources, like computers, which did not even exist a generation ago.
Which argument do you find more compelling?
A school of thought believes that students are not as good as they used to be in previous generations. They are unable to match up with their previous generations both in language and logic, and are thus not as prepared for college. Instead, I find the counter-argument, that students are actually more creative than ever before, more logical and compelling, for reasons I will elaborate on.
We live in a defining era--the age of Information, heralded by the birth of the Internet. History has shown that whenever there was a breakthrough in the proliferation and dessimination of information, culture and society would blossom. For example, the invention of the printing press in the 1400s by Johannes Guthenburg resulted in the Renaissance. The Age of Information, where we are now, is no less momentous. With such a wealth of resources at the tips of our students fingers, it is natural that they should be more creative and resourceful than ever before. The Internet, together with the immensely rich content of witty blogs, cutting-edge videos and anthemic music, is testament to this fact.
Secondly, we cannot compare between different generations, and then judge them on subjective skills like thinking and writing. It is true the previous generations seemed to be more prolific and creative, but possibly we are looking into the past with rose-tinted glasses. The Jack-Keroac inspired Beat Generation was a movement in response to the 'hippie' culture, but the main reason there is no equivalent Jack Keroac in our present generation is we do not need one. We have instead, technological whiz-kids and scientists who continually define the new frontiers of science. The quantitative demands of a physicist is more gruelling than ever before. It is difficult to argue that the previous generation of students was possessed of better quantitative thinking skills.
In conclusion, the present generation of students are equally, if not more creative than students of the previous generations. And rightly so, for they have so much more resources and information to tap from, unthinkable only one decade ago. Also, we cannot compare between different generations. Each generation had their own demands, the baby boomers with the social issues, and now, our generation, with technology. Certainly, our present generation are well-equipped to tackle college and life after college.
2. Human nature, no matter how selfless is appears, is selfish. Discuss.
The author asserts that there is no such thing as altruism in human nature, and that we are inherently selfish in everything we do. Human nature is too complex an issue to make such generalisations, but upon deeper analysis, with support from philosophy and neuroscience, I agree with the author.
People tend to struggle with an emptiness in life. Philosophers from the school of thought of Kiekegaard term this inherent emptiness "existential loneliness". Some immerse themselves in a religion, start a family, embark on world adventures, while others seek solace in volunteering. All these are alleged to be manisfestations of the phenomonon of "existential loneliness". When we observe a selfless act, we can trace its roots back to the person struggling to find a meaning in life. His act of volunteering or committing altruism is his way of filling that emotional void.
Doing good and selfless often makes one feel good about himself. Developments in neuroscience has discovered that the act of committing altruism may release certain chemicals into the brain which can get people hooked, much like what romantic love does to the brain. So if you need a rush of high, you can always go out and do something good. These chemical reactions are inherent in us, and we are often unaware of them. Once the scientists have pointed this fact, it becomes clear why people are addicted to altruism.
But how about Mother Theresa? Hasn't she dedicated her whole life to helping the underpriveleged in India, so far away from her safe haven in Ireland? Mother Theresa is invariable a shining example of altruism. But people look no further than the 2nd hand accounts given by what the media wants us to believe. Some scholars who have studied her life have controversially pointed out that she was obsessed with her public image, so much so that she only granted interviews to "cordial" reporters. She made timely public appearances in a show of ultimate devotion to her cause. In short, she knew the world needed a "Mother Theresa" figure, and she boldly set out to claim her role as that aforementioned "Mother Theresa", thus writing herself into world history.
In conclusion, there are lots of basis to claim that human nature, no matter how selfless it appears, are inherently selfish. It is difficult, and understandably so, to break away from how we are wired up in our mind and body. Still, altruism can be considered to be a form of benevolent selfishess, definitely more welcome than the strain of selfishness we normally encounter. Be selfish, and help save the world!
3. The study of history is largely a waste of time because it prevents us from focusing on the challenges of the present.” Discuss the extent to which you agree or disagree with the opinion expressed above. Support your point of view with
reasons and/or examples from your own experience, observations, or reading.
The author asserts that the study of history detracts us from our present problems, and is thus largely an exercise in time wasting. While it is true that our attention and resources should be focused on the problems of now, nevertheless there are much to learn from our history. Therefore, I disagree with the strong stance of the author.
History repeats. Much of history is littered with amazing stories and lessons from which our present society has much to learn. The success of UN stems largely from the failures of the League of Nations. Ronald Reagan, probably aware of the doomed appeasement policy to Adolf Hitler, refused to stand down to the Soviet Union's arms race in the 1980s, ultimately culminating in the arms treaty pact signed between the two superpowers.
On the other hand, politicians who refuse to heed history's lessons too often find themselves walking down the slippery path of failure and doom. Geroge Bush has been forewarned of the problems caused by an invasion of Iraq by Vietnam war veterans who knew better. Despite international condemnation and warnings of another Vietnam in the making, he went ahead, and got the US stuck in a largely unsuccessful and costly operation. Ethnic cleansing in history have always been shown to be a disastrous policy, yet in our modern society, we are still forced to witness the horrors of mass slaughter based on racial prejudice from Serbia to Rwanda.
In conclusion, the study of history is still largely relevant in our modern world. A leader who is astute and wise would do well to listen to history lessons and forge policies with history in mind. Otherwise he risks committing the mistakes of his forefathers. For the sake of progress, history is still an important part of our modern world.
Subscribe to:
Posts (Atom)