6
$\begingroup$

I came across this problem.

enter image description here

I want to flip a triangle upside down and find the minimum number of moves to do so.

These are all triangular numbers. And I have found that dividing the total number of coins $(N)$ by $3$ will give the required result $(m)$ (ignoring the remainder).

N=3 => m=1
N=6 => m=2
N=10 => m=3 (ignoring r=1)
N=15 => m=5
N=21 => m=7
.. and so on

I have tried to do this, and all my results have been consistent with this result: $m=N/3$ so far. But I am not sure if it is true for all $N$ as I cannot prove this in a logical cohesive manner.

Is this true for all $N$, and what is the reason behind this?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ add another row and see if it works ! and probably do an induction proof $\endgroup$ – alkabary Jun 6 '15 at 0:28
  • $\begingroup$ @alkabary I did as far as I could. I initially tried to approach this problem with a moderately complex algorithm based on a divide & conquer strategy. The answer always came as $N/3$, and I cannot figure out why it is so. $\endgroup$ – Rahul Thakur Jun 6 '15 at 1:06
  • $\begingroup$ it will not be the same moves if you added another row, because if you did the same moves, then you will have one ball and then three balls above it $\endgroup$ – alkabary Jun 6 '15 at 1:13
  • $\begingroup$ I'm not talking about the same moves, but the same type of moves which was based on my algorithm. But that is of no interest here, the same moves will never work. But the result was consistent with $N/3$ for as far as I checked $\endgroup$ – Rahul Thakur Jun 6 '15 at 1:19
  • $\begingroup$ @PrasunBiswas $m=5$ for $N=15$ & $m=7$ for $N=21$. I'm not sure if it'll be clear how from my notes, but here are the snaps from my notebook: inft.ly/3Psf2ZC, inft.ly/3gq2yVq $\endgroup$ – Rahul Thakur Jun 6 '15 at 1:59
4
$\begingroup$

Let $A$ be the triangle of side length $n$, $B$ be a upside-down triangle flipped from $A$. To minimize the # of moves $m$, we only need to maximize # of coins in $A \cap B$, denoted as $S$, i.e., those coins that don't need to be moved.

Suppose the first row of $B$ is in the same level of the $i$th row of $A$. To get a maximal $S$ (may be not the maximum, it is dependent on $i$), the $i$th row of $A$ should be in the middle of the first row of $B$. Then the part $B - A \cap B$ consists of three triangles. See the figure below (those triangles with hatch lines). They are the minimal number of coins we need to move when the first row of $B$ is in the same level of the $i$th row of $A$.

enter image description here

There are totally $m$ coins in $B - A \cap B$, where \begin{align} m &= \frac{(\lceil \frac{n-i}{2} \rceil + 1)\lceil \frac{n-i}{2} \rceil}{2} +\frac{(\lfloor \frac{n-i}{2} \rfloor + 1)\lfloor\frac{n-i}{2} \rfloor}{2} + \frac{i(i-1)}{2} \\ &= \frac{\lceil \frac{n-i}{2} \rceil^2 + \lfloor \frac{n-i}{2} \rfloor^2 + i^2 + n - 2i}{2} \end{align} We should find the $i$ that make $m$ minimized.

I've computed the minimum $m$ for differnt $n$ (by computing the optimal $i$), summarized in the table below ($k \geq 0$). $$ \small{ \begin{array}{c|c|c|c|c|c|c} n & 6k & 6k + 1 & 6k + 2 & 6k + 3 & 6k + 4 & 6k + 5\\ \hline N & 18k^2 + 3k & 18k^2 + 9k + 1 & 18k^2 + 15k + 3 & 18k^2 + 21k + 6 & 18k^2 + 27k + 10 & 18k^2 + 33k + 15\\ \hline \text{optimal } m & 6k^2 + k & 6k^2 + 3k & 6k^2 + 5k + 1 & 6k^2 + 7k + 2 & 6k^2 + 9k + 3 & 6k^2 + 11k + 5 \end{array} } $$

Therefore, we have $$ \text{optimal } m = \lfloor \frac{N}{3} \rfloor $$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.