There happens to be a politician that might lie at any moment (this isn't unusual) but his conscience bothers him enough (now, that is unusual!) so he won't say two lies in a row.

He said ten consecutive statements.

How many combinations of truths/lies can there be?

He can tell anywhere from zero to 5 lies; any more would require at least one pair of successive lies. So:

There's exactly 1 way of telling zero lies.

The ways of telling one lie are C(10,1) = 10

The ways of telling two lies are more complicated.  The two lies can't be successive (when laid out as a plan, they can't be adjacent).  The two lies divide the remaining eight true statements into three groups, the first and last of which might be empty, but the middle needs at least one to separate the lies.  There is a formula for the number of ways three non-negative integers (including the possibility of zero) can add up to a given number, n, based on choosing which two of n+2 objects shall be partitions rather than counted objects: C(n+2,2).  Before we use this, we must separate out the fact that the middle of the three numbers to be added must be at least one. So, of the 8 truths, there must be 1 in the middle group, and then the remaining 7 must be in the three groups, so the number of ways is C(7+2,2)=36.

Similarly for three lies, there are four groups of truths, the middle two of which have at least one.  The lies and required truths account for 5, leaving 5 more truths to be distributed among the four groups of truths: C(5+3,3)=56.

For four lies, there are five groups of truths, the middle three of which have at least one, leaving only three optional truths to be distributed among the five groups: C(3+4,4)=35.

For five lies, there are six groups of truths, the middle four of which have at least one, leaving only one optional truth to be distributed among the six groups: C(1+5,5)=6.

These ways total 144.

Posted by Charlie on 2004-02-27 08:52:09