Problem: Let $m,n\in\mathbb{N}$. There are $n$ coins labelled $1$, $2$, $\ldots$, $n$. A move consists of a selection of
$i\in\{1,2,\ldots,n\}$ and flipping of coins $i,i+1,i+2,\ldots,i+m-1$
(where the coin labels are considered modulo $n$). Initially, all
coins are tails up. When is it possible to flip these
coins according to the rule so that they are heads up?
When this task is possible, what is the minimum number of moves
required?
Consider $V:=\mathbb{F}_2^n$. Denote by $[n]$ the set $\{1,2,\ldots,n\}$. For $i\in[n]$, let $\mathbf{e}_i$ be the vector in $V$ with $1$ at the entry $i$, and $0$ everywhere else. A vector $\mathbf{v}=\sum_{i=1}^n\,a_i\mathbf{e}_i$ in $V$, where $a_1,a_2,\ldots,a_n\in\mathbb{F}_2$, is associated to the state where, for $i\in[n]$, the coin $i$ is heads up if and only if $a_i=1$.
For $i\in[n]$, let $\mathbf{u}_i:=\sum_{j=1}^m\,\mathbf{e}_{i+j-1}$, where indices are consider modulo $m$. Write $\mathbf{1}$ for the all-$1$ vector $\sum_{i=1}^n\,\mathbf{e}_i$. Now, the required task is possible if and only if there are $a_1,a_2,\ldots,a_n\in\mathbb{F}_2$ such that $\sum_{i=1}^n\,a_i\mathbf{u}_i=\mathbf{1}$. The smallest number of moves required is then the smallest possible value of $k:=\Big|\big\{i\in[n]\,\big|\,a_i\neq 0\big\}\Big|$. Observe that
$$\sum_{i=1}^n\,\mathbf{e}_i=\mathbf{1}=\sum_{i=1}^n\,a_i\mathbf{u}_i=\sum_{i=1}^n\,a_i\,\left(\sum_{j=1}^m\,\mathbf{e}_{i+j-1}\right)=\sum_{i=1}^n\,\left(\sum_{j=1}^m\,a_{i-j+1}\right)\,\mathbf{e}_i\,.$$
That is, for each $i\in[n]$, $\sum_{j=1}^m\,a_{i-j+1}=1$. Hence, for all $i\in[n]$, $\sum_{j=1}^m\,a_{i-j+1}=\sum_{j=1}^m\,a_{(i-1)-j+1}$, or equivalently,
$$a_i=a_{i-m}\,.$$
If $d:=\gcd(m,n)$, then we conclude that $a_i=a_{i+d}$ for every $i\in[n]$. Let $t\in\mathbb{N}$ be such that $m=td$. Thus, $1=\sum_{j=1}^m\,a_{i-j+1}=t\,\sum_{j=1}^d\,a_j$ for any $i\in[n]$. Therefore, the task is possible if and only if $t$ is odd, which is equivalent to saying that $\frac{m}{d}=\frac{m}{\gcd(m,n)}$ is odd.
Now, the minimum value of $k$ is attained when exactly one among $a_1,a_2,\ldots,a_d$ is $1$ (and the remaining numbers are $0$). That is, the smallest possible value of $k$ is $\frac{n}{d}=\frac{n}{\gcd(m,n)}$.
Note: If a move is define to be choosing $i\in\{1,2,\ldots,n\}$ and flipping all coins with labels in $\left\{i-r,i-r+1,\ldots,i-r+m-1\right\}$ (here, labels are not considered modulo $n$) where $r\in\mathbb{Z}$ such that $0\leq r <m$ is fixed, then the task is always possible with the minimum number of moves being $\left\lceil\frac{n}{m}\right\rceil$.
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.
Best Answer
Let $1.i$ and $2.j$ denote that we toggled row i and column j respectively. There are no decimals in this writeup.
For simplicity (you'd see why in a moment), we add $2.1, 2.2, 2.3, \ldots, 2.99, 2.100, 1.1, 1.2, 1.3$ to the start of any sequence (meaning we toggle every single column first and then every row). Since the board ends up as all heads up after these operations, we've not changed the final outcome. However, it ensures that we've used each column and row operation at least once, which is very helpful to keep track of the counting.
Claim: Suppose that some series of operations was done. Then, the final display depends only on:
You can prove this claim rigorously by showing that for each cell $(i,j)$, the state only depends on whether operation 1.i or 2.j was the last to be done.
We apply PIE based on the event where the rows are consecutive.
The total number of ways is $6$ (corresponding to which order we take $1.1, 1.2, 1.3$) $\times 4^{100}$ (each column can appear in 4 positions).
However, we've double-counted the cases when 2 rows appear consecutively, which correspond to $ 6 \times 3^{100}$ (each column can appear in 3 positions) that we need to subtract.
However, we now need to add back the case when all 3 rows appear consecutively, which correspond to $2^{100}$ cases (each column can appear in 2 positions).