Maximum value of the smallest number of operations to obtain configuration from original configuration

Question

Let $n$ be a positive integer. There are $n(n+1)/2$ marks, each with a black side and a white side, arranged into an equilateral triangle, with the biggest row containing $n$ marks. Initially, each mark has the black side up. An operation is to choose a line parallel to the sides of the triangle, and flipping all the marks on that line. A configuration is called admissible if it can be obtained from the initial configuration by performing a finite number of operations. For each admissible configuration $C$, let $f(C)$ denote the smallest number of operations required to obtain $C$ from the initial configuration.

What is the maximum value of $f(C)$, where $C$ varies over all admissible configurations?

Answer 1

While i haven't found a definite answer yet, let me at least provide some quick n' dirty bounds where the solution must lie.

Let me rename the number of moves for the most complicated configuration possible $f(C_n)$. It's easy enough to prove that:

$$n \le f(C_n) \le 3n$$

Because:

1. $n \le f(C_n)$ since you need $n$ operations to perform a "flip every tile" configuration.
2. $f(C_n) \le 3n$ because a set of operations can be done in any order, producing the same configuration. From that it can be deduced that doing the same operation twice or more is wasting movements. And therefore, we can set the number of different operations $3n$ as a safe, yet huge, bound.

Answer 2

We can think of the operations as vectors spanning a subspace of $\mathbb{Z}_2^{n(n+1)/2}$. We're searching the girth of the Cayley graph of the additive group (with these operation vectors as generators) of this vector space. This is usually difficult, but might be easier given the special structure of the group.

As an upper bound, no admissible configuration will need more than $\frac{3n}{2}$ operations:

Let's call the three sides of the triangle $P$, $Q$ and $R$. Let's call $P$-operations those operations that affect a line parallel to $P$, and likewise define $Q$- and $R$-operations. When we add all $P$- and all $Q$-operations, we get the zero vector.

Now assume there is an admissible configuration that needs more than $\frac{3n}{2}$ operations. That means there is a vector that can be written as the sum of $m>3n/2$ operation vectors, but not with less than $m$ such vectors.

For one such fixed way of writing the vector, seperately count the number of occurances of $P$-, $Q$- and $R$-operations, and call those numbers $p$, $q$ and $r$. Then we have $$ p+q+r = m > 3n/2, $$ and without loss of generality we may assume $$p\geq q\geq r.$$ It follows that $$p+q>n. \tag{*}\label{*}$$

Now add zero in the form of all $P$- and $Q$-operations to the vector sum and let them interact with the $P$- and $Q$-operations that were already there. Those that were already there will now appear twice in the sum and cancel each other, leaving only the $n-p$ $P$-operations and the $n-q$ $Q$-operations that weren't there before. (The $R$-operations remain unchanged.) We have found a new way of writing the vector, which uses $$2n-(p+q)+r$$ operations. Because of \eqref{*}, this is less than $m$, a contradiction to the assumed minimality of $m$. $\blacksquare$

Unless I made a mistake, the series of maximally needed numbers of operations for different $n$ starts like this:

1, 2, 3, 6, 7, 8, 9, 12,...

Observe that 1, 6, 7 and 12 are the smallest (integer) values allowed by our upper bound. Observe also that if we allow $n=0$, then we can prepend a 0 to the series, and we can see what might be a regular pattern.

---

Additional results

I can now show that for $n=4k+2$ and $4k+3$ we always need one operation less than already guaranteed by the above upper bound.

Call an operation even if it affects an even number of marks, odd otherwise. It is not difficult to show that every mark is affected by either zero or two even operations, so all even operations together have no net effect. The same is true for the combination of for example all odd $P$-operations, all odd $Q$-operations and all even $R$-operations, and two other such combinations. Crucially, if we choose either the even or the odd $P$-operations, and either the even or the odd $Q$-operations, then there is a way to choose either the even or the odd $R$-operations so that the net effect is nothing.

Now assume that for $n=4k+2$, we need $p+q+r=6k+3$ operations for some admissable configuration. The argument above that $p+q>n$ leads to a contradiction needs no assumption about $p+q+r$ (that was just used to get $p+q>n$). So we have $p=q=r=2k+1$.

Next count how many of the used $P$-operations are even and how many are odd, call those numbers $p_e$ and $p_o$, and do the same for the types of operations. Then we have $$p_e+p_o=q_e+q_o=r_e+r_o=2k+1.$$

Since $p_e+p_o$ is odd, $p_e$ and $p_o$ can't be equal. Call the bigger one $p_+$, the other $p_-$, and likewise for the rest. Without loss of generality we may assume $p_+\geq q_+\geq r_+$.

We will now choose one of the new neutral sets of operations. If $p_+$=$p_e$, we choose the even $P$-operations, otherwise the odd ones. In the same way, if $q_+=q_e$, we choose the even $Q$-operations, otherwise the odd ones. Finally, we choose the even or odd $R$-operations, so that the net effect is none. As above, we let these operations interact with the old ones, cancelling those that were already there. Since the number of even as well as the number of odd $P$-operations is $2k+1$, this will replace $p_+$ $P$-operations with $2k+1-p_+=p_-$ $P$-operations, so that in total there will be $2p_-$ $P$-operations. The $Q$-operations are reduced in the same way. The number of $R$-operations may also be reduced, but may as well be increased to $2r_+$. However, because of $q_+\geq r_+$, the possible increase of $R$-operations will at most be as big as the decrease of $Q$-operations, so we have at least the decrease of $P$-operations as net result, contradicting the minimality assumption. $\blacksquare$

We can do essentially the same for $n=4k+3$, here's a sketch: the old upper bound is $6k+4$, so we have $p=2k+2$ and $q=r=2k+1$. There are $2k+1$ even operations of each kind, and $2k+2$ odd ones. We may have $p_e=p_o$, if that is the case, choose the even $P$-operations, that will decrease the number of $P$-operations by one. Again assume $q_+\geq r_+$, and if $q_+=r_+$ and only one of them corresponds to even operations, choose these operations. Then again the total number of $Q$- and $R$-operations will not increase. $\blacksquare$

Finally, an argument that for $n=4k$, we always need $6k$ operations. Call an operation short if it affects at most $n/2$ marks. The set of all short operations has size $6k$ with $p_e=p_o=q_e=q_o=r_e=r_o=k$, so it can not be reduced with any of the methods above. Any way to combine operations so that they have the same effect as all short operations would also give a new way of combining operations such that their total effect is none. That means that considered as vectors they belong to the kernel of the obvious linear map from the $3n$-dimensional $\mathbb{Z}_2$ vector space of formal linear combinations of operations to $\mathbb{Z}_2^{n(n+1)/2}$. For $n\geq 2$, the dimension of the image seems to be $3n-3$. That doesn't look like it's hard to prove, but I have only calculated it for $n$ up to 250. In any way, if it's true, then the kernel has dimension 3, and we have already seen seven nonzero kernel elements, so there couldn't be other ways to rewrite combinations of operations.

Missing ends

Let's prove the dimension formula conjectured above: Call the vector space of formal linear combinations of operations $O_n$ and the image of the map considered above $C_n$. Let $n\geq 2$ and look at the maps $$O_{n+1}\to C_{n+1}\to C_n,$$ where the last map comes from ignoring the last line of marks. The vectors corresponding to the operations that affect all marks, the left mark, or the right mark of the last line all belong to the kernel of the second map and are linearly independent. So that map has nullity at least 3. So does the first map, as explained above. The maps are surjective and $O_{n+1}$ has dimension $3n+3$. So if $C_n$ has dimension $3n-3$, then both nullities are exactly 3 and the dimension of $C_{n+1}$ is $3n$. It is easy to see that $C_2$ has indeed dimension 3, so the result follows by induction. $\blacksquare$

So for $n=4k$, the combination of all short operations indeed leads to an admissable configuration that can't be reached by fewer than $6k$ operations. For $n=4k+2$, again all short operations lead to a configuration that needs the maximal number of operations. However, as we have seen, that number is $6k+2$. For odd $n$, use all short operations and one operation that affects the middle mark. For $n=4k+1$, this set of operations can't be reduced, for $n=4k+3$ it can only be reduced by 1.

So as suspected, the series is given by $$a_n=\begin{cases} 6k & \text{if $n=4k$,} \\ 6k+1 & \text{if $n=4k+1$,}\\ 6k+2 & \text{if $n=4k+2$,}\\ 6k+3 & \text{if $n=4k+3$.}\\ \end{cases}$$