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
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
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\;\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}$
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
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
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.
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:
(I used A instead of 10 so that it would look cleaner.)Code:1 2 3 4 5 6 7 8 9 A 7 2 3 A 4 5 6 8 9 1
I would try to find a formula like Soroban did. Haven't worked on it yet, but what have you tried so far?
$\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.)
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.
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.