This is actually interesting.
Let's say there are $n$ coins, and we want to find the maximum flips.
It turns out that,
for $n$ even, the maximum is attained at TT...THH..H
, with $n/2$ T
and $n/2$ H
;
for $n$ odd, the maximum is attained at T...THH...H
, with $(n - 1)/2$ T
and $(n + 1)/2$ H
.
In both cases, the maximun number of flips is $n(n+1)/2$, and the configuration attaining the max is unique.
I'll leave the proof to others, because it's time for bed...
Seems nobody else wants to give a proof ...
OK here we go.
Let $M(n)$ be the maximum number of flips among all configurations of $n$ coins. For such a configuration, there are two possibilities:
The $n$-th coin is T
. Then the $n$-th coin will always remain T
, until the end of the game. Hence it is essentially a game with $n - 1$ coins and the maximum number of flips is no more than $M(n - 1)$.
The $n$-th coin is H
. Then the $n$-th coin will still remain H
, until the configuration HH...H
is reached. After that, it's easy to see that $n$ more flips leads to the final configuration TT...T
.
Therefore it suffices to consider the number of flips until the configuration HH...H
.
Now we reindex the coins: previously they were indexed $1, 2, \dotsc, n$, and now we index them as $n - 1, \dotsc, 1, 0$. Under this new index system, the rule of flipping becomes: if there are $k$ tails among the first $n - 1$ coins, then we flip the coin with new index $k$. The procedure continues until all the first $n - 1$ coins are H
, i.e. we reach the configuration HH...H
.
This is then exactly the same game with $n - 1$ coins, and with heads and tails exchanged. Thus the maximum number of flips until the configuration HH...H
is $M(n - 1)$, and hence the total maximum number of flips (until the configuration TT...T
) is $M(n - 1) + n$.
Combining 1. and 2., we get $M(n) = M(n - 1) + n$, and the maximum is attained only when the last coin is H
, and the first $n - 1$ coins attain the maximum for the game with $n - 1$ coins, with H
and T
switched and order inversed.
By induction on $n$, this proves exactly our claims.
$\def\eqd{\stackrel{\text{def}}{=}} $
This is a problem in linear algebra over the field $\ \Bbb{F}_2\ $ of numbers $\ 0,1\ $ under addition and multiplication mod $2$. Any $\ n\times n\ $ configuration of coins can be represented by an $\ n\times n\ $ matrix whose entry in its $\ i^\text{th}\ $ row and $\ j^\text{th}\ $ column is $\ 0\ $ if the coin in the corresponding row and column of the coin configuration shows heads or $\ 1\ $ if that coin shows tails.
If you modify a configuration represented by the matrix $\ A\ $ by flipping all the coins in the $\ i^\text{th}\ $ row and $\ j^\text{th}\ $ column, then the matrix $\ B\ $ representing the new configuration will be given by
$$
B=A+M(i,j)\
$$
where $\ M(i,j)\ $ is the $\ n\times n\ $ matrix with $\ 1$s along its $\ i^\text{th}\ $ row and down its $\ j^\text{th}\ $ column. Thus, if your target configuration is represented by the matrix $\ T\ $, then your problem is equivalent finding the smallest number $\ m\ $ of matrices $\ M\big(i_1,j_1\big), M\big(i_2,j_2\big),\dots,M\big(i_m,j_m\big)\ $ such that
$$
T=\sum_{k=1}^mM\big(i_k,j_k\big)\ .\label{eq1}\tag{1}
$$
When $\ n\ $ is even, the set $\ \big\{\,M(i,j)\,|\,1\le i,j\le n\,\big\}\ $ of matrices is linearly independent, and spans the space of $\ n\times n\ $ matrices over $\ \Bbb{F}_2\ $, so for any such matrix, there's a unique set $\ \big\{M\big(i_1,j_1\big), M\big(i_2,j_2\big),\dots,M\big(i_m,j_m\big)\big\}\ $ of distinct matrices $\ M\big(i_k,j_k\big)\ $ such that equation \eqref{eq1} holds, and $\ m\ $ will then be the minimum number of moves needed to obtain the configuration with matrix $\ T\ $.
When $\ n\ge3\ $ is odd, the set $\ \big\{\,M(i,j)\,|\,1\le i,j\le n\,\big\}\ $ of matrices is linearly dependent, so there will be configurations which will be impossible to reach, and for those configurations that are reachable, there will always be more than one set of distinct matrices $\ M\big(i_k,j_k\big)\ $ for which equation \eqref{eq1} holds and there may well be more than one of minimum size. If $\ e_i\ $ is the $\ i^\text{th}\ $ column of the $\ n\times n\ $ identity matrix, and $\ \mathbf{1}\eqd\sum_\limits{i=1}^ne_i\ $ the $\ 1\times n\ $ column vector all of whose entries are $\ 1\ $, then
$$
M(i,j)=e_i\mathbf{1}^T+\mathbf{1}e_j^T+e_ie_j^T\ ,
$$
and
\begin{align}
\sum_{i=1\\i\ne s}^nM(i,t)&+\sum_{j=1\\j\ne t}^nM(s,j)\\
&=\sum_{i=1\\i\ne s}^n\big(e_i\mathbf{1}^T+\mathbf{1}e_t^T+e_ie_t^T\big)+\sum_{j=1\\j\ne t}^n\big(e_s\mathbf{1}^T+\mathbf{1}e_j^T+e_se_j^T\big)\\
&=\big(e_s+\mathbf{1}\big)\big(\mathbf{1}+e_t\big)^T+(n-1)\mathbf{1}e_t^T\\
&\hspace{1em}+(n-1)e_s\mathbf{1}^T+\big(e_s+\mathbf{1}\big)\big(\mathbf{1}+e_t\big)^T\\
&=(n-1)\big(e_s\mathbf{1}^T+\mathbf{1}e_t^T\big)\\
&=\cases{0&if $\ n\ $ is odd\\
e_s\mathbf{1}^T+\mathbf{1}e_t^T=\\
M(s,t)+e_se_t^T&if $\ n\ $ is even.}
\end{align}
Thus, when $\ n\ge3\ $ is odd, the set of matrices $\ M(i,j)\ $ is linearly dependent. When $\ n\ $ is even,
$$
e_se_t^T=M(s,t)+\sum_{i=1\\i\ne s}^nM(i,t)+\sum_{j=1\\j\ne t}^nM(s,j)\ ,
$$
and since the matrices $\ e_se_t^T\ $ span the space of $\ n\times n\ $ matrices over $\ \Bbb{F}_2\ $, then so do the matrices $\ M(i,j)\ $. Since there are only $\ n^2\ $ matrices in the set $\ \big\{\,M(i,j)\,|\,1\le i,j\le n\,\big\}\ $, and they span a space of dimension $\ n^2\ $ they must be linearly independent.
Here's an example of non-unique minimal solutions for $\ n=3\ $.
\begin{align}
\pmatrix{0&0&0\\0&1&1\\0&1&1}&=
\pmatrix{1&0&0\\1&1&1\\1&0&0}+\pmatrix{1&0&0\\1&0&0\\1&1&1}\\
&=\pmatrix{1&1&1\\0&1&0\\0&1&0}+\pmatrix{1&1&1\\0&0&1\\0&0&1}\ .
\end{align}
Solution for even $\ n\ $
It turns out there's a simple method of solution when $\ n \ $ is even. Let $\ T\ $ be the matrix representing the target configuration, with entry $\ t_{ij}\ $ in it's $\ i^\text{th}\ $ row and $\ j^\text{th}\ $ column, and $\ (i_1,j_1),$$\, (i_2,j_2),$$\,\dots,$$\,(i_t,j_t)\ $ the pairs of rows and columns for which $\ t_{i_kj_k}=1\ $. Let
\begin{align}
C&=\sum_{i=1}^n\sum_{i=1}^nt_{ij}M(i,j)\\
&=\sum_{k=1}^tM\big(i_k,j_k\big)\ .
\end{align}
If $\ \mu\ $ is the number of ones in the matrix $\ C\ ,$ $\ c_{ij}\ $ the entry in its $\ i^\text{th}\ $ row and $\ j^\text{th}\ $ column, and $\ (c_1,d_1),$$\,(c_1,d_1),$$\,\dots,$$\,(c_\mu,d_\mu)\ $ the pairs of rows and columns for which $\ C_{c_kd_k}=1\ ,$ then $\ \mu\ $ is the minimum number of moves needed to reach the target, and $\ (c_1,d_1),$$\,(c_1,d_1),$$\,\dots,$$\,(c_\mu,d_\mu)\ $ are the row-column pairs that need to be flipped. In other words,
\begin{align}
T&=\sum_{i=1}^n\sum_{i=1}^nc_{ij}M(i,j)\\
&=\sum_{k=1}^\mu M\big(c_k,d_k\big)\ .
\end{align}
Example
If
$$
T=\pmatrix{0&0&0&0\\
1&1&0&0\\
0&1&1&0\\
0&1&1&0}\,
$$
then
\begin{align}
C&=M(2,1)+M(2,2)+M(3,2)\\
&\hspace{2em}+M(3,3)+M(4,2)+M(4,3)\\
&=\pmatrix{1&0&0&0\\1&1&1&1\\1&0&0&0\\1&0&0&0}+\pmatrix{0&1&0&0\\1&1&1&1\\0&1&0&0\\0&1&0&0}\\
&\hspace{1em}+\pmatrix{0&1&0&0\\0&1&0&0\\1&1&1&1\\0&1&0&0}+\pmatrix{0&0&1&0\\0&0&1&0\\1&1&1&1\\0&0&1&0}\\
&\hspace{1em}+\pmatrix{0&1&0&0\\0&1&0&0\\0&1&0&0\\1&1&1&1}+\pmatrix{0&0&1&0\\0&0&1&0\\0&0&1&0\\1&1&1&1}\\
&=\pmatrix{1&1&0&0\\0&0&0&0\\1&0&1&0\\1&0&1&0}\ .
\end{align}
Thus, the smallest number of moves needed to obtain the configuration represented by the matrix $\ T\ $ is $6$, and the unique set of moves required to reach the configuration in $6$ moves is to flip the coins in row $1$ column $1$, row $1$ column $2$, row $3$ column $1,$ row $3$ column $3,$ row $4$ column $1$ and row $4$ column $3$.
Best Answer
You cannot on any board except $n=1$.
First note that the order you do flips does not matter because the effects commute. Doing a flip twice is equivalent to not doing it at all, so all you care about is which rows and columns you have flipped once.
A simple proof is that you cannot succeed for even $n$. You start with an even number of heads and each move flips an even number of coins, so the number of heads must stay even.
On a board with odd $n$ all the coins are equivalent, so we might as well try to have the top left coin be the one that finishes tails. Then if we just look at the $2 \times 2$ piece of the board in the upper left, we have to solve that and the only moves that matter are the top two rows and the left two columns. If we can solve the subboard, we can solve $2 \times 2$, which we cannot.