(New page: I'm a little confused about part a. I tried it in two different ways that both seemed right to me and got very different answers. I figured to count all 6-letter strings containing ''a'', ...) |
(Rhea week 4 -- Brian Thomas) |
||
| (3 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | + | == Part A == | |
| + | I'm a little confused about part a. I tried it in two different ways that both seemed right to me and got very different answers. I figured to count all 6-letter strings containing ''a'', you could count all possible 6-letter strings and subtract the ones that do NOT contain ''a''. This should be <math>26^6-25^6=64,775,151</math>. | ||
Then, I thought to try it this way: suppose I first pick any 5 letters (in <math>26^5</math> ways). Then, to guarantee the string contains an ''a'', I can insert an ''a'' into this string at any of 6 places. So with this method, my answer is <math>(26^5)*6=71,288,256</math>. What am I doing wrong here? | Then, I thought to try it this way: suppose I first pick any 5 letters (in <math>26^5</math> ways). Then, to guarantee the string contains an ''a'', I can insert an ''a'' into this string at any of 6 places. So with this method, my answer is <math>(26^5)*6=71,288,256</math>. What am I doing wrong here? | ||
| + | |||
| + | UPDATE: I figured out that the second method is definitely wrong because it overcounts. For example, I could guarantee an ''a'' as the first character and have an ''a'' randomly as the second character. I could also guarantee the ''a'' in the second position and have one appear randomly in the first position. These two strings would be indistinguishable but counted multiple times. I think the first one is right (<math>26^6-25^6=64,775,151</math>). | ||
| + | |||
| + | |||
| + | ===Opinion ([[User:Thomas34|Brian Thomas]])=== | ||
| + | I agree with the first solution you have for part a. I did the problem in a much more complicated way, but I ended up with the same solution: | ||
| + | |||
| + | Our main problem is not so much that we cover all possible combinations of a's, but that we don't overcount. For example, how many times would some given algorithm count 'aaaaaa'? My solution was to mark where the ''first'' a appeared in the string. That way, if more than one a appeared in such a string, there would be no duplicate counting. (For the example above, 'aaaaaa' would only be counted when the position of the first a was position 1.) So, I used the following algorithm to construct my answer: | ||
| + | *1. Choose the position -- call it n (<math>1 \leq n \leq 6</math>) -- for the first a. (We are guaranteed there will be at least one 'a' from the problem statement.) | ||
| + | *2. For any position <math>k \leq n</math>, there are 25 ways to fill the space in, since we can't fill it in with a. There are n-1 positions we need to fill in like this. | ||
| + | *3. For any position <math>k \geq n</math>, there are 26 ways to fill the space in, since we can fill it in with any letter -- including a. There are 6-n positions we need to fill in like this. | ||
| + | |||
| + | (Sanity check: 1 + (n-1) + (6-n) = 6 total positions to fill in. Phew.) | ||
| + | |||
| + | So, using this algorithm, we iterate on point 1 for k = 1, 2, ..., 6, each time calculating the total number of possible strings we can create. The sum of all these will be the total number of possible strings. We can construct this (not so pretty) summation so that MATLAB (or other calculator of choice) can do the work for us: | ||
| + | |||
| + | <math>\sum_{n=1}^6 25^{n-1} 26^{6-n}</math> | ||
| + | |||
| + | MATLAB code: | ||
| + | <pre> | ||
| + | syms n; | ||
| + | symsum( 25^(n-1) * 26^(6-n), n, 1, 6) | ||
| + | </pre> | ||
| + | |||
| + | Using this method, we get 64,775,151 possible strings, which matches what is above. So, while this method (a way to count all the positive matches) works, I wouldn't recommend it. (Part b was a real pain to do in a similar way.) | ||
Latest revision as of 17:21, 16 September 2008
Part A
I'm a little confused about part a. I tried it in two different ways that both seemed right to me and got very different answers. I figured to count all 6-letter strings containing a, you could count all possible 6-letter strings and subtract the ones that do NOT contain a. This should be $ 26^6-25^6=64,775,151 $. Then, I thought to try it this way: suppose I first pick any 5 letters (in $ 26^5 $ ways). Then, to guarantee the string contains an a, I can insert an a into this string at any of 6 places. So with this method, my answer is $ (26^5)*6=71,288,256 $. What am I doing wrong here?
UPDATE: I figured out that the second method is definitely wrong because it overcounts. For example, I could guarantee an a as the first character and have an a randomly as the second character. I could also guarantee the a in the second position and have one appear randomly in the first position. These two strings would be indistinguishable but counted multiple times. I think the first one is right ($ 26^6-25^6=64,775,151 $).
Opinion (Brian Thomas)
I agree with the first solution you have for part a. I did the problem in a much more complicated way, but I ended up with the same solution:
Our main problem is not so much that we cover all possible combinations of a's, but that we don't overcount. For example, how many times would some given algorithm count 'aaaaaa'? My solution was to mark where the first a appeared in the string. That way, if more than one a appeared in such a string, there would be no duplicate counting. (For the example above, 'aaaaaa' would only be counted when the position of the first a was position 1.) So, I used the following algorithm to construct my answer:
- 1. Choose the position -- call it n ($ 1 \leq n \leq 6 $) -- for the first a. (We are guaranteed there will be at least one 'a' from the problem statement.)
- 2. For any position $ k \leq n $, there are 25 ways to fill the space in, since we can't fill it in with a. There are n-1 positions we need to fill in like this.
- 3. For any position $ k \geq n $, there are 26 ways to fill the space in, since we can fill it in with any letter -- including a. There are 6-n positions we need to fill in like this.
(Sanity check: 1 + (n-1) + (6-n) = 6 total positions to fill in. Phew.)
So, using this algorithm, we iterate on point 1 for k = 1, 2, ..., 6, each time calculating the total number of possible strings we can create. The sum of all these will be the total number of possible strings. We can construct this (not so pretty) summation so that MATLAB (or other calculator of choice) can do the work for us:
$ \sum_{n=1}^6 25^{n-1} 26^{6-n} $
MATLAB code:
syms n; symsum( 25^(n-1) * 26^(6-n), n, 1, 6)
Using this method, we get 64,775,151 possible strings, which matches what is above. So, while this method (a way to count all the positive matches) works, I wouldn't recommend it. (Part b was a real pain to do in a similar way.)
