I ran into a little coincidence last week. There was a news story about an American Idol staffer claiming that the fix was in, and that the final four contestants had already been chosen. At the time, there were 11 contestants remaining on the show. Maybe the staffer just made this up - what are the odds that they could just guess the correct final four? The number we want is the number of ways to choose 4 people from a group of 11, and this is just the same calculation as was done in my Arby's Algebra post a few weeks ago. There are 330 possible final fours from a pool of 11 contestants, so the odds of guessing correctly are 1 in 330, or about 0.3%.
Of course, this quick calculation ignores the fact that not all contestants are equal, as some are known to be popular and so on.
Tuesday, March 31, 2009
SoftwareCEO Article
SoftwareCEO has an interesting article about the company I work for, Stonefield Software.
Monday, March 23, 2009
Formula Testing
Just testing a way to display formulas. If this works, it might make things clearer for posts like the Arby's one from a little while ago.
Saturday, March 14, 2009
Happy Pi Day!
Today is March 14 - 3.14. Celebrate by having some pastry, or by measuring some circumferences.
Friday, March 13, 2009
Arby's Algebra
Arby's has recently had a commercial announcing their current deal, where you can choose 4 items from a list of 8 choices. They mention that this gives you 330 different options. Counting up this total is a nice example of combinatorics, so let's see how to figure out the total value.
Before getting into the math, it's helpful to assign a number to each of the eight menu choices. Rather than talking about an order as sandwich, fries, drink, apple turnover, it's simpler to call this 1,2,3,4. In the items below, when something like item 1 is mentioned, that just means I'd rather type "1" than "roast beef sandwich".
There are some approaches that are reasonable, but that don't give the right answer. First, you might consider that you have 8 choices for each of your 4 items, and simply count up 8*8*8*8, which gives 4096. This gives the total number of four-digit numbers where all the digits are from 1 to 8. The problem is that this double-counts some orders: the orders 1,1,2,3, 1,2,3,1, 3,2,1,1 are all counted as separate orders, when really they are the same.
Another approach is the 8 choose 4 method. The logic of this is that we have 8 items and we will choose 4 of them. There are 8 choices for the first item; once that's selected, there are 7 remaining choices for the next item, 6 for the third item, and 5 for the last. The total is 8*7*6*5 =1680. There are two problems with this. The first is that we're again double-counting some orders; this method will include both 1,2,3,4 and 4,3,2,1 as separate orders. We could solve that by dividing out these repetitions, but the second problem is worse: we're missing some orders. This method doesn't include repeating one item more than once. An order like 1,1,2,3 or 4,4,4,4 (for someone who loves apple turnovers) is never counted.
The correct way to look at this is as a "balls in buckets" problem (technically, combinations with repetition). The 8 menu items are the buckets, and we have 4 balls (choices in our order) to place in these buckets. If we place 2 balls in bucket 1, a ball in bucket 2, and a ball in bucket 3, that's an order of 1,1,2,3. All balls in bucket 4 is an order of 4,4,4,4. Now, here's the trick:
We can picture this as 7 dividers separating our 4 items into the 8 buckets. Visually, this means we translate our orders this way:
Order 1,2,3,4: o/o/o/o////
Order 4,4,4,4: ///oooo////
Order 2,4,5,8: /o//o/o///o
With the orders written this way, using the o and / characters, what we want to know is: how many different ways can we arrange 7 /s and 4 os? For this, we want an 11 choose 4 calculation. We have 11 total characters, and we need to choose 4 of them to be o's.
To start this calculation, we use 11*10*9*8, just like in the 8 choose 4 example above. As mentioned there, this has the problem of double-counting; it counts placing os in spots 1,2,3,4 as well as placing them in spots 4,3,2,1. This means that to get our final answer, we need to divide out these double-counts.
Luckily, that's pretty straightforward. The number of double-counts is just the number of ways to rearrange four numbers, and by the same logic we know this is 4*3*2*1. The final calculation is:
11*10*9*8 / 4*3*2*1
= 7920 / 24
= 330
Wikipedia link: Combinations
Before getting into the math, it's helpful to assign a number to each of the eight menu choices. Rather than talking about an order as sandwich, fries, drink, apple turnover, it's simpler to call this 1,2,3,4. In the items below, when something like item 1 is mentioned, that just means I'd rather type "1" than "roast beef sandwich".
There are some approaches that are reasonable, but that don't give the right answer. First, you might consider that you have 8 choices for each of your 4 items, and simply count up 8*8*8*8, which gives 4096. This gives the total number of four-digit numbers where all the digits are from 1 to 8. The problem is that this double-counts some orders: the orders 1,1,2,3, 1,2,3,1, 3,2,1,1 are all counted as separate orders, when really they are the same.
Another approach is the 8 choose 4 method. The logic of this is that we have 8 items and we will choose 4 of them. There are 8 choices for the first item; once that's selected, there are 7 remaining choices for the next item, 6 for the third item, and 5 for the last. The total is 8*7*6*5 =1680. There are two problems with this. The first is that we're again double-counting some orders; this method will include both 1,2,3,4 and 4,3,2,1 as separate orders. We could solve that by dividing out these repetitions, but the second problem is worse: we're missing some orders. This method doesn't include repeating one item more than once. An order like 1,1,2,3 or 4,4,4,4 (for someone who loves apple turnovers) is never counted.
The correct way to look at this is as a "balls in buckets" problem (technically, combinations with repetition). The 8 menu items are the buckets, and we have 4 balls (choices in our order) to place in these buckets. If we place 2 balls in bucket 1, a ball in bucket 2, and a ball in bucket 3, that's an order of 1,1,2,3. All balls in bucket 4 is an order of 4,4,4,4. Now, here's the trick:
We can picture this as 7 dividers separating our 4 items into the 8 buckets. Visually, this means we translate our orders this way:
Order 1,2,3,4: o/o/o/o////
Order 4,4,4,4: ///oooo////
Order 2,4,5,8: /o//o/o///o
With the orders written this way, using the o and / characters, what we want to know is: how many different ways can we arrange 7 /s and 4 os? For this, we want an 11 choose 4 calculation. We have 11 total characters, and we need to choose 4 of them to be o's.
To start this calculation, we use 11*10*9*8, just like in the 8 choose 4 example above. As mentioned there, this has the problem of double-counting; it counts placing os in spots 1,2,3,4 as well as placing them in spots 4,3,2,1. This means that to get our final answer, we need to divide out these double-counts.
Luckily, that's pretty straightforward. The number of double-counts is just the number of ways to rearrange four numbers, and by the same logic we know this is 4*3*2*1. The final calculation is:
11*10*9*8 / 4*3*2*1
= 7920 / 24
= 330
Wikipedia link: Combinations
Monday, March 9, 2009
Let Me Google That For You
I am easily amused. Luckily, in this age of the internet, there are innumerable stupid little diversions available for us. The following example is great, because it also helps address the fact that I am easily annoyed as well. One little annoyance that's common enough is people taking the time to email or post a simple question, when it would take them less time to Google the answer themselves. Now, there's a site to help with such situations.
For example, say someone posts to a message board, asking for something like a listing of all the past champions of the Masters golf tournament. You can just reply, with a link like so:
Here you go.
For example, say someone posts to a message board, asking for something like a listing of all the past champions of the Masters golf tournament. You can just reply, with a link like so:
Here you go.
Tuesday, March 3, 2009
Monday, March 2, 2009
Strangest Bug Ever
I recently came across an extremely odd bug in Visual Studio 2003, which I've since learned is known as the Haunted Keyboard bug. I was editing some code, and suddenly a few of my keys stopped responding. Pressing enter, tab, or the arrow keys did nothing, while the normal letter keys worked normally. Very strange. I actually physically checked the keyboard to see if something was jamming or sticking to the keys, before opening Notepad and verifying that they worked fine there.
The explanation is that this bug allows one of the docked Visual Studio windows, such as the Toolbox, to grab focus for command keystrokes, but not others. The interesting thing is that for different versions of VS there are different fixes - in one case you can simply select the Toolbox and then set focus back to the code editor, and in another you need to reset all settings. Also you may need to use a fixed-pitch font, for some reason. Interestingly I could not find any mention of this happening in VS2003, where I was getting it, but only in VS2005. There were also claims that this issue was resolved for the release version of VS2005, but also postings of users still experiencing it there.
In any case, I was glad to find that this was a known issue. It was one of the few times where I've wondered if I was literally hallucinating the behaviour I was seeing. I'm happy I wasn't, partly because I don't particularly want to hallucinate, and partly because Oh noes my enter key doesn't work! is a pretty lame hallucination, even for me :).
The explanation is that this bug allows one of the docked Visual Studio windows, such as the Toolbox, to grab focus for command keystrokes, but not others. The interesting thing is that for different versions of VS there are different fixes - in one case you can simply select the Toolbox and then set focus back to the code editor, and in another you need to reset all settings. Also you may need to use a fixed-pitch font, for some reason. Interestingly I could not find any mention of this happening in VS2003, where I was getting it, but only in VS2005. There were also claims that this issue was resolved for the release version of VS2005, but also postings of users still experiencing it there.
In any case, I was glad to find that this was a known issue. It was one of the few times where I've wondered if I was literally hallucinating the behaviour I was seeing. I'm happy I wasn't, partly because I don't particularly want to hallucinate, and partly because Oh noes my enter key doesn't work! is a pretty lame hallucination, even for me :).
Sunday, March 1, 2009
Zugzwang
There was an interesting position in a recent game of mine. I'm playing black.
1.e4 c5 2.Nf3 Nc6 3.Bb5 e6 4.O-O Nge7 5.c3 a6 6.Ba4 b5 7.Bc2 Bb7 8.Re1 Rc8 9.a4 Ng6 10.axb5 axb5 11.Na3 b4?!
11...Ra8 is probably better.
12.Nb5 Be7 13.e5 O-O 14.d4 Qb6 15.Bd3 c4!? 16.Bxc4 Nxd4 17.Qxd4 Qxd4 18.cxd4 Rxc4 19.Bg5 Bxf3 20.Bxe7 Nxe7 21.gxf3 Nf5?
21...Rc2
22.Rec1 Rxc1 23.Rxc1 g5 24.Rc4 Nh4
24...Rb8!
25.Rxb4 Nxf3+ 26.Kg2 Nh4+ 27.Kg3 Nf5+ 28.Kg4 f6 29.Rc4 fxe5 30.dxe5 Rb8 31.Rc5 h6 32.b3 Kg7 33.Kh5 Kh7
This is the position, although most of what I'll say about it applies to the position a few moves later, after 35...Kg6 as well.
When I reached this position, I thought it was simply fairly equal. I don't mean a dead draw, since there are still some things to play with: White has a passed pawn, but his pawns are a bit split up; Black has a backwards d-pawn, and a nice knight on f5. However, looking at the position a bit more closely, White has a problem. He has no moves.
Let's go through the possibilities. White's knight can't move without dropping the b-pawn. White's rook can't move without dropping the knight. White does have some pawn moves, but not many, and none that really change the situation. b4 doesn't do much, and actually introduces a tactic once the king goes back to g4; f3 does nothing; h3 does nothing (except block a square the king might need). The king can move back to g4, but that allows the black king into g6, when White still has the same problems, and the added problem of Black pushing the kingside pawns.
Black, on the other hand, has as many waiting moves as needed, just by moving the king between g7 and h7. As a simple variation, if White tries to delay, Black can just wait: 34.f3 Kg7 35.b4 Kh7 36.h3 Kg7 and White is stuck, and probably has to throw away the h-pawn with 37.h4 Nxh4 38.f4 Nf3.
In the game, White retreated the king before using up all the pawn moves, and I was able to press forward for a win.
34.f3 Kg7 35.Kg4 Kg6
This is where the tactic against b4 appears. 36.b4 Nd4! and Black wins the b-pawn after 37.Nxd4 Rxb4, pinning the knight.
36.Kh3 h5 37.Kg2 Ra8 38.Rc7 Ra2+ 39.Kg1 Nh4 40.Rc3 Kh5 41.Re3 Kf4 42.Re4+ Kxf3 43.Re1 Kf4 44.Nd4 Rb2 45.Re2 Rb1+ 46.Kf2 Rh1 47.b4 Rxh2+ 48.Ke1 Rxe2+ 49.Kxe2 Kxe5 50.b5 Nf5 51.Nf3+ Kd6 52.Nxg5 Kc5 53.Kf3 Kxb5 54.Ke4 Kc4 55.Ke5 Kc3 56.Kf6 Ke3 57.Ke5 h4 0-1
1.e4 c5 2.Nf3 Nc6 3.Bb5 e6 4.O-O Nge7 5.c3 a6 6.Ba4 b5 7.Bc2 Bb7 8.Re1 Rc8 9.a4 Ng6 10.axb5 axb5 11.Na3 b4?!
11...Ra8 is probably better.
12.Nb5 Be7 13.e5 O-O 14.d4 Qb6 15.Bd3 c4!? 16.Bxc4 Nxd4 17.Qxd4 Qxd4 18.cxd4 Rxc4 19.Bg5 Bxf3 20.Bxe7 Nxe7 21.gxf3 Nf5?
21...Rc2
22.Rec1 Rxc1 23.Rxc1 g5 24.Rc4 Nh4
24...Rb8!
25.Rxb4 Nxf3+ 26.Kg2 Nh4+ 27.Kg3 Nf5+ 28.Kg4 f6 29.Rc4 fxe5 30.dxe5 Rb8 31.Rc5 h6 32.b3 Kg7 33.Kh5 Kh7
This is the position, although most of what I'll say about it applies to the position a few moves later, after 35...Kg6 as well.
When I reached this position, I thought it was simply fairly equal. I don't mean a dead draw, since there are still some things to play with: White has a passed pawn, but his pawns are a bit split up; Black has a backwards d-pawn, and a nice knight on f5. However, looking at the position a bit more closely, White has a problem. He has no moves.
Let's go through the possibilities. White's knight can't move without dropping the b-pawn. White's rook can't move without dropping the knight. White does have some pawn moves, but not many, and none that really change the situation. b4 doesn't do much, and actually introduces a tactic once the king goes back to g4; f3 does nothing; h3 does nothing (except block a square the king might need). The king can move back to g4, but that allows the black king into g6, when White still has the same problems, and the added problem of Black pushing the kingside pawns.
Black, on the other hand, has as many waiting moves as needed, just by moving the king between g7 and h7. As a simple variation, if White tries to delay, Black can just wait: 34.f3 Kg7 35.b4 Kh7 36.h3 Kg7 and White is stuck, and probably has to throw away the h-pawn with 37.h4 Nxh4 38.f4 Nf3.
In the game, White retreated the king before using up all the pawn moves, and I was able to press forward for a win.
34.f3 Kg7 35.Kg4 Kg6
This is where the tactic against b4 appears. 36.b4 Nd4! and Black wins the b-pawn after 37.Nxd4 Rxb4, pinning the knight.
36.Kh3 h5 37.Kg2 Ra8 38.Rc7 Ra2+ 39.Kg1 Nh4 40.Rc3 Kh5 41.Re3 Kf4 42.Re4+ Kxf3 43.Re1 Kf4 44.Nd4 Rb2 45.Re2 Rb1+ 46.Kf2 Rh1 47.b4 Rxh2+ 48.Ke1 Rxe2+ 49.Kxe2 Kxe5 50.b5 Nf5 51.Nf3+ Kd6 52.Nxg5 Kc5 53.Kf3 Kxb5 54.Ke4 Kc4 55.Ke5 Kc3 56.Kf6 Ke3 57.Ke5 h4 0-1
Subscribe to:
Posts (Atom)
Posts
