A mathematical question
posted by ShubhamJain
- June 09 2012 11:53:04 PM
There is a string of n characters. It can be made of only a or b or c., with the following restrictions:
1. No restriction on a
2. b can occur at most once in the whole string
3. c can occur simultaneously only once, And the maximum length of it occurring simultaneously can be only 2. it can occur independently any number of times.
Example: aaaaaaaaaa, acacacacac, aaabccaaca are valid strings of size 10
aaaabbbbcc is invalid because b occurs twice
aaccc is invalid because c is occurring simultaneously with length > 2
aaccaabcc is invalid because c is occurrimg simultaneously twice .
Find the number of strings possible.
HINT: May be recursive answer be easier, but it depends on how well the person understands recursion
1. No restriction on a
2. b can occur at most once in the whole string
3. c can occur simultaneously only once, And the maximum length of it occurring simultaneously can be only 2. it can occur independently any number of times.
Example: aaaaaaaaaa, acacacacac, aaabccaaca are valid strings of size 10
aaaabbbbcc is invalid because b occurs twice
aaccc is invalid because c is occurring simultaneously with length > 2
aaccaabcc is invalid because c is occurrimg simultaneously twice .
Find the number of strings possible.
HINT: May be recursive answer be easier, but it depends on how well the person understands recursion
Reply by VinceAuric
- June 10 2012 04:11:00 AM
aaaaaaabcc
Reply by ShubhamJain
- June 10 2012 07:46:50 AM
if you are asking about aaaaaaabcc then it is a valid string..
Reply by Boiler
- June 16 2012 03:01:10 PM
To be quite honest, given your three criterion, there is an infinite amount of possible answers. Since there is no restriction on "A", and it's also a string of "n" characters, mathematically speaking, there's not an end to the combinations of A's for the solution....... there's not even any need to include B and C as a choice. Am i wrong?
Reply by ShubhamJain
- June 17 2012 03:36:21 AM
@Boiler
Had there been no restriction, then there were 3^n possible strings, because at each place either of a or b or c can come.
So the answer in this case is surely less than this.
Had there been no restriction, then there were 3^n possible strings, because at each place either of a or b or c can come.
So the answer in this case is surely less than this.
Reply by Boiler
- June 17 2012 08:17:51 PM
In the given example, however, aaaaaaaaaa is an accepted string of 10 letters. Following that logic, there would be a, aa, aaa, aaaa..... and on and on, until, well.... infinity. Am i just reading this wrong?
Reply by ShubhamJain
- June 18 2012 08:13:44 AM
Yes you are reading it wrong.
The length n is fixed. So a, aa, aaa are invalid. The string has to be of n letters.
The length n is fixed. So a, aa, aaa are invalid. The string has to be of n letters.
Reply by Caprico
- June 20 2012 11:12:15 PM
Wow... This is quite a high level combinatorics problem!
I understand your hint on recursion. If I am trying to find for a length n, and I know the answer for (n-1), (say) x, then I will have
1) n*x solutions inherently (because you can add an 'a' in the start, in between the letters, and at the end.)
However, one of the solutions in x will be only 'a's, so I subtract 1 from all, since adding a in the start or middle or end is equivalent. Hence I have n*(x-1) + 1.
2) If y is the number of strings in x, not having b, then I also have n*y,
3) If z is the number of strings in x containing p 'c's, no pairs of c, then since I have n places to add another c, minus (p), I have (n*z - p).
4) If a string contains t 'c's, one pair (inclusive), then I have (n-2t+1) places to add another c. Hence if there are w such strings in x, then again, I have w*(n-2t+1).
I presume I have covered all the possibilities, and so my total is: n*x + n*y + n*z + w*(n-2t+1). So from the base case of n=1 (a, b, c) and n=2 (aa, ab, ac, ba, bc, ca, cb, cc), we can deduce the rest.
However, this algorithm fails to cover any repeats;
For eg: for n=1, I have a, b, c.
Following the above algorithm, we end up getting 'ab' twice and such similar repeats occur.
It is unfortunately taking me time to figure out conditions for those. I'll need to try out some cases. Still, please confirm that my current answer is sufficient to continue?
I understand your hint on recursion. If I am trying to find for a length n, and I know the answer for (n-1), (say) x, then I will have
1) n*x solutions inherently (because you can add an 'a' in the start, in between the letters, and at the end.)
However, one of the solutions in x will be only 'a's, so I subtract 1 from all, since adding a in the start or middle or end is equivalent. Hence I have n*(x-1) + 1.
2) If y is the number of strings in x, not having b, then I also have n*y,
3) If z is the number of strings in x containing p 'c's, no pairs of c, then since I have n places to add another c, minus (p), I have (n*z - p).
4) If a string contains t 'c's, one pair (inclusive), then I have (n-2t+1) places to add another c. Hence if there are w such strings in x, then again, I have w*(n-2t+1).
I presume I have covered all the possibilities, and so my total is: n*x + n*y + n*z + w*(n-2t+1). So from the base case of n=1 (a, b, c) and n=2 (aa, ab, ac, ba, bc, ca, cb, cc), we can deduce the rest.
However, this algorithm fails to cover any repeats;
For eg: for n=1, I have a, b, c.
Following the above algorithm, we end up getting 'ab' twice and such similar repeats occur.
It is unfortunately taking me time to figure out conditions for those. I'll need to try out some cases. Still, please confirm that my current answer is sufficient to continue?
Reply by ShubhamJain
- June 22 2012 09:22:17 AM
Yes you are going in right direction.. Go ahead...
To post a response, simply log in with your Google Account.
