Problem 1750

Solution (By Warut Suksompong). The answer is $6\lfloor\frac{n}{4}\rfloor + n - 4\lfloor\frac{n}{4}\rfloor = n + 2\lfloor\frac{n}{4}\rfloor$.
For $n=1$ the answer is clearly 1, since there is only one configuration other than the initial one, and that configuration takes 1 step to get to. From now on we will consider $n \ge 2$.
Note that there are $3n$ possible operations in total, since we can select $3n$ lines to perform an operation on ($n$ lines parallel to each side of the triangle.) Performing an operation twice on the same line is equivalent to doing nothing. Hence, we will describe any combination of operations as a triple of $n$-tuples $((a_1, a_2, \dots, a_n), (b_1, b_2, \dots, b_n), (c_1, c_2, \dots, c_n))$, where each element $a_i, b_i, c_i$ is either 0 or 1 ($0$ means no operation, $1$ means the opposite), each tuple of the triple denotes operating on a line parallel to one of the sides, and the indices denote the number of marks in the row of operation. Let $A$ denote the set of all such $3n$-tuples, so that $|A| = 2^{3n}$.
Let $B$ denote the set of all admissible configurations. Let $N = \frac{n(n+1)}{2}$. We will describe each element of $B$ by an $N$-tuple $(z_1, z_2, \dots, z_N)$, where $z_i = 0$ if mark $i$ is black and $z_i = 1$ otherwise.
For each element $a \in A$, let $b = f(a)$ be the element of $B$ that is the result of applying the operations in $a$. Then $f(a + a') = f(a) + f(a')$ for all $a, a' \in A$, where addition is considered in modulo 2. Let $K$ be the set of all $a \in A$ such that $f(a)$ is the all-black configuration. The following eight elements are easily seen to be in $K$.

* $((0, 0, \dots, 0), (0, 0, \dots, 0), (0, 0, \dots, 0)) = \text{id}$
* $((0, 0, \dots, 0), (1, 1, \dots, 1), (1, 1, \dots, 1)) = x$
* $((1, 1, \dots, 1), (1, 1, \dots, 1), (0, 0, \dots, 0)) = y$
* $((1, 1, \dots, 1), (0, 0, \dots, 0), (1, 1, \dots, 1)) = x + y$
* $((0, 1, 0, 1, \dots), (0, 1, 0, 1, \dots), (0, 1, 0, 1, \dots)) = z$
* $((0, 1, 0, 1, \dots), (1, 0, 1, 0, \dots), (1, 0, 1, 0, \dots)) = x + z$
* $((1, 0, 1, 0, \dots), (1, 0, 1, 0, \dots), (0, 1, 0, 1, \dots)) = y + z$
* $((1, 0, 1, 0, \dots), (0, 1, 0, 1, \dots), (1, 0, 1, 0, \dots)) = x + y + z$
We will show that they are the only elements of $K$.
Suppose $L = ((a_1, a_2, \dots, a_n), (b_1, b_2, \dots, b_n), (c_1, c_2, \dots, c_n))$ is in $K$. For $i+j+k = 2n+1$, there is a unique mark contained in a row of length $i$ in the $a$ direction, a row of length $j$ in the $b$ direction, and a row of length $k$ in the $c$ direction. Operations $a_i$, $b_j$, and $c_k$ are the only operations affecting the mark, so $a_i + b_j + c_k = 0$. By adding one or both of $x$ and $y$ if necessary, we will assume that $b_n = c_n = 0$. Since $a_2 + b_{n-1} + c_n = a_2 + b_n + c_{n-1} = 0$, we have that $b_{n-1} = c_{n-1}$. We now have two cases.

a. First, suppose that $b_{n-1} = c_{n-1} = 0$. Then from $a_3+b_{n-2}+c_n = a_3+b_{n-1}+c_{n-1} = a_3+b_n+c_{n-2}$, we have that $b_{n-2} = c_{n-2} = 0$. Continuing in this manner (considering equalities with $a_4, a_5, \dots$), we find that all the $b_i$'s and $c_i$'s are 0, from which we deduce that $L = \text{id}$.

b. Second, suppose that $b_{n-1} = c_{n-1} = 1$. Then from $a_3 + b_{n-2} + c_n = a_3 + b_{n-1} + c_{n-1} = a_3 + b_n + c_{n-2}$, we have that $b_{n-2} = c_{n-2} = 0$. Continuing in this manner (considering equalities with $a_4, a_5, \dots$), we find that $(b_1, b_2, \dots, b_n) = (c_1, c_2, \dots, c_n) = (\dots, 1, 0, 1, 0)$, from which we deduce that either $L = z$ or $L = x + z$.

Hence $L$ is one of the eight elements listed above. It follows that the $2^{3n}$ elements of $A$ form $2^{3n-3}$ sets consisting of elements differing by an element of $K$. Each $a \in A$ corresponds to an element of $B$ which is the result of applying the operations in $a$. For each element $a \in A$, let $x_1$ be the number of $a_i$ with odd indices which are equal to 1, and let $x_2$ be the number of $a_i$ with even indices which are equal to 1. Define $y_1, y_2, z_1$, and $z_2$ similarly for the $b_i$'s and $c_i$'s. Note that for each choice of $(x_1, x_2, y_1, y_2, z_1, z_2)$, there is at least one element of $A$ which corresponds to this choice.
Let $T(a)$ be the minimum value of $T$ over the set containing $a$. The maximum of this value over all the sets is the desired answer. For an element $a \in A$ with minimal value of $T$ in its set, adding an element of $K$ to $a$ must increase the value of $T$. Conversely if adding any element of $K$ to $a$ decreases $T$, then $a$ has the minimal value of $T$ within its set. Applying this observation for $x, y, x+y, z, x+z, y+z, x+y+z \in K$, we see that $a \in A$ has the minimal value of $T$ within its set if and only if the following inequalities hold.

(a) $x_1 + x_2 + y_1 + y_2 \le n$
(b) $x_1 + x_2 + z_1 + z_2 \le n$
(c) $y_1 + y_2 + z_1 + z_2 \le n$

(d) $x_2 + y_2 + z_2 \le \left\lfloor \frac{3\lfloor n/2 \rfloor}{2} \right\rfloor = V$
(e) $x_1 + y_1 + z_2 \le \left\lfloor \frac{2\lfloor n/2 \rfloor + \lfloor n/2 \rfloor}{2} \right\rfloor = W$

$$(f) \quad x_2 + y_1 + z_1 \le \left\lfloor \frac{2\lfloor n/2 \rfloor + \lfloor n/2 \rfloor}{2} \right\rfloor = W$$
$$(g) \quad x_1 + y_2 + z_1 \le \left\lfloor \frac{2\lfloor n/2 \rfloor + \lfloor n/2 \rfloor}{2} \right\rfloor = W$$
Adding the last four inequalities and dividing by 4, we obtain
$$T(a) \le \left\lfloor \frac{V + 3W}{2} \right\rfloor.$$
We analyze this in four separate cases:

a. $n = 4k$. Then $V = W = 3k$, and so $T(a) \le 6k$, with equality for $x_1 = x_2 = y_1 = y_2 = z_1 = z_2 = k$.
b. $n = 4k + 1$. Then $V = 3k$ and $W = 3k + 1$, and so $T(a) \le 6k + 1$ with equality for $x_1 = x_2 = y_1 = y_2 = z_2 = k$ and $z_1 = k + 1$.
c. $n = 4k + 2$. Then $V = 3k + 1$ and $W = 3k + 1$, and so $T(a) \le 6k + 2$ with equality for $x_1 = x_2 = y_1 = y_2 = k$ and $z_1 = z_2 = k + 1$.
d. $n = 4k + 3$. Then $V = 3k + 1$ and $W = 3k + 2$, and so $T(a) \le 6k + 3$ with equality for $x_1 = x_2 = y_2 = k$ and $y_1 = z_1 = z_2 = k + 1$.
In each case, observe that $T(a) \le n + 2 \lfloor \frac{n}{4} \rfloor$ and that equality is attained for some configuration in $A$, hence the maximum value of $T(a)$ is as claimed, concluding our proof.