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

**mido22** · July 6th 2010, 05:42 AM

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

**Soroban** · July 6th 2010, 08:13 AM

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} \qquad\Rightarrow \qquad \begin{array}{c}\circ\;\circ\;\circ\;\circ\;\bulle t\;\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 $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}$

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

**undefined** · July 6th 2010, 08:15 AM

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!

**mido22** · July 6th 2010, 08:27 AM

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!

thx 4 reply
1st: how can i remove solved???
2nd: it is a problem in programming and i want a formula to solve it
here is the link:
Sphere Online Judge (SPOJ) - Problem MINCOUNT

**mido22** · July 6th 2010, 08:30 AM

thx soroban

but can u explain more i didn't understand u

**undefined** · July 6th 2010, 08:45 AM

Originally Posted by mido22

thx 4 reply
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
here is the link:
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:

(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** · July 6th 2010, 08:49 AM

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

but it is wrong answer

**undefined** · July 6th 2010, 09:16 AM

Originally Posted by mido22

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

but it is wrong answer

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.

**undefined** · July 6th 2010, 09:44 AM

Here's the answer

Spoiler:

**mido22** · July 6th 2010, 12:49 PM

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

**undefined** · July 6th 2010, 01:57 PM

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.)

**undefined** · July 6th 2010, 02:03 PM

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.

**mido22** · July 7th 2010, 05:38 AM

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

**undefined** · July 7th 2010, 05:55 AM

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.

**mido22** · July 7th 2010, 06:45 AM

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)

Thread: want formula for number of moves to invert 'triangle'.

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

How do I setup a formula to make ANY number into a number between X & Y ?

Invert this ellipsoid formula

How to invert binary number in schematic?

A particle moves according to a law of motion (Derivatives Chapter)

Aparticle moves.......