Incorrect solution used to be here >_<

Apparently everyone who did this problem forgot that if n=2, the answer is 2, not 3. Huh.

I messed up >_< didn't check on smaller cases. But otherwise that works.

Do you have a proof that the construction works? Taking all the rows in 2 different directions is not the only way to have a sequence of distinct moves cancel out.

Your question confuses me.

Like how do you know that the construction you gave for floor(3n/2) can't be reached by fewer moves?

Darn is what I said when I realized that I had forgotten to label my 8th of 10 pages.

Sorry I'm bad with pictures

OOPS james4l probably has a better proof than me

Semi-sketch, will edit later on. (stevenmeow if you want you can take care of the identity part since I don't really feel like replicating it here T_T)

Huh the identities are basically solving a_i+b_j+c_k = 0 mod 2 for i,j,k from 1 to n with i+j+k=2n+1, and letting i=m,j = n+1-m,k = n and i = m+1, j = n+1-m,k = n-1, we find $a_{m+1}-a_m = c_n-c_{n-1}$, and doing this cyclically we find that all the $a_{i+1}-a_i$, $b_{i+1}-b_i$,$c_{i+1}-c_i$ are the same which immediately implies what the identities are combined with $a_n+b_n+c_1$ is 0.

I think this hammers out the details of the identities well enough. If only I had time to reword/clean up/finish this solution during the test.

This solution shows my motivation, though.

can any one give some details about the lower bound?

The answer is \[ \max_C f(C) = \begin{cases} 6k & n = 4k \\ 6k+1 & n = 4k+1 \\ 6k+2 & n = 4k+2 \\ 6k+3 & n = 4k+3. \end{cases} \]The main point of the problem is actually to determine all linear dependencies among the $3n$ possible moves (since the moves commute and applying a move twice is the same as doing nothing). In what follows, assume $n > 1$ for convenience. To this end, we consider sequences of operations as additive vectors in $v \in \mathbb F_2^{3n}$, with the linear map $T : \mathbb F_2^{3n} \to \mathbb F_2^{\frac{1}{2} n(n+1)}$ denoting the result of applying a vector $v$. We in particular focus on the following four vectors. Three vectors $x$, $y$, $z$ are defined by choosing all $n$ lines parallel to one axis. Note $T(x) = T(y) = T(z) = \mathbf 1$ (i.e.\ these vectors flip all tokens). The vector $\theta$ which toggles all lines with an even number of tokens. One can check that $T(\theta) = \mathbf 0$. The main claim is: Claim: The kernel of $T$ has exactly eight elements, with basis $\{x+y, x+z, \theta\}$. Proof. It's clear these are distinct elements of the kernel. To see that is all, suppose $T(v) = 0$. By shifting by $y$, $z$, or $\theta$, we can assume $v$ has $0$ coefficient for two lines of length $n$, and a third line of length $2$ (not parallel to previous two). Then one can inductively show $v = 0$. $\blacksquare$ Then problem is a coordinate bash, since given any $v$ we now know exactly which vectors $w$ have $T(v) = T(w)$, so given any admissible configuration $C$ one can exactly compute $f(C)$ as the minimum of eight values. (See EmptySet's solution above for this answer extraction, for example.)

Here is another approach to obtain the upper bound on the maximum value of $f$ (which is probably equivalent to the approaches described above): Suppose a configuration $\mathcal{D}$ can be arranged in $m$ operations using a sequence of operations $S$. There are a total of $3n$ possible operations so this leaves $3n-m$ operations not in $S$. If we label the sides of the triangle as $A$, $B$, $C$, then there are $n$ operations which act in lines parallel to each of $A$, $B$, and $C$. In particular, of the $3n-m$ operations unused, $x \ge \left \lceil \frac{3n-m}{3} \right\rceil$ of them are parallel to a specific side, WLOG $A$. Therefore, we could also obtain $\mathcal{D}$ by applying the $n$ operations parallel to $A$ and then the $3n-m$ operations unused in $S$; however, we can do even better: each of the $x$ operations not in $S$ parallel to side $A$ are done twice in this process; we can therefore avoid ever doing them at all. Then: \begin{align*} f(\mathcal{D}) &\le \min(m, n + (3n-m) - 2x) \\ &\le \min\left(m, 4n - m - 2\left\lceil \frac{3n-m}{3} \right\rceil\right) \\ &= \min \left(m, 2n - m + 2\left \lfloor \frac{m}{3} \right \rfloor \right) \end{align*} The last statement is maximized for $n = \left\lfloor \frac{3}{2}n \right\rfloor$, giving $f(\mathcal{D}) \le \left \lfloor \frac{3}{2}n \right \rfloor$. This is optimal for $n \equiv 0, 1 \pmod 4$ and one higher than optimal for $n \equiv 2, 3 \pmod 4$.

The answer is $\left\lfloor\frac{3}{2} n\right\rfloor$ for $n\equiv 0,1\mod 4$ and $\left\lfloor\frac{3}{2} n\right\rfloor-1$ for all other $n$. First, we will show there are at least $2^{3n-3}$ possible admissible configurations. We will show this by choosing $3n-3$ marks such that any subset of these will be admissible, and we will choose this subset by induction on $n$. Make the initial observation that if, for this set, by flipping exactly one of them will make the resulting configuration admissible, then any subset of them will be admissible (because we can combine the operations, and then for each operation we do it if the parity of that number of operations performed is odd). Our base case is $n = 2,3,4$. For $n = 2,3$, choose all the marks. For $n = 4$ choose all the marks except for the one at the bottom row, 2nd leftmost. Casework allows all three of these cases two work (we only have to prove admissibility for each mark flippped). Now, consider our inductive step, where for all $j < n$ there exists a set of $3j - 3$ marks. We have two cases: Case 1: $n = 2k$. In this case, consider the $k+2$ size equilateral triangle such that it intersects the bigger equilateral triangle at the $k$th and $k+1$th leftmost marks (so this means the $3$ endpoints of the $k+2$ size equilateral triangle don't lie in the big one). Since $k + 2 < 2k$, by our inductive step, we can choose $3(k+2) - 3$; we will also remove the $3$ endpoints for $3k$. Now, choose the $k-1$ leftmost points on the bottom row; this still allows the central $k+2$ triangle with each mark flipped admissible, and also each of these $k-1$ points, since for each point there exists a line going through it not going through any of the other points in this set, so we can always use this operation to change it however we like. We can choose another $2(k-1)$ from the other two rows, for a total of $6k - 3 = 3(2k) - 3$. Case 2: $n = 2k+1$. We do the same thing as the previous case: choose the central $k+1$ size triangle for a total of $3k$, and now choose the $k$th leftmost on each row for a total of $3k + 3k = 3(2k+1) - 3$. This completes our induction. We conclude that there are at least $2^{3k-3}$ admissible configurations. Observe that there are a total of $2^{3k}$ "movesets" (each operation has $2$ choices, and there are $3k$ operations). This means there are at most $2^3 = 8$ movesets that result in no total change (call these uneventful movesets), otherwise for each of the $2^{3k-3}$ admissible configurations we can apply each uneventfull moveset for a total of more than $2^{3k}$ movesets, a contradiction. These $8$ uneventfull movesets are: No moves Only rows an even distance from the top for two vertices, and only rows an odd distance from the top for the last vertex Only rows an odd distance from the top for each vertex Moving every row parallel to two of the sides, none of the third Now, for each moveset, we are able to apply these $8$ uneventfull movesets to find it's minimum. Boring casework results in the answer and construction.

If $n = 1$, the answer is just $1$. There are at most $3n$ possible moves, thus the space of admissible config is a subspace of ${\mathbb F}_2^{3n}$ and embeds in ${\mathbb F}_{2}^{\frac{n(n+1)}{2}}$. Consider the linear map $f \colon {\mathbb F}_2^{n} \to {\mathbb F}_2^{\frac{n(n+1)}{2}}$. Classify operations based off whether they are row, column, or diagonal after shifting the equilateral triangle into a right triangle. Define an operation based off its length. Claim: $|\ker f| = 8$. Proof. We first show that there are $3$ linearly independent elements of a kernel. Two of them are obtained from having all operations of two types. The third one is obtained by having all operations of an even length. This follows by taking a coordinate system $(a, b, c)$ based off row length, and noting that $a + b + c = 2n + 1$. We now show that for a given admissible config, and given the states of whether there were $3$ operations, we can uniquely determine the states of the remaining $3n - 3$ operations. Take the three states of the diagonal length $2$, and the horizontal/vertical with length $n - 1$. Note that for a cell, if we know the states of two operations that go through it, we know the third. As such, we know the states of the length $n$ horizontal/vertical, as well as the diagonal of length $3$ if it exists. This in turn allows us to discover the state of the horizontals and verticals of length $n - 2$, and we can repeat until we know all states. $\blacksquare$ As such, $f(C)$ for a certain $C$ is the minimum number of $1$s for an element in $C + \ker f$. Claim: If $n = 2k + i$ for $i \in \{0, 1\}$, then $f(C) \le 3k + i$. Proof. Let $a, b, c$ be the number of $1$s for each operation type. If one of $a + b, b + c, c + a$ is more than $n = 2k + i$, inverting around that decreases the sum. As such, summing we get $a + b + c < \frac{3}{2} \cdot (2k + i)$. $\blacksquare$ Claim: If $n = 4k + i$ for $i \in \{0, 1, 2, 3\}$, then $f(C) \le 3k + i$. Proof. Note that the inverting operation preserves parity. However, if $n \equiv 2, 3 \pmod{4}$ then the inverting evens operation does not preserve parity, else it does. This allows us to further decrease the number of $1$s. $\blacksquare$ Claim: If $n = 4k + i$, then $\underset{C}{\max} f(C) = 6k + i$ Proof. Note that this is maximal. Then, For $n = 4k$, take $a = b = c = 2k$ with $k$ evens in each case. For $n = 4k + 1$, take $a = b = 2k, c = 2k + 1$ with $k$ evens in each case. For $n = 4k + 2$, take $a = b = 2k, c = 2k + 2$ with $k$ evens for $a, b$, $k + 1$ evens for $c$. For $n = 4k + 3$, take $a = b = c = 2k + 1$ with $k$ evens in each case. Manually checking all cases gives the result. Note that this is consistent with $n = 1$. $\blacksquare$

This problem is headache-inducing... but also fun. Ouch. Let $n = 4k + b$ where $b \in {1, 2, 3, 4}$. Then I claim the answer is $6k+1, 6k+2, 6k+3, 6k+6$ in these four cases. First, note that the base cases $n = 1, 2, 3$ are trivial by checking to be $1, 2, 3$. Now note the case $n = 4$ needs at least $6$ to construct a black triangle with a single white mark at its center by checking. Call this size $4$ triangle the evil triangle. To show the lower bound, notice we can take the top $n$ rows of a $n+4$ equilateral triangle to be the limiting case for $n$ and put two evil triangles on the bottom left and bottom right, respectively: these force $4$ new rows to be occupied since each evil subcase requires at least two rows in every direction, which is a claim easy verified. To show the upper bound, we reparameterize the triangles in terms of their rows. Notably, we can start counting rows from each corner, and give each mark a barycentric coordinate $(a, b, c)$ where $a, b, c$ are integers denoting the $i$th row in a given direction the point lies in, and this satisfies $a+b+c = 2n+1$ by Viviani's theorem. Now, consider the configuration $C$ that minimizes $f(C)$. We place the rows in boxes: odd rows of each direction, and even rows of each direction, to make six boxes total. Call the numbers of odd rows $a, b, c$ and the even rows $d, e, f$ such that $(a, b, c)$ and $(d, e, f)$ correspond to the same directions respectively in that order. Notice no row is operated on twice since row operations are commutative. Assume for sake of contradiction our claim is wrong, then we can construct a solution for the case one higher than our claim. We now perform casework: for $b = 4$, it follows one of the quantities $a+b+d+e, b+c+e+f, c+a+f+d$ is greater than $n$. In this case, invert the rows chosen in those four boxes (i.e. remove the ones chosen and choose the ones unchosen). This fixes the configuration and decreases $f(C)$, giving contradiction. Now, consider the case $b = 1$. Like the above paragraph, we know $a+d, b+e, c+f$ are equal to $2k, 2k+1, 2k+1$ in some order since if any pair sums to more than $4k+1$ then we reach a contradiction. But then $2k+1 + 2k + 1 > 4k + 2$, giving contradiction. Now, for the two remaining cases, we show a lemma: the xor of all the odd rows in two directions and all the even row in a third direction, or the sum of all the even rows in all directions are both $0$. This result follows immediately from our earlier result via Vivani's theorem (it cannot be that all three claims are true, and it cannot be the case that two of the claims are false and one is true by parity). Thus in the $b = 2$ case it follows that $\min(a+b+f, b+c+d, c+a+e, d+e+f) \geq \frac{12k+6}{4}$ so one of the triples is at least $3k + 2$. However inverting the three involved boxes, that total to $6k+3$ rows and don't affect the configuration when all three are inverted, decreases the $f(C)$, giving contradiction. Finally, in the $b = 3$ it follows that $(a+b+f)+(b+c+d) + (c+a+e) + (d+e+f) =12k+8$. In particular, the odd/odd/even triples consist of $\frac{n+1}{2} + \frac{n+1}{2} + \frac{n-1}{2} = 6k+5$ rows each, while the even/even/even triple consists of $3 \cdot \frac{n-1}{2} = 6k+3$ rows. For each of the triples to avoid decreases $f(C)$ after being inverted, it needs to satisfy either $\leq 3k + 2$ or $\leq 3k+1$ depending on the two cases, so it follows that $LHS \leq 12k + 7$, giving contradiction. Thus we have reached contradiction in all cases of counterexamples, proving our desired claim.