Page 1 of 2 12 LastLast
Results 1 to 15 of 20

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

  1. #1
    Member
    Joined
    Jun 2010
    From
    Zewail University - Cairo - Egypt
    Posts
    136

    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
    Last edited by mido22; July 6th 2010 at 07:28 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,682
    Thanks
    614
    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}\<br />
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}<br />
\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\;<br />
\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]<br />
\bullet\;\bullet\;\bullet \\ [-2mm] \circ\;\circ\;\circ\;\circ \\ [-2mm]<br />
\bullet\;\circ\;\circ\;\circ\;\circ \\ [-2mm] \bullet\;\bullet\;\circ\;\circ\;\circ\;\circ \\<br />
[-2mm] \bullet\;\bullet\;\bullet\;\circ\;\circ\;\circ\;\c  irc \end{array}<br />
 \qquad\Rightarrow \qquad \begin{array}{c}\circ\;\circ\;\circ\;\circ\;\bulle  t\;\bullet\;\bullet \\ [-2mm]<br />
\circ\;\circ\;\circ\;\circ\;\bullet\;\bullet \\ [-2mm] \circ\;\circ\;\circ\;\circ\;\bullet \\<br />
[-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 \\<br />
\text{For }d = 7\!: & n \:=\:2\cdot T_3 \\ \vdots & \vdots \\<br />
\text{For }d = 2k+1\!: & n \:=\:2\cdot T_k &=& k(k+1) \end{array}


    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by mido22 View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Zewail University - Cairo - Egypt
    Posts
    136
    Quote Originally Posted by undefined View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2010
    From
    Zewail University - Cairo - Egypt
    Posts
    136
    thx soroban

    but can u explain more i didn't understand u
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by mido22 View Post
    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.

    Quote Originally Posted by mido22 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jun 2010
    From
    Zewail University - Cairo - Egypt
    Posts
    136
    i tried this formula
    (((n-2)*((n-2)-1))/2)+2)

    but it is wrong answer
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by mido22 View Post
    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 by undefined; July 6th 2010 at 09:35 AM. Reason: typo (wrote an "n" when i meant "h")
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Here's the answer

    Spoiler:

    A001840 on OEIS.

    Formula: \displaystyle f(h)=\left\lfloor \frac{h(h+1)}{6}\right\rfloor
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Jun 2010
    From
    Zewail University - Cairo - Egypt
    Posts
    136
    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
    Last edited by mido22; July 6th 2010 at 01:02 PM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by mido22 View Post
    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.)
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Jun 2010
    From
    Zewail University - Cairo - Egypt
    Posts
    136
    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
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by mido22 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Jun 2010
    From
    Zewail University - Cairo - Egypt
    Posts
    136
    Quote Originally Posted by undefined View Post
    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)
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: June 23rd 2011, 02:30 AM
  2. Invert this ellipsoid formula
    Posted in the Geometry Forum
    Replies: 1
    Last Post: March 9th 2011, 01:14 PM
  3. How to invert binary number in schematic?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 3rd 2009, 06:09 PM
  4. Replies: 3
    Last Post: October 7th 2009, 10:24 AM
  5. Aparticle moves.......
    Posted in the Calculus Forum
    Replies: 2
    Last Post: January 3rd 2008, 03:31 PM

/mathhelpforum @mathhelpforum