Minimum number of moves required to invert a triangular array of coins?

Question

I cannot find an equation that works WITHOUT rounding. The idea is to find the minimum number of moves to invert a triangle that is made out of counters. The triangle is arranged so that the first row has 1 counter, second row has 2 counters, third row as 3 counters, fourth row as 4 counters and so on. In one move you are allowed to move one coin. For a triangle with 4 rows the minimum number of moves to invert it so that it points downwards is 3. The triangle I'm talking about looks just like a pascals triangle with counters instead of numbers, but I'm not sure if pascals triangle is actually relevant or not. I would like to know a formula that can give the minimum number of moves that involves either the amount of rows, or the amount of counters.

Answer 1

Imagine the upright and the inverted triangle in the same figure. You can see $3\cdot2$ little triangles of counters that make up the symmetric difference of the two arrays. Assume these triangles have side lengths $p$, $q$, $r\in{\mathbb N}_{\geq0}$. It is easy to see that $p+q+r=n-1$, and that the total number of moved coins for this configuration is $$N={1\over2}\bigl(p(p+1)+q(q+1)+r(r+1)\bigr)\ .\tag{1}$$ In order to make $N$ as small as possible we have to make $p$, $q$, $r$ as equal as possible. Therefore we have to distinguish cases according to the remainder of $n$ modulo $3$:

Let $\bigl\lfloor{n\over3}\bigr\rfloor=:m$, and put $p:=m$, $q:=m$. If $n=3m$ put $r:=m-1$; if $n=3m+1$, put $r:=m$; and if $n=3m+2$, put $r:=m+1$.

Using $(1)$ one obtains the following end result: $$N_\min(n)=\left\lfloor{n(n-1)\over6}\right\rfloor\qquad(n\geq1)\ .$$