# Math Help - want formula for number of moves to invert 'triangle'.

1. ## want formula for number of moves to invert 'triangle'.

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

2. Hello, mido22!

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

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

Find a formula for $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 $d$ (odd or even).

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

$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$

$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$

$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 $d,\;n$ is the sum of two consecutive Triangular Numbers.

. . $\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}$

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

$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$

$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$

$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\;\c irc \end{array}
\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 $d,\:n$ is twice a Triangular Number.

. . $\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}$

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

3. Originally Posted by mido22
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!

4. Originally Posted by undefined
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

5. thx soroban

but can u explain more i didn't understand u

6. Originally Posted by mido22
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.

Originally Posted by mido22
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?

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

8. Originally Posted by mido22
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.

Spoiler:

A001840 on OEIS.

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

10. thx at all

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

11. Originally Posted by mido22
thx at all

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
$\displaystyle f(4)=\left\lfloor \frac{4(4+1)}{6}\right\rfloor=\left\lfloor \frac{10}{3}\right\rfloor=3$. See floor function. Find out how to use the floor function in your programming language; using integer division has the same effect. (Coincidentally, the example on the MathWorld page for integer division is exactly the same calculation done in this post.)

12. By the way, here is how I got the first few terms. Consider h=6. Write

1
2
3
4
5
6

Now consider making the third row the new top row. Take coins from row 6 and put them in row 3.

1
2
3+3=6
4
5
6-3=3

Now take a coin from the row 5 and put it in row 4.

1
2
6
5
4
3

Lastly, move the top two rows to the bottom.

6
5
4
3
2
1

We see this is (3+1) + (1+2) = 7.

We could also have worked it out like this

1
2
3
4
5
6

1
2+4
3+2
4
5-2
6-4

giving (4+2) + (1) = 7.

You can continue further with higher values of h.

13. thx very much for help but it still wrong answer with my code

then my friend tell me that he found an equation about it if i knew i would write it in this thread

14. Originally Posted by mido22
thx very much for help but it still wrong answer with my code

then my friend tell me that he found an equation about it if i knew i would write it in this thread
Are you sure it's a wrong equation as opposed to wrong presentation? Or possibly something like integer overflow? Also be careful with test cases like h=0 since it is a little unclear whether 0 or the empty string is supposed to be returned. Anyway OEIS is occasionally wrong but it's not typical. I could work it out further on paper or code a (slower but dependable) algorithmic approach based on my previous post, and it could be used to test against the formula.

Note that starting around 1/6 of the maximum value of a 64-bit long you will have overflow problems with that formula.

I might even join the programming site.. I'm a bit busy though.

15. Originally Posted by undefined
Are you sure it's a wrong equation as opposed to wrong presentation? Or possibly something like integer overflow? Also be careful with test cases like h=0 since it is a little unclear whether 0 or the empty string is supposed to be returned. Anyway OEIS is occasionally wrong but it's not typical. I could work it out further on paper or code a (slower but dependable) algorithmic approach based on my previous post, and it could be used to test against the formula.

Note that starting around 1/6 of the maximum value of a 64-bit long you will have overflow problems with that formula.

I might even join the programming site.. I'm a bit busy though.
here is the correct formula:
(n*( n+1 ) /2 )/3)

Page 1 of 2 12 Last