The rules of the game are as follows:
(1) You can flip (turn it over) one coin at a time.
(2) You can't see the coins, but you can query after each flip, if you've reached the all heads or all tails state.
(3)
Apparently the answer is $2^{n-1} - 1 = 2^{7} - 1 = 127$ (this formula generalizes to any $n$, number of tosses).
I have no idea where this formula came from. Could someone explain?
I found a paper on it http://people.csail.mit.edu/nbenbern/CoinFlipping.pdf, but I haven't wrapped my head around it on how it works.
Given $n$ number of coins on the table, there are $2^n$ possible sequences of heads or tails. You can ignore the first coin, and then go through every possible permutation of the other $n-1$. As you are checking every single permutation, one of them is guaranteed to be all heads or all tails. This gives you a minimum of $2^{n-1}$ flips. However, because there is an original permutation of coins that is not all heads or all tails, there is one position you will not have to check, giving the final expression of $2^{n-1}-1$.