¿Números triangulares divididos por $3$?

Question

Me encontré con este problema.

Quiero mover de un tirón un triángulo al revés y encontrar el mínimo número de movimientos para hacerlo.

Estos son todos los números triangulares. Y he encontrado que dividiendo el número total de monedas $(N)$ $3$ le dará el resultado requerido $(m)$ (ignorando el resto).

N=3 => m=1
N=6 => m=2
N=10 => m=3 (ignoring r=1)
N=15 => m=5
N=21 => m=7
.. and so on

He tratado de hacer esto, y todos mis resultados han sido consistentes con este resultado: $m=N/3$ hasta la fecha. Pero no estoy seguro de si esto es cierto para todos los $N$ ya que no puedo probar esto en una lógica coherente.

Esto es cierto para todos los $N$, y cuál es la razón detrás de esto?

Answer 1

Deje $A$ ser el triángulo de lado de longitud $n$, $B$ ser un triángulo al revés volteado de la $A$. Para minimizar el número de movimientos de $m$, sólo necesitamos maximizar el número de monedas en $A \cap B$, que se denota como $S$, es decir, esas monedas que no necesita ser movido.

Supongamos que la primera fila de $B$ está en el mismo nivel de la $i$ésima fila de a $A$. Para obtener una máxima $S$ (no puede ser el máximo, depende de $i$) $i$ésima fila de a $A$ debe estar en el medio de la primera fila de $B$. A continuación, la parte $B - A \cap B$ consta de tres triángulos. Vea la figura de abajo (los triángulos con sombreado). Ellos son el número mínimo de monedas que necesita para moverse cuando la primera fila de $B$ está en el mismo nivel de la $i$ésima fila de a $A$.

Hay un total $m$ monedas en $B - A \cap B$, donde \begin{align} m &= \frac{(\lceil \frac{n-i}{2} \rceil + 1)\lceil \frac{n-i}{2} \rceil}{2} +\frac{(\lfloor \frac{n-i}{2} \rfloor + 1)\lfloor\frac{n-i}{2} \rfloor}{2} + \frac{i(i-1)}{2} \\ &= \frac{\lceil \frac{n-i}{2} \rceil^2 + \lfloor \frac{n-i}{2} \rfloor^2 + i^2 + n - 2i}{2} \end{align} Debemos encontrar la $i$ que hacen de $m$ minimizado.

He calculado el mínimo de $m$ para differnt $n$ (calculando el óptimo $i$), que se resumen en la siguiente tabla ($k \geq 0$). $$ \pequeño{ \begin{array}{c|c|c|c|c|c|c} n & 6k & 6k + 1 & 6k + 2 & 6k + 3 & 6k + 4 & 6k + 5\\ \hline N & 18k^2 + 3k & 18k^2 + 9k + 1 & 18k^2 + 15k + 3 & 18k^2 + 21k + 6 & 18k^2 + 27k + 10 & 18k^2 + 33k + 15\\ \hline \text{optimal } m & 6k^2 + k & 6k^2 + 3k & 6k^2 + 5k + 1 & 6k^2 + 7k + 2 & 6k^2 + 9k + 3 & 6k^2 + 11k + 5 \end{array} } $$

Por lo tanto, tenemos $$ \text{óptimo } m = \lfloor \frac{N}{3} \rfloor $$