Menu:

We will use the following notation: h = heads, t = tails, x = unknown, R=revealed, C=conceiled. Repeating patterns will be denoted in the form . This is a pattern of k values repeated r times. E.g., .

Pattern:

Suppose the last turn will be solved in a symmetric pattern by finding all h or t where k≥1 and r≥2. If we are in the case, then the problem is solvable with c=n/2 if can be prepared with at most c=n/2.

Otherwise, we want to reveal all t's or all h's. To reveal the first t, it takes at most k+1 reveals, i.e., k+r reveals for all t. Similarly, it takes at more kr+1 reveals to reveal all h's. Since k≥1, r(k-1)≥(k-1) implies rk+1≥k+r. It is therefore always better to reveal all t's and since n=r(k+1) we obtain the lower bound . In particular, a symmetric solution of the form requires c≥k+r=3+2=5.

To find another bound for c, we will rearrange as . In other words, implies .

Finally, shows that .

Pattern:

Now let the pattern be with l≤k. Suppose you first find an h. Then it takes at most rk+1 reveals to find all h's and rl+k reveals to find all t's. Similarly, first observing t, at most rl+1 reveals are required to find all t's and rk+l to find all h. Since l≤k it is always better to reveal all t's if you first observe a t. First observing an h, it is better to reveal all h's if and only if rk+1<rl+k which is equivalent to r(k-1)<rl-1 and hence k-l<1-1/r. This can only be true for k=l in which case 2rk=r(k+l)=n implies c≥rk+1=1+n/2. In particular, the only remaining symmetric solution to n=8 is for which we observe c≥5.

For l<k, we thus always want to reveal all t's which takes at most rl+k reveals. Since n=rl+rk, we obtain c≥(r-1)l+n/r≥r-1+n/r.