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 States9109 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)" | ||
|
qrs
United States3637 Posts
On May 15 2009 06:28 Muirhead wrote: qrs I don't understand what's wrong (except in case k=0 which doesn't make any sense anyways) No, that's all I meant: k=0. It makes sense, just it's a special case. It wasn't a serious error in your answer, of course, just a technicality. I assumed that our answers worked out to the same thing otherwise. Let me recheck that. Edit: Yeah, I assume it's the same: I wrote 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)!] obviously not the most readable notation, and you probably looked at the bottom version and assumed that the last bit of the numerator was (n-1)!, like yours, so the denominator made no sense. But it was just (n-1) and it was coincidental. My method was a bit different from yours: I let the man keep selecting until both boxes were finished and then counted how many of those satisfied the problem's requirements. Your way is a little nicer, probably: it seems clumsy to be counting picks that he didn't make. Still, it should work out to the same. Edit2: Anyway, both of us were wrong, I think. Pliers and aznmathfreak were right. We didn't pay attention to the line "(after absentmindedly placing the box back in his pocket after using the last match)". | ||
|
Dromar
United States2145 Posts
(2C1)(nCn)(nCn-k)/(2nC2n-k) = 2(nCn-k)/(2nC2n-k) Explanation: There are 2 boxes, choose one to be empty at the end. In that box, there are n matches, choose n of them. In the other box, there are n matches, choose n-k of them. Finally, in total, there were 2n matches, and you chose 2n-k of them. This problem is very similar to a deck of cards, if you think of splitting the deck into two piles beforehand (ex, red and black). | ||
|
food
United States1951 Posts
but sometimes human mind evolves at a rapid rate | ||
|
Malongo
Chile3472 Posts
| ||
|
igotmyown
United States4291 Posts
I'm wondering if there's a simplified answer to a more difficult version: what's the probability of winning n games before the opponent wins k games. | ||
|
ThaddeusK
United States233 Posts
i have not read other answers because i wanted to try it myself. so if this has been said already, i apologize i would try this a binomial probability problem, where pulling from the empty box is a failure, and pulling from the non empty box is a success, so you find probability of n-k sucesses in 2n-k trials, where the probability of success and failure is .5 (2n-k)!/((n-k)!(n!)) * (.5)^(n-k) * (.5)^(n) that looks really ugly in text, but its just this with n= 2n-k and k = n-k | ||
|
qrs
United States3637 Posts
On May 15 2009 09:12 igotmyown wrote: This is more a matter of being careful than being difficult. I'm wondering if there's a simplified answer to a more difficult version: what's the probability of winning a best of 2n-1 series (whoever wins n games first) if you're down k games. It depends how many games are left, of course. So you're asking, in essence, if player X needs x games to win and player Y needs y games to win (where y = x - k), what is the probability of Y winning. OK, changed everything. We need to know how many arrangements there are of y wins by Y and up to x -1 wins by x. The up-to bit is annoying: I'd rather not use a sigma. Fortunately, it does not actually make a difference. So let's count the arrangements of y wins by y and x -1 wins by X. There are (y + x -1)! / [y! (x-1)!] of those. (If you want to know what the match result looks like, just ignore the final x's in each case.) By symmetry, of course, there are (y + x -1)! / [x! (y-1)!] cases where x wins. To make the answer look simpler, let's just call the first number A and the second number B. Probability of Y winning the match is A / (A + B) Let's see if this simplifies: + Show Spoiler + (y + x -1)! / [y! (x-1)!] / (y + x -1)! / [y! (x-1)!] + (y + x -1)! / [x! (y-1)!] (y + x -1)! / [y! (x-1)!] / (y + x -1)! * (1/ [y! (x-1)!] + 1/ [x! (y-1)!] ) 1/ [y! (x-1)!] / (1/ [y! (x-1)!] + 1/ [x! (y-1)!] ) 1/ [y! (x-1)!] / ([x! (y-1)!] + [y! (x-1)!] / [y! (x-1)!] * [x! (y-1)!] ) [y! (x-1)!] * [x! (y-1)!] / [y! (x-1)! * ([x! (y-1)!] + [y! (x-1)!)] [x! (y-1)!] / ([x! (y-1)!] + [y! (x-1)!)] [x! (y-1)!] / (x! y!/y + y! x!/x) [x! (y-1)!] / (x! y! (1/y +1/x)) (x! y!/y) / (x! y! (1/y +1/x) 1/y / (1/y + 1/x) 1/y / [(x + y)/yx] yx / y(x + y) x / (x + y) and I am back to the same answer. Unbelievable. well, someone will correct me if I have erred, I am sure. Right now, it's looking to me like arrangements of wins are actually irrelevant, although I am not sure why. + Show Spoiler [original method] + We need to know how many arrangements there are of y wins by Y and up to x wins by x. The up-to bit is annoying: I'd rather not use a sigma. So let's count the arrangements of y wins by y AND x wins by X. There are (y + x )! / [y! (x)!] of those. In how many of those does y win the match? Well, in all cases where the last win (the guaranteed irrelevant one) is by x. So then, assuming that each player has an equal probability of winning, your answer is: (y + x- 1)! / y! (x-1)! / (y + x )! / [y! (x)!] We can do some canceling: x / (y + x) | ||
|
igotmyown
United States4291 Posts
On May 15 2009 09:49 qrs wrote: It depends how many games are left, of course. So you're asking, in essence, if player X needs x games to win and player Y needs y games to win (where y = x - k), what is the probability of Y winning. We need to know how many arrangements there are of y wins by Y and up to x wins by x. The up-to bit is annoying: I'd rather not use a sigma. So let's count the arrangements of y wins by y AND x wins by X. There are (y + x )! / [y! (x)!] of those. In how many of those does y win the match? Well, in all cases where the last win (the guaranteed irrelevant one) is by x. So then, assuming that each player has an equal probability of winning, your answer is: (y + x- 1)! / y! (x-1)! / (y + x )! / [y! (x)!] We can do some canceling: x / (y + x) edit: and the simplicity of the reduced form suggests a better way of doing this: Ignore the arrangement of wins--that's a red herring: Just think about the possible ways that the match can end. For example, if you need 3 wins and I need 5, it could finish with: 3:0 5:0 3:1 5:1 3:2 5:2 3:3 3:4 (y + x) possibilities (one of us gets all his wins: the other gets from 0 to all but one of his wins). x of them are good for me (the ones where you don't get all your wins). That's it. Different arrangements do not have equal probabilities of occurring. | ||
|
qrs
United States3637 Posts
edit: redid everything a different way, still got same answer Edited my answer above now. _______ OK, maybe this is a better way to think of it: Suppose we have two equally skilled players, Bob and Mike, just to give them names, competing against each other to win 3 games. It stands to reason that since both are equally skilled, and both are trying to do exactly the same thing, their tasks are equally hard. Therefore we split the chances between the two of them and say that each has a 50% chance of winning. Now suppose that Bob has to win 3 games while Mike has to win 5. This time, Mike's task is 5/3 as hard as Bob. Bob is the 5:3 favorite, making the odds of his winning 5/8 and the odd's of Mike's winning 3/8. | ||
|
igotmyown
United States4291 Posts
 1+4) chance of winning the series. | ||
|
qrs
United States3637 Posts
On May 15 2009 17:02 igotmyown wrote: You're omitting the 1/2^(n+r) values. Take the 2004 Boston Red Sox being down 3-0 to the yankees. Boston does not have a 1 1+4) chance of winning the series.You're right. I think my mistake was in counting only the outcomes that actually happen (with meaningless games not played) and assuming they all had the same probability, whereas really they don't, because "3-0 and wins" is shorthand for all the possible (unplayed) outcomes that begin with 3-0. If I'm going to take the count-the-outcomes approach, I had better count them all. So let me redo this as if it were a showmatch, where all games are played: P= 2^(y + x - 1) outcomes possible. F= (y + x - 1 CHOOSE y) + (y + x - 2 CHOOSE y + 1)...(y + 0 CHOOSE y) favorable outcomes. (There's probably a slicker way to count them but I can't think of one at the moment.) Total = F/P. So the Red Sox would have a 1/16 chance (but that was your point). | ||
| ||
