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

Jun 2010
145
3
Zewail University - Cairo - Egypt
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
May 2006
12,028
6,341
Lexington, MA (USA)
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
Mar 2010
2,340
821
Chicago
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!
 
Jun 2010
145
3
Zewail University - Cairo - Egypt
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
 
Jun 2010
145
3
Zewail University - Cairo - Egypt
thx soroban

but can u explain more i didn't understand u
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
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.

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?
 
Jun 2010
145
3
Zewail University - Cairo - Egypt
i tried this formula
(((n-2)*((n-2)-1))/2)+2)

but it is wrong answer
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
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.
 
Last edited:

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
Here's the answer

A001840 on OEIS.

Formula: \(\displaystyle \displaystyle f(h)=\left\lfloor \frac{h(h+1)}{6}\right\rfloor\)
 
Jun 2010
145
3
Zewail University - Cairo - Egypt
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: