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

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Jul 6th 2010, 05:42 AM
mido22
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:
http://www.spoj.pl/content/abhilash_i:invert
i want a formula to calculate the minimum transfers of coins to invert triangle
• Jul 6th 2010, 08:13 AM
Soroban
Hello, mido22!

Quote:

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

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
• Jul 6th 2010, 08:15 AM
undefined
Quote:

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!
• Jul 6th 2010, 08:27 AM
mido22
Quote:

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
here is the link:
Sphere Online Judge (SPOJ) - Problem MINCOUNT
• Jul 6th 2010, 08:30 AM
mido22
thx soroban

but can u explain more i didn't understand u
• Jul 6th 2010, 08:45 AM
undefined
Quote:

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.

Quote:

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:

  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?
• Jul 6th 2010, 08:49 AM
mido22
i tried this formula
(((n-2)*((n-2)-1))/2)+2)

but it is wrong answer
• Jul 6th 2010, 09:16 AM
undefined
Quote:

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.
• Jul 6th 2010, 09:44 AM
undefined

Spoiler:

A001840 on OEIS.

Formula: $\displaystyle \displaystyle f(h)=\left\lfloor \frac{h(h+1)}{6}\right\rfloor$
• Jul 6th 2010, 12:49 PM
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
• Jul 6th 2010, 01:57 PM
undefined
Quote:

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

$\displaystyle \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.)
• Jul 6th 2010, 02:03 PM
undefined
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.
• Jul 7th 2010, 05:38 AM
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(Hi)
• Jul 7th 2010, 05:55 AM
undefined
Quote:

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(Hi)

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.
• Jul 7th 2010, 06:45 AM
mido22
Quote:

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)
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last