# SOLVEDwant formula for number of moves to invert 'triangle'.

#### mido22

for example
:
* means a coin

a triangle of coins like this:
*
* *
* * *
its number is 3
when i invert it it will be like that:
* * *
* *
*
for more explination:

i want a formula to calculate the minimum transfers of coins to invert triangle

Last edited:

#### Soroban

MHF Hall of Honor
Hello, mido22!

A triangle of coins like this: .$$\displaystyle \begin{array}{c}o \\ [-2mm] o\;o \\ [-2mm] o\;o\;o \\ [-2mm] o\;o\;o\;o\end{array}$$
Its dimension is $$\displaystyle d = 4.$$

When inverted, it looks like this: .$$\displaystyle \begin{array}{c}\ o\;o\;o\;o \\ [-2mm]o\;o\;o \\ [-2mm]o\;o \\ [-2mm] o \end{array}$$

Find a formula for $$\displaystyle n$$, the minimum moves of coins to invert a triangle.

I cranked out the first few cases and found that there are two formulas,
. . depending on the parity of $$\displaystyle d$$ (odd or even).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

$$\displaystyle d = 2\qquad \begin{array}{c} \bullet \\ [-2mm] \circ\;\circ \end{array} \qquad\Rightarrow\qquad \begin{array}{c} \circ\;\circ \\ [-2mm] \bullet \end{array} \qquad n = 1$$

$$\displaystyle d = 4 \qquad\begin{array}{c}\bullet \\ [-2mm] \bullet\;\bullet \\ [-2mm] \circ\;\circ\;\circ \\ [-2mm] \bullet\;\circ\;\circ\;\circ \end{array} \qquad \Rightarrow\qquad \begin{array}{c} \circ\;\circ\;\circ\;\bullet \\ [-2mm] \circ\;\circ\;\circ \\ [-2mm]\bullet\;\bullet \\ [-2mm]\bullet \end{array} \qquad n = 4$$

$$\displaystyle d = 6 \qquad \begin{array}{c}\bullet \\ [-2mm] \bullet\;\bullet \\ [-2mm]\bullet\;\bullet\;\bullet \\ [-2mm]\circ\;\circ\;\circ\;\circ \\ [-2mm]\bullet\;\circ\;\circ\;\circ\;\circ \\ [-2mm]\bullet\;\bullet\;\circ\;\circ\;\circ\;\circ \end{array} \qquad\Rightarrow\qquad \begin{array}{c} \circ\;\circ\;\circ\;\circ\;\bullet\;\bullet \\ [-2mm] \circ\;\circ\;\circ\;\circ\;\bullet \\ [-2mm] \circ\;\circ\;\circ\;\circ \\ [-2mm] \bullet\;\bullet\;\bullet \\ [-2mm]\bullet\;\bullet \\ [-2mm]\bullet \end{array} \qquad n = 9$$

For even $$\displaystyle d,\;n$$ is the sum of two consecutive Triangular Numbers.

. . $$\displaystyle \begin{array}{ccccc}\text{For }d = 2\!: & n \:=\:T_0 + T_1 \\ \text{For }d = 4\!: & n \:=\:T_1 + T_2 \\ \text{For }d = 6\!: & n \:=\:T_2 + T_3 \\ \vdots & \vdots \\ \text{For }d = 2k\!: & n \:=\:T_{k-1} + T_k &=& k^2 \end{array}$$

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

$$\displaystyle d = 3 \qquad\begin{array}{c}\bullet \\ [-2mm] \circ\;\circ \\ [-2mm] \bullet\;\circ\;\circ \end{array} \qquad\Rightarrow\qquad \begin{array}{c} \circ\;\circ\;\bullet \\ [-2mm] \circ\;\circ \\ [-2mm] \bullet \end{array} \qquad n = 2$$

$$\displaystyle d = 5 \qquad \begin{array}{c} \bullet \\ [-2mm] \bullet\;\bullet \\ [-2mm] \circ\;\circ\;\circ \\ [-2mm] \bullet\;\circ\;\circ\;\circ \\ [-2mm] \bullet\;\bullet\; \circ\;\circ\;\circ\end{array} \qquad\Rightarrow\qquad \begin{array}{c} \circ\; \circ\;\circ\;\bullet\;\bullet \\ [-2mm] \circ\;\circ\;\circ\;\bullet \\ [-2mm] \circ\; \circ\;\circ \\ [-2mm] \bullet\;\bullet \\ [-2mm] \bullet \end{array} \qquad n = 6$$

$$\displaystyle d = 7 \qquad \begin{array}{c}\bullet \\ [-2mm] \bullet\;\bullet \\ [-2mm] \bullet\;\bullet\;\bullet \\ [-2mm] \circ\;\circ\;\circ\;\circ \\ [-2mm] \bullet\;\circ\;\circ\;\circ\;\circ \\ [-2mm] \bullet\;\bullet\;\circ\;\circ\;\circ\;\circ \\ [-2mm] \bullet\;\bullet\;\bullet\;\circ\;\circ\;\circ\;\circ \end{array} \qquad\Rightarrow \qquad \begin{array}{c}\circ\;\circ\;\circ\;\circ\;\bullet\;\bullet\;\bullet \\ [-2mm] \circ\;\circ\;\circ\;\circ\;\bullet\;\bullet \\ [-2mm] \circ\;\circ\;\circ\;\circ\;\bullet \\ [-2mm] \circ\;\circ\;\circ\;\circ \\ [-2mm] \bullet\;\bullet\;\bullet \\ [-2mm] \bullet\;\bullet \\ [-2mm] \bullet \end{array} \qquad n = 12$$

For odd $$\displaystyle d,\:n$$ is twice a Triangular Number.

. . $$\displaystyle \begin{array}{ccccc}\text{For }d = 3\!: & n \:=\:2\cdot T_1 \\ \text{For }d = 5\!: & n \:=\:2\cdot T_2 \\ \text{For }d = 7\!: & n \:=\:2\cdot T_3 \\ \vdots & \vdots \\ \text{For }d = 2k+1\!: & n \:=\:2\cdot T_k &=& k(k+1) \end{array}$$

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

#### undefined

MHF Hall of Honor
plz help me anyone
Hi, I see you're a little new to the forum, and welcome.

You marked your thread as [SOLVED], which leads people not to make further posts because they believe you solved the problem on your own!

As for the problem, I don't know what you mean, and could you explain the rules more? What constitutes a "move"? Why did the yellow coins become blue in your image?

EDIT: It looks like Soroban knew what you meant. Nice problem!

#### mido22

Hi, I see you're a little new to the forum, and welcome.

You marked your thread as [SOLVED], which leads people not to make further posts because they believe you solved the problem on your own!

As for the problem, I don't know what you mean, and could you explain the rules more? What constitutes a "move"? Why did the yellow coins become blue in your image?

EDIT: It looks like Soroban knew what you meant. Nice problem!
1st: how can i remove solved???
2nd: it is a problem in programming and i want a formula to solve it
Sphere Online Judge (SPOJ) - Problem MINCOUNT

#### mido22

thx soroban

but can u explain more i didn't understand u

#### undefined

MHF Hall of Honor
1st: how can i remove solved???
Should be near the top right of the thread: see where it says "Thread tools"? On a thread I started, there is an option "Mark this thread as solved..." I'm guessing you have a reverse option available.

2nd: it is a problem in programming and i want a formula to solve it
Sphere Online Judge (SPOJ) - Problem MINCOUNT
Looking at test cases, it seems Soroban's answer doesn't give the minimal number of moves as desired. After staring mindlessly at the diagram for five minutes, I see how it's possible to invert h=4 in 3 moves:

Code:
   1
2 3
4 5 6
7 8 9 A

7 2 3 A
4 5 6
8 9
1
(I used A instead of 10 so that it would look cleaner.)

I would try to find a formula like Soroban did. Haven't worked on it yet, but what have you tried so far?

#### mido22

i tried this formula
(((n-2)*((n-2)-1))/2)+2)

#### undefined

MHF Hall of Honor
i tried this formula
(((n-2)*((n-2)-1))/2)+2)

Okay I can actually see where you got that formula; it's 2+T(h-3), where T(n) gives the nth triangle number.

It fails for h=6. There is a way to invert a triangle with height 6 using only 7 moves.

Last edited:

#### undefined

MHF Hall of Honor

A001840 on OEIS.

Formula: $$\displaystyle \displaystyle f(h)=\left\lfloor \frac{h(h+1)}{6}\right\rfloor$$

#### mido22

thx at all(Itwasntme)

but it can't be the right formula that
if h=4
the result will be : 3.3333333333>>>

and it must be 3 only

also when i write it to my program the judge tells me wrong answer

Last edited: