The first thing they always did was count you.
We're going to be a bit more sophisticated than the counting you did in high school, but I imagine this will be familiar to a lot of you anyway. A lot of the stuff I write about has to do with discrete, finite probabilities. In order to solve these, you typically look at how many possible favorable outcomes there are an divide them by the number of total outcomes. In order to do this, we first have to know how to count things.
Suppose you have 6 people in a group and you want to put them in a line. How many ways are there to do this?
You start by picking someone to put in the front of the line (6 ways), then you have only 5 people left to pick, so you pick someone to go second (5 ways), then third (4 ways), etc. This gives a total of 6*5*4*3*2*1=720 ways to line up your people! You can generalize this approach to n people, you pick someone for each spot in the line successively to get n*(n-1)*(n-2)*...*3*2*1. This is written as n! (spoken as "n factorial"). We also define 0!=1 for reasons that may not be apparent, but will make things easier later.
Ok, now suppose we have 8 people and we want to line up only 3 of them. The procedure is the same as above, first we pick someone for the first spot, then the second and finally the third. This gives us 8*7*6=336 possibilities. Note that we can write that as 8!/5!. In general, if we want to line up k people out of a group of n people, there are n!/(n-k)! ways to do this. Note that if n=k, this is n!/0!=n!, which is the exact same result as in the previous section.
Finally, suppose we have a group of 5 people and we want to choose a committee of 3 people from this group. How many ways are there to do this?
If we try to count these groups by lining up people as in the last example, we will overcount. For instance, for the group including A,B, and C we will count ABC, ACB, BAC, BCA, CAB, and CBA. Note that although these are different orders, they are the exact same group. If we think about it carefully, we will see that we have counted each group of 3 people exactly 3! times. So in order to count them, we simply line up our group of people and then divide by 3! to account for the fact that we've counted each group of 3 people 3! times. This gives us 5!/(3!2!)=10 ways to do it. In general, if we want to pick a group of k things from a set of n objects, this is denoted by
The above is spoken as "n choose k" and is also call a binomial coefficient. I will frequently write this as n(C)k. It gets its name from the expansion of the binomial (a+b)^n
To prove the above fact, write (a+b)^n as (a+b)(a+b)...(a+b). When we individually multiply all the terms out, we notice that each term will have the form a^k*b^{n-k} since our expansion will be the product of one thing from each of the n (a+b) terms above. Then, we ask how many of each of these there are. Well, each if these will occur when we have "chosen" k a's from terms above and left the rest as b's. This is by definition n(C)k.
Ok, now here's an interesting proof using the binomial expansion.
Theorem
For n>0, given an n element set, there are the same number of even subsets as odd subsets
We are counting both the empty set and the full n element set as subsets in this argument. If you're anything like me, your intuition is write up the summations and try to simplify them somehow. This is pretty hard work and will likely get you nowhere. You could also try an inductive proof, which wouldn't be too bad. However, the following proof is extremely elegant:
The two sums above represent the number of even element subsets and the number of odd element subsets. Since their difference is equal to 0, they are the same.
Problems
I will post two problems for this inaugural edition. The first is a bit easier and has some relationship to the stuff written above. I know of 3 different ways to do it. Remember, this isn't Nam-there are rules.
The second one is harder and has nothing to do with binomial coefficients.
1. Ron Gardenhire has no idea how to fix his impotent lineup. He decides to pull a Billy Martin and put the names of the 9 hitters he is playing today into a hat and then draws randomly for the batting order. Given that Rondell White and Nick Punto's names are both in the hat, what is the probability that they end up in 2 of the top 4 spots in the lineup?
2. (a) BrianS and Rhubarb_Runner have a jar with 21 stones in it. During each player's turn, they may remove either 1,2 or 3 stones from the jar. The winner is the person who removes the last stone from the jar. Assuming BrianS goes first, determine which player has a winning strategy.
(b) Same question as above, except now our jar contains n stones and during each players turn they may remove any number of stones between 1 and k. (The player with the winning strategy may depend on n and/or k)
Oh, "The Nation" has problems, has it?! Passing the buck?
1: the probability is well over 90% that Punto and RonDL will be 1-2 in the lineup. Murphy works that way.
2a: are they kidney stones? If so, I have none. But that doesn't necessarily make me the winner. And this is a trick question, as brianS does not capitalize his first name. You're right to assume he'd go first, though - he's that kind of game player.
I knew someone would make some kind of joke like this. You can thank me for setting you up.
Yes, thank you.
GH, I think if you had been my math teacher somewhere along the line I might not have switched to history. I think I just learned more than I did in 4 years of college. And I still have a math minor.
Thank you.
Are we supposed to post actual answers?
Moss says #1 is 12/9! -- To satisfy the criterion, Punto could bat any of 1-4, each of which leaves three ways for White to fill a remaining (1-4) slot. That gives 12 ways to satisfy the criterion, out of a total number of 9! ways to order the lineup. In fact, it's only 1 in 30,240.
#2 -- brianS has a winning strategy. He first takes 1 stone, then each time it is his turn, he reduces the number of remaining stones to a multiple of 4 (16, 12, 8, 4). This forces RR to ultimately reduce the number below 4, enabling brianS to grab the remainder.
Moss doesn't know how to show that with your formulae, though.
#2b -- It seems the first player who has to draw stones when the number is a multiple of (k+1) before his draw is the loser. Therefore, if n/(k+1) is a whole number, then the first player is the loser; otherwise the first player can initially reduce the number to a multiple of (k+1) and force a win.
Edit: I whited out the answer for those who don't wish to have it spoiled. --GH
Geeze Moss. Didn't you read. And I quote
Please define "some time has passed."
Well, the main point is that I don't want people to read the post and then scroll immediately down a few comments to see the answer staring them in the face.
Ideally, you should wait to post the solution until it seems like most people have either solved it or given up.
I don't want people to feel like they have to wait too long, or to feel like they can't post anything either, which is why I leave the rule vague.
I would see the original discussion for an idea of what I have in mind.
http://stickandballguy.com/blog/2007/10/09/on-playoffs-college-football-and-doping/#comment-102701
I solved the problem right away and then ubelmann got it without posting the answer. People posted their ideas about solving it and I dropped a few hints. Then, eventually I decided people were pretty much done with it and wanted to know the answer so I posted it.
Moss is only being a pain.
Please post how to white/gray out the posts, though, if it hasn't been posted already...Moss can do that.
Moss, you type the following before your text: <font color="white">
and then you type the following after your text: </font>
I you are in a grey box, instead of white you type f8f8f8
I am going to put together a macro for GH so that he can have all the rules at the end of a post without having to type it every time.
Your answer for #1 is incorrect. There is a much greater chance than that!
For #2, your answer is correct. I whited it out so people who don't want to see it can ignore it.
Here is some stuff to make sure that the answer doesn't show up in the comment preview. Nick Punto is not very good at baseball. Joe Mauer is very good at baseball. Justin Morneau is from Canada. Ron Gardenhire needs to spend some quality time with Earl Weaver.
Looks like the appropriate color here is #f8f8f8
Moss is correct that there are 12 ways to arrange Punto and Rondelle in the top four spots. However, for each way to arrange Punto and Rondelle, there are many ways to arrange the rest of the hitters. With 7 spot left over each time Punto and Rondelle have already been placed in the lineup, there should be 7! different ways to arrange the lineup for each way you can put Punto and Rondelle in the top four spots. With no restrictions, there are 9! ways to arrange the lineup.
So, it looks like the answer is (4!/2!)*(7!)/(9!), which reduces nicely to (4*3)/(9*8), or 1/6. I feel like there should be an easier way to get this answer, but maybe not.
More stuff just in case the back end of my answer shows up in the comment preview for some reason.
Moss thought the (1/30k) answer was way too small, but wasn't sure why.
Time to go to the exhaustive method.
NOTE -- Moss doesn't know how to do the white-out!! What's the secret?
The odds of them batting (1,2) are (2/9)(1/8)=2/72.
The odds of them batting (1,3) are (2/9)(7/8)(1/7)=2/72.
...[same results for (1,4), (2,3), (2,4)]
The odds of them batting (3,4) are (7/9)(6/8)(2/7)(1/6)=2/72.
The sum is 12/72 or 1 in 6.
http://stickandballguy.com/blog/2007/10/14/new-column/#comment-103704
Don't worry, Moss, your answer is still there, it's just been whited out.
Yes, this is correct and yes, there is a simpler way to do it.
One of the neat things about this problem is that there are many different ways you can count stuff and different things you can count to arrive at the same answer. There is also another solution which is the simplest of all...
Firing Punto and White?
LOL...That would make this problem trivial and solve a lot of other problems in the process!
For completeness, for a randomly selected k and n, n>=k, the first player has (k-1)/k chance of winning and the second player only has a 1/k chance. (The outcome is determined without even playing the game.)
This is (almost) true. You need to replace k by k+1 above. Also, it's not necessary for n>k. If k<=n, then the first player can win just be taking all the stones. It's not a very sporting game though!
And that's why brianS always goes first.
Oops, yeah that's what Moss meant. k/(k+1) and 1/(k+1).
People! There's a game going on here. Even if the Rox are running away with it.
Focus!!!!
btw, GH. "discrete, finite probabilities"?? I sure hope they are finite.
I suppose I should say "discrete, finite number of probabilities". There are many problems which are discrete but have an infinite number of different outcomes, each with its own distinct probability!
which all summ to one, which is the loneliest number. Which brings us back to ubelmann's post about dating.
Is the WGOM written in some other language now? I don't understand a single thing in this post. I mean, numbers? What in God's name are those?
But seriously folks, don't ever do computer dealings with Sony. Or at least don't count on their warranty/repair service.
I don’t understand a single thing in this post
but some parts are interesting, right, NG??
Come check out my online pharmacy! v1a g-ra at deap disc0unt! No 0bligati0n downl0ad casin0 $$$ pf1zer!
New guy's new avatar:
my non-cheating answer to 1. *edit* I foo-barred by mis-reading the problem, as WELL as doing what I thought the problem was incorrectly. Now that I see the correct solution, I hang my head in shame.
first, 9(C)4 -- there are 9!/(4!*5!) possible lineup permutations. We are interested only in the permutations in which Punto and White occupy the first two slots.
so we are interested in 2*[7!/(2!*5!)] of the permutations (since either NP leads off or RW leads off in the orders of interest).
2*[7!/(2!*5!)] = 7!/5!
(7!/5!)/(9!/(4!*5!)) = (7!*4!*5!)/(9!*5!) = 4!/(9*8) = 1/3
problem 2. blah blah Derek Jeter blah blah Troy Tulowitski blah blah blah blah Troy Jeterwitski.
if there are 1-3 stones remaining, the player whose move it is, wins. Hence, the goal at any point in the game is to either (a) end the game or (b) leave 4+ stones in the bin.
In the Mth move, if there are 1-3 stones remaining, you win. If there are 4 stones remaining, you lose. If there are 5-7 stones, drive the number to 4 and you are guaranteed to win. If there are 8, you lose, because no matter how many you take (1-3), your opponent will subsequently drive the number to 4. If there are 9-11, you drive the number to 8.
If there are 12 remaining, you lose. No matter how many you take, your opponent will then drive the number to 8; you take however many, your opponent drives the number to 4, etc.
this generalizes. If there is a multiple of 4 remaining at your turn, you lose. If not, your strategy is to drive the number down to the next multiple of 4. since I move first with 21 stones remaining, I take one stone, Rhu_Ru capitulates. I win.
blah blah Derek Jeter blah blah Troy Tulowitski blah blah blah blah Troy Jeterwitski.
Never capitulate! Never surrender! *damn that Corey Hart and his Canadian sunglasses!*
Johan Santana is a great pitcher. Sandy Koufax is overrated. But not as much as Nolan Ryan. Alright, I figured out an easier way:
There's a 4/9ths chance that Punto falls in the top 4 and a 3/8ths chance that Rondell falls in the top 4 after Punto has been placed in the top 4. (4/9)*(3/8)=1/6. (I should have realized this when I was simplifying the fraction above--it was practically staring me in the face.)
Also, I realized that the more straightforward way of stating my solution above would be to say that the probability is (4 choose 2)/(9 choose 2)--the ratio of the number of ways to place two things in four spots to the ratio of the number of ways to place two things in nine spots.
Alright, I'm all combinated out now.
yea, I was almost to the latter solution. but your first, "easier" was is nifty and, now that you state it, seems obvious. Ain't that always the way of it?
Yes, that is the easiest solution to the problem.
I still know one more solution which counts things in a distinctly different way!
Well, there is 5/9 probability that Punto is not in the top 4, and an independent 5/9 chance that RonDL is not in the top 4. However, you would have to take back out the chance that they both are in the bottom 5, which would be 5/9*4/8 = 5/18.
So 5/9 + 5/9 - 5/18 = 5/6 is the chance that at least one of them is in the bottom 5, which would leave a 1/6 chance that neither of them are in the bottom 5.
Sorry should have put that in white text like
this test
The problem that you had is you had curly quote marks.
It seems like most people have gotten #1 by now, so feel free to post comments about it in non-white text.
The answer is 1/6. This has been derived in several different ways so far.
The first way is the moss/ubelmann method, which counts the number of total ways to set up a batting order. The total number of ways to do this is 9!. To count the number of ways to place Punto and RonDL in the top of the order. We start by picking a place for Punto (4 ways), then pick a place for RonDL (3 ways), then pick a spot for everyone else (7! ways). This gives a probability of:
12*7!/9!=1/6
Another way to look at it which is a bit simpler is to just use the fact that spots for the players are picked randomly. Instead of picking the order randomly, you can think about it as picking lineup spots for the two players. First, we pick a spot for Punto which has 4/9 outcomes that land him in the top 4. Next, we pick a spot for RonDL. Since Punto already occupies 1 of the "good" spots, there are 3 spots in the top four left and 8 total spots, so the probability that he is in the top 4 given that Punto is already in is 3/8. So the probability that both of them get in is: 4/9*3/8=1/6.
There are slight variations of the above as well. Ubelmann pointed out a variation of the first one and Diggity Dino has essentially a variation of the second one.
There is one other solution that nobody has gotten yet (and I don't think that anyone will). For whatever reason, this is the first solution that came to me, even though it seems the least straight forward.
Think about the different ways to make up the top 4 spots in the lineup. There are 9(C)4 of these. Now, think about the number of ways to pick a top 4 including Punto and Rondelle. 2 spots must be occupied by them, so there are only 2 spots left to pick and 7 players to pick from, so there are 7(C)2 of these. Thus, our probability is 7(C)2/9(C)4=21/126=1/6.
yea. I had the 7(C)2 part, but for some reason read the problem as having LNP and Dell in the first TWO spots and that we were only interested in the first 4 spots in the order (and then berted THAT up).
problem 2, GH?
this is fun, even if I suck at solving them.
Ok, so problem 2a was originally a challege on Survivor: Thailand. I figured it out immediately and then sat there laughing as both tribes screwed it up. I tend to like problems where there is more than one solution, unfortunately this isn't one of them. Once you prove that one of the players has a winning strategy, there is obviously no counter-strategy that is going to work. This is the definition of a winning strategy.
Sometimes there may be more than one winning strategy for one of the players, but this isn't one of those problems. Part (a) is just a specific instance of part (b), so once you know the solution to (b), part (a) is trivial. I often find it useful in problems like this to try out particular instances of the game to see if I can come up with a conjecture for the solution. It is often easier to do this if you don't see the solution right away.
The second player will have a winning strategy if n is multiple of k+1 and the first player will have a winning strategy otherwise.
The idea for a winning strategy here is for the number of stones left at the end of your turn to always be a multiple of k+1. If is a multiple of k+1 at the end of a player A's turn, then the other player has to take some number of stones between 1 and k. Let m be the number of stones the other player takes. After his turn, there will be n-m stones left, which cannot be a multiple of k+1 (do you see why?). Next, the original player takes k+1-m stones (which is also a legal number of stones to take, proof left as an exercise for the reader). So after both players play, there will be n-m-(k+1-m)=n-(k+1) stones left. This is also a multiple of k+1. Play continues in this way until we have k+1 stones left, then player B takes some number of stones, leaving k or fewer at which point player A takes them all 4TW.
We see that if n is a multiple of k+1, then the second player will be able to implement this strategy. Otherwise, the first player takes the correct number of stones to make it a multiple of k+1 and implements the above strategy.
In part (a), 21 is not a multiple of 4, so BrianS has a winning strategy by taking a single stone on his first turn.
People seemed to do well with this problem and there were several people who posted correct solutions. More discussion can occur, if people have questions. I will up the ante for next week and come up with a harder problem.
Another note about problem 2. Because there is no draw condition in this game, one player or the other must have a winning strategy (assuming that player plays optimally).
Also, we need the game to be guaranteed to finish in a finite number of turns for the above to be true.
which is true for any finite n, given the specified play of the game requires a player whose turn it is must take between 1 and k<=n stones, right?
Yeah, in this case we know that the game will finish in at most n turns since each player is forced to remove at least one stone. If we add the option for a player to take 0 stones, the game could continue indefinitely. In fact, once we got down to k+1 stones the best strategy for each player would be to pass because taking any stones would result in a loss, so the game would continue indefinitely.
This concept is true for not only this game, but for finite games in general. Off the top of my head, the only other game of the sort is Hex. There is no possible tie in Hex, so one player or the other must have a winning strategy.
Many other games also include a draw condition. So assuming optimal play from both players, the game will result in a forced win, loss, or draw for the first player. For instance, Tic-tac-toe and Connect 4 are both forced draws assuming optimal play. Games like Othello, Chess, and Go all have a forced result, but because of the complexity of the games, it is unknown what the result is.
I was hoping this was a Ron Paul thread... With that said, I firmly agree that Gardy is clueless.