EPT
Difficult Math Puzzle !
| Blogs > kdog3683 |
|
kdog3683
United States916 Posts
| ||
|
Muirhead
United States556 Posts
2*(2n-k-1 C n-1)*(1/2)^(2n-k) From the first 2n-k-1 matches pulled, you must choose which n-1 are pulled from the box that first runs out. | ||
|
Fontong
United States6454 Posts
| ||
|
Deleted User 3420
24492 Posts
im curious how this will be answered it seems like it might be easier than a couple of the other ones lately, tho | ||
|
Jonoman92
United States9107 Posts
| ||
|
naonao
United States847 Posts
1-(1/2)^n since having k<n only means that at least 1 match was pulled out of the other box. Then (1/2)^n is the probability that all of the matches were pulled from one box, which is the only possible way for k >= n. So you subtract it from 1 to find the probability of k<n | ||
|
Pliers
Canada42 Posts
On May 15 2009 04:08 Muirhead wrote: + Show Spoiler + 2*(2n-k-1 C n-1)*(1/2)^(2n-k) From the first 2n-k-1 matches pulled, you must choose which n-1 are pulled from the box that first runs out. Not sure If I agree with you. (1/2)^(2n-k) I think you're assuming that for every match drawn till 2n-k you would have 1/2 probability for the matches in either box however when a match is drawn it is not replaced therefore the probability changes. Not sure how you have (2n-k-1 C n-1) since the OP asked what the probability of the box having k matches left when the other box is empty. My logic is one box must run out therefore there is 2 choose 1 boxes and n choose n matches for one of the boxes and n choose n-k for the other. While the total probably is 2n choose 2n-k giving: [2*1*(n C n-k)]/(2n C 2n-k) | ||
|
Muirhead
United States556 Posts
| ||
|
Macavenger
United States1132 Posts
On May 15 2009 04:08 Muirhead wrote: + Show Spoiler + 2*(2n-k-1 C n-1)*(1/2)^(2n-k) From the first 2n-k-1 matches pulled, you must choose which n-1 are pulled from the box that first runs out. + Show Spoiler + Where do you get that initial factor of 2 from, and why choosing n-1? Shouldn't you be choosing which n come from the empty box, since if I read the question right, he doesn't know exactly when he emptied it? I feel like it should just be (2n-k C n) * .5^(2n-k) Edit: Oh, the 2 comes from the fact that he could be pulling either box to find empty I guess? | ||
|
Muirhead
United States556 Posts
On May 15 2009 04:52 Macavenger wrote: + Show Spoiler + Where do you get that initial factor of 2 from, and why choosing n-1? Shouldn't you be choosing which n come from the empty box, since if I read the question right, he doesn't know exactly when he emptied it? I feel like it should just be (2n-k C n) * .5^(2n-k) + Show Spoiler + The factor of 2 comes from the fact that there are two boxes. The n-1 comes from the fact that the box of the (2n-k)th match is fixed. | ||
|
Pliers
Canada42 Posts
On May 15 2009 04:56 Muirhead wrote: The factor of 2 comes from the fact that there are two boxes. The n-1 comes from the fact that the box of the (2n-k)th match is fixed. How is it fixed if it wasn't specified which box he drew it from? All we know is that once he drew the 2n-kth match one of the boxes is empty. | ||
|
Muirhead
United States556 Posts
| ||
|
Macavenger
United States1132 Posts
On May 15 2009 04:56 Muirhead wrote: + Show Spoiler + The factor of 2 comes from the fact that there are two boxes. The n-1 comes from the fact that the box of the (2n-k)th match is fixed. + Show Spoiler + I don't see how the (2n-k)th match is fixed according to the problem statement, though. The way I read it, he pulls a box out (I assume when he needs another match) and finds it was already empty; that the last match must have come from that box is not specified. For all we know, he could have just emptied it, or he could have emptied it 2 draws ago, or he could have pulled the first n matches from that box and then the remaining n-k from the second before discovering the first was empty. Thus, we should be able to choose any n of the 2n-k matches as coming from that box, no? | ||
|
Pliers
Canada42 Posts
On May 15 2009 05:06 Muirhead wrote: Just work out some small cases like n=3, k=2 and you'll see what I mean No I don't see what you mean and you should read my response to your logic like I did yours. Either prove me wrong or defend your logic; simple. Having said that, can we focus on the correct solution to this problem now? | ||
|
qrs
United States3637 Posts
+ Show Spoiler + Let's call the matchboxes Head and Tail and count the number of ways to make n selections from each box. That would be (2n)!(/n!n!). Now let's count the number of ways to make n selections from each box, where the last k selections are all "heads". That's easy: we just remove k heads from the scenario, and one "tail" (for the last match picked from Tail) and count how many ways there are to arrange the remainder. That would be (n-k + n-1)!/(n-k)!(n-1)! By symmetry, it's the same number for the case where the last k are tails. So dividing the number of cases we are looking for by the number of possible cases, we get the probability: 2*[(2n - k - 1)! * n! * n! ]/ [2n! * (n - k)! * (n-1)!] We can simplify that a little bit, at least: 2*[(2n - k - 1)! * n! * (n-1)]/ [2n! * (n - k)!] I don't know if there is a way to simplify it further. PS: the formula breaks down when k = 0. That's the only case where the specification "first box to empty" makes a difference. In every other case, we guarantee that the box we are looking at empties first by making k of its matches the last to be chosen, but when k=0, of course, that doesn't work. For that case, I'll have to just specify separately that f(0) = 0, since there is no way to finish both boxes at the same time while picking one match at a time. I wonder if anyone's formula was general enough to encompass that case. Muirhead, your answer is (partly) wrong on a technicality... | ||
|
aznmathfreak
United States148 Posts
Assuming that either box has equal chance of being picked. Each time he picks, he has a 1/2 chance of picking a certain box, either box A or box B. Let's ignore the order that he picks for a second. He has to pick box A n+1 times and box B n-k times. Each one's odd of being picked is 1/2. Therefore, the chance of him picking that is (1/2)^(n+1) x (1/2)^(n-k), or... (1/2)^(2n-k+1). Now, if we factor in the order. Since it doesn't matter which order the matches are picked, so long as the last pick was the empty box, we can think of it as out of 2n-k picks, we have to pick n of which are from box A. So it's a combination of 2n-k picks, n of which has to be from box A. There are (2n-k C n) ways to pick it. Therefore the solution is (2n-k C n) x (1/2)^(2n-k+1) Edit: If you switch box A and box B, you have another set of symmetrical cases that would also satisfy the conditions, So there is a factor of 2 like Muir suggested earlier. 2(2n-k C n) x (1/2)^(2n-k+1) or (2n-k C n) x (1/2)^(2n-k) | ||
|
qrs
United States3637 Posts
On May 15 2009 05:11 Macavenger wrote: Ah, that's an interesting point, but unless we assigned some kind of probability function to his absent-mindedness, it would not be possible to give an answer for that case, so since the question was posed as a puzzle, it's probably fair to assume that he discovers that the box is empty as soon as he tries to pull a match from it (or at any rate when his pipe refuses to light).+ Show Spoiler + The way I read it, he pulls a box out (I assume when he needs another match) and finds it was already empty; that the last match must have come from that box is not specified. For all we know, he could have just emptied it, or he could have emptied it 2 draws ago, or he could have pulled the first n matches from that box and then the remaining n-k from the second before discovering the first was empty. Thus, we should be able to choose any n of the 2n-k matches as coming from that box, no? | ||
|
qrs
United States3637 Posts
On May 15 2009 05:05 Pliers wrote: How is it fixed if it wasn't specified which box he drew it from? All we know is that once he drew the 2n-kth match one of the boxes is empty. You are right. I was wrong. | ||
|
Muirhead
United States556 Posts
The only thing I can see different about your solution is the denominator [2n! * (n - k)! * (n-1)!], but I don't understand this denominator and why it shouldn't just be 1/2^(2n-k) since he has a 50% chance of picking H or T each time. I still like my solution except when k=0 and it seems to agree with brute force checking of small cases  | ||
|
qrs
United States3637 Posts
On May 15 2009 04:08 Muirhead wrote: + Show Spoiler + 2*(2n-k-1 C n-1)*(1/2)^(2n-k) From the first 2n-k-1 matches pulled, you must choose which n-1 are pulled from the box that first runs out. On May 15 2009 05:54 aznmathfreak wrote:+ Show Spoiler + The person had to have picked 2n-k+1 times. n times from the empty box of matches and n-k times from the box of matches with k matches left, and the +1 is from the last time the person picks and ends up picking out the empty box. Assuming that either box has equal chance of being picked. Each time he picks, he has a 1/2 chance of picking a certain box, either box A or box B. Let's ignore the order that he picks for a second. He has to pick box A n+1 times and box B n-k times. Each one's odd of being picked is 1/2. Therefore, the chance of him picking that is (1/2)^(n+1) x (1/2)^(n-k), or... (1/2)^(2n-k+1). Now, if we factor in the order. Since it doesn't matter which order the matches are picked, so long as the last pick was the empty box, we can think of it as out of 2n-k picks, we have to pick n of which are from box A. So it's a combination of 2n-k picks, n of which has to be from box A. There are (2n-k C n) ways to pick it. Therefore the solution is (2n-k C n) x (1/2)^(2n-k+1) Edit: If you switch box A and box B, you have another set of symmetrical cases that would also satisfy the conditions, So there is a factor of 2 like Muir suggested earlier. 2(2n-k C n) x (1/2)^(2n-k+1) or (2n-k C n) x (1/2)^(2n-k) Interesting, the logic of each of you seems compelling, yet you give different answers. I'm trying to decide which is wrong... Edit: OK, azn is right. Muirhead and I both overlooked the significance of "(after absentmindedly placing the box back in his pocket after using the last match)" | ||
| ||
