On a remote island, its inhabitants might lie at any given moment. However, they are restricted by the island code NOT to tell 3 lies in a row.
A group of visitors to the island meets an inhabitant of the island.
Responding to various queries of the visitors he made precisely 17 consecutive statements.
How many combinations of truths/lies can there be?
A true statement can follow any valid sequence of statements, so there is a one-to-one relationship between 'sequences of n statements' and 'sequences of n+1 statements ending with a true statement'.
So then we will find a formula to calculate the number of sequences of statements ending with a true statement.
Let T represent a true statement and L represent a lie
There is 1 sequence of length 1 ending with a true statement: T
There are 2 sequences of length 2 ending with a true statement: TT, LT
There are 4 sequences of length 3 ending with a true statement: TTT, TLT, LTT, LLT.
Longer sequences can be built recursively by adding one true statement, possibly with lies in between, to an existing sequence.
To make a length N sequence we can append T to a length N-1 sequence, or append LT to a length N-2 sequence, or append LLT to a length N-3 sequence.
Then all this information gives us a recursion: S(N) = S(N-1) + S(N-2) + S(N-3) with S(0)=1, S(1)=2, and S(2)=4.
Indexing this starting at 0 will make S(17) line up with the problem's desired goal of finding the number of possible truth/lie sequences of 17 consecutive statements made by the inhabitant.
Then S(17) = 35890.
A quick search on OEIS finds this is the Tribonacci Sequence. http://oeis.org/A000073
Solution
