patternMinor
On a table there are $N$ stacks. Stack $i$ contains $i$ tokens. Minimum number of moves to make all stacks empty
Viewed 0 times
numbermovesstackallaremakeminimumemptystackscontains
Problem
On a table there are $n$ stacks (numbered $1$ to $n$). Stack $i$ contains $i$ tokens ($1 \leq i \leq n$). During a move, a set of stacks can be chosen and the same number of chips can be drawn from each stack that is part of the chosen set. What is the minimum number of moves to make all stacks empty?
For example if $n=3$, the answer is $2$. On the first move, you can choose stacks $2$ and $3$ and remove $2$ chips from them and in the second move you can choose stacks $1$ and $3$ and remove one chip from them.
My approach would be to split the stacks in half, and removing $n/2$ tokens from the second half. Now, the problem size is reduced in half and we can solve it recursively.
I don't know if this approach results in the minimum number of moves or if it does how to prove it.
For example if $n=3$, the answer is $2$. On the first move, you can choose stacks $2$ and $3$ and remove $2$ chips from them and in the second move you can choose stacks $1$ and $3$ and remove one chip from them.
My approach would be to split the stacks in half, and removing $n/2$ tokens from the second half. Now, the problem size is reduced in half and we can solve it recursively.
I don't know if this approach results in the minimum number of moves or if it does how to prove it.
Solution
Let $k$ be the smallest integer such that $2^k > n$.
Any solution must use at least $k$ moves
Suppose towards a contradiction that there exists a winning strategy using at most $k-1$ moves $m_1, m_2, \dots$.
Label each stack $i$ with the set $M(i)$ of moves $m_j$ that involve $i$ and notice that no label can be empty.
Since the number of possible labels (i.e., the number of possible non-empty sets of moves) is at most $2^{k-1} - 1 \le n - 1$, there must be at least two distinct stacks $i,j$ such that $M(i) = M(j)$.
This means that the winning strategy removes the same number of tokens from $i$ and $j$, which is a contradiction.
The divide and-conquer algorithm uses exactly $k$ moves
Consider now the following recursive algorithm (which is probably the one you are describing in your question):
-
If $k=1$ (i.e., $n=1$), let $m$ be the move that removes the only remaining token from the only existing stack and return $\{m\}$.
-
Split the stacks into two sets $S_1 = \{1, \dots, 2^{k-1} - 1\}$, $S_2 = \{ 2^{k-1}, \dots, n\}$.
-
Consider the move $m$ that removes $2^{k-1}$ tokens from each stack in $S_2$. After $m$, one stack in $S_2$ is empty and the other $r = n - 2^{k-1}
-
Call the algorithm recursively on $S_1$, to obtain a set $M = \{m_1, m_2, \dots\}$ of moves that makes $S_1$ empty.
-
Construct a modified set of moves $M'$ that contains all moves $m_i$ from $M$, with the exception that whenever a move $m_i$ removes some number $x$ of tokes from the $i$-th stack (which is in $S_1$), we also remove $x$ tokens from the $(2^{k-1}+i)$-th stack (i.e., from the $(i+1)$-th stack in $S_2$), if it exists. Notice that this does not increase the number of moves.
-
Return $\{m\} \cup M'$.
Each invocation of the above algorithm increases the number of moves by $1$, therefore the overall number of moves is equal to the maximum number of recursive calls. Since each invocation decreases the value of $k$ by $1$ and the base case corresponds to $k=1$, we can conclude that the algorithm returns a sequence with exactly $k$ moves.
Any solution must use at least $k$ moves
Suppose towards a contradiction that there exists a winning strategy using at most $k-1$ moves $m_1, m_2, \dots$.
Label each stack $i$ with the set $M(i)$ of moves $m_j$ that involve $i$ and notice that no label can be empty.
Since the number of possible labels (i.e., the number of possible non-empty sets of moves) is at most $2^{k-1} - 1 \le n - 1$, there must be at least two distinct stacks $i,j$ such that $M(i) = M(j)$.
This means that the winning strategy removes the same number of tokens from $i$ and $j$, which is a contradiction.
The divide and-conquer algorithm uses exactly $k$ moves
Consider now the following recursive algorithm (which is probably the one you are describing in your question):
-
If $k=1$ (i.e., $n=1$), let $m$ be the move that removes the only remaining token from the only existing stack and return $\{m\}$.
-
Split the stacks into two sets $S_1 = \{1, \dots, 2^{k-1} - 1\}$, $S_2 = \{ 2^{k-1}, \dots, n\}$.
-
Consider the move $m$ that removes $2^{k-1}$ tokens from each stack in $S_2$. After $m$, one stack in $S_2$ is empty and the other $r = n - 2^{k-1}
-
Call the algorithm recursively on $S_1$, to obtain a set $M = \{m_1, m_2, \dots\}$ of moves that makes $S_1$ empty.
-
Construct a modified set of moves $M'$ that contains all moves $m_i$ from $M$, with the exception that whenever a move $m_i$ removes some number $x$ of tokes from the $i$-th stack (which is in $S_1$), we also remove $x$ tokens from the $(2^{k-1}+i)$-th stack (i.e., from the $(i+1)$-th stack in $S_2$), if it exists. Notice that this does not increase the number of moves.
-
Return $\{m\} \cup M'$.
Each invocation of the above algorithm increases the number of moves by $1$, therefore the overall number of moves is equal to the maximum number of recursive calls. Since each invocation decreases the value of $k$ by $1$ and the base case corresponds to $k=1$, we can conclude that the algorithm returns a sequence with exactly $k$ moves.
Context
StackExchange Computer Science Q#162707, answer score: 3
Revisions (0)
No revisions yet.