Dear
MakeUrTimeCount,
That's a fantastic question. First, let's be clear. The problem with six tosses is already hard, near the outer limit of what the GMAT is going to ask. There's not a snowball's chance in the Sahara that the GMAT would ever ask you about the 15 toss case. That's way above and beyond what any ordinary non-Isaac-Newton could be expected to do with pencil and paper.
Also, I'll say: if I had to calculate the 15 toss case myself, my preference would be to write a program and let a computer do the heavy lifting.
Having said that, what can we say about the solution? Well, we still have to break things down by cases, each # of heads a different case.
So, the question:
How many ways are there to toss 15 coins and get no two head on consecutive tosses?
Case #1: 0 H and 15 T
Easy ---> 1 case
Case #2: 1 H and 14 T
Easy ---> put the H in every slot ---> 15 case
Case #3: 2 H and 13 T
OK, so 15C2 = 105 --- that's all the ways to distribute two head; then subtract the 14 possibilities when they are adjacent (at positions 1 & 2, or 2 & 3, or 3 & 4, etc., up to 14 & 15). That leaves 91 cases. OK, so far.
Case #4: 3 H and 12 T
Now things start to get dicey.
One method would be to start with 15C3 = 455, then subtract doubles and triples --->
not easy
Another method would be: consider what you have as
(A T's) - H - (B T's) - H - (C T's) - H - (D T's)
where integers A, B, C, D have the properties that A & D are >= 0, B & C are >= 1, and A + B + C + D = 12. I'm not sure, but I suspect patterns may emerge here . . .
A = 0, B = 1 ---> C can be anything from 1-13, so 13 cases
A = 0, B = 2 ---> C has 12 possibilities, so 12 cases, etc. etc.
....
A = 0, B = 11, C = 1 ---- 1 case
A = 1, B = 1 ---> C has 12 possibilities, so 12 cases, etc.
...
That approach seems promising, but again, my own predilection would be to let a computer carry it out to completion.
Part of what is coming into play with this way of thinking is a hard branch of math dealing with a beast known as the Partition Function -- (
https://mathworld.wolfram.com/Partition.html) --- unless you have an advanced degree in pure math, that stuff will probably make your head spin. It took folks like the super-genius Ramanujan to tame the partition function.
I will decline to pursue this analysis any further --- I will point out that in the next few cases, I probably would try something very much like this second approach in Case #4. Also, I will point out that toward the end it simplifies again
Case 8: 7 H and 8 T
36 cases (I'll let you think about why --- see explanation in post below)
Case 9: 8 H and 7 T
1 case only.
So, not a complete solution, but I hope that gives you a taste of what would be involved. Again, really only a masochist or a super-genius would commit to a purely paper & pencil approach to this problem. Most of us mere mortals would resort to computers.
Great question. Let me know if you find anything I've said unclear, or if you have any follow up questions.
Mike
)
