Given $n$ numbers different from $0$, ($n \in \mathbb{N}$) which are arranged randomly. We do the following operation: Choose some consecutive numbers in the given order and change their sign (i.e. $x \rightarrow -x$). What is the minimum number of operations needed, in order to make all the numbers positive for any given initial configuration of the $n$ numbers?
Problem
Source:
Tags: combinatorics
12.05.2017 13:32
Duarti wrote: Given $n$ numbers different from $0$, ($n \in \mathbb{N}$) Do you mean $n \in \mathbb{Z}$? Otherwise, they are all trivially positive.
12.05.2017 16:53
Quote: Given $n$ numbers different from $0$, ($n \in \mathbb{N}$) which are arranged randomly. We do the following operation: Choose some consecutive numbers in the given order and change their sign (i.e. $x \rightarrow -x$). What is the minimum number of operations needed, in order to make all the numbers positive for any given initial configuration of the $n$ numbers? Here is my solution. I'm not sure that I understood the question correctly, so here I took 'consecutive numbers' to be numbers lined up in the sequence, but not necessarily in numerical order. First of all, let's consider any individual integer to be a $+$ or a $-$ (positive or negative). That is, we will only consider its sign, and not its value. This is allowed, since all that matters is the sign of the numbers. 1st assertion: Define a 'block' to be a series of consecutive numbers with the same sign, so that bordering this series is either a number of opposite sign, or nothing (in this case, the 'block' is on the edge of the configuration). Consider the following way of doing things: for any given 'block', we always change the sign of its members the same way. If we do not do like this for a given operation, the number of 'blocks' will either stay the same of grow greater. Proof: Consider two consecutive blocks, like in this situation: $...+---------++++++++++-...$ (the number of $+$s and $-$s is arbitrary, this is just a representation). If we do not do like the operation defined above, we will end up in a situation like $...+---+++++++++++++++-...$ (the number of blocks stays the same) or $...+------+++++------++++++-...$ (the number of 'blocks' gets greater). The principle stays the same if we have several entire blocks that are changed at the same time. It is obvious that if the number of distinct 'blocks' does not diminish (we will consider that it starts greater than 1), we will never get to the desired situation. We now know that the only way to diminish this number is to perform the operation defined in the first assertion. 2nd assertion: Let $B$ be the number of distinct blocks. It is always possible to decrease $B$ of $2$ during one operation, and it is not possible to decrease $B$ of more than $2$ during one operation. Proof: Consider the blocks as $(+)$ and $(-)$. If $B>2$, it is easy to see that there exists the situation $(+)(-)(+)$ (or with the signs inverted). If $B=2$, it is easy to see that we are almost finished. By changing the block $(-)$, we arrive at $(+)(+)(+)$, and $B$ decreased by $2$. Now we come to the second part of the assertion. Consider a situation where we have a series of consecutive blocks and we change all of them at the same time. Within the series, the borders between the blocks stay the same. On each edge of the series, it is possible that the block on the edge group with a block on the outside of the series. In that case, $B$ does not decrease of more than $2$. It is also clear that changing a block on the edge decreases $B$ of $1$. So we have shown that by always changing whole blocks, $B$ can be decreased of $2$ at a time, and not more at a time. We want to arrive at $B=1$ in the fewest moves possible, so we will only change whole blocks at a time (changing several whole blocks at a time is also possible). We saw that changing a block on the edge decreases $B$ of only $1$ at a time. Now we are going to consider situations where the number of blocks is maximal, since it will be in these situations that the minimum number of operations needed is also maximal. This means that $B=n$. Let's consider the situation when $B=n$ is even. Then we have the situation $+-+...+-$, with $n/2$ blocks $(+)$ and $n/2$ blocks $(-)$. Here, in the starting position, each number is a separate block. As seen before, in minimum $n/2 - 1$ moves, $B$ will be equal to $2$ and this is possible. Which means that for $n$ even, the minimum number of moves needed is $n/2$. Now, let's consider $n$ odd. Using the same arguments as before, it will take $[n/2]$ ([.] representing the integer part) moves to get to $B=1$. But we also need all the numbers to be positive. If the beginning position has minuses on the edges, after $[n/2]$ moves, all the signs will be negative since changing a number on the edge would mean that $B$ decreases of only $1$ at a time, but we decreased of $2$ at a time at every move. So we will have to do another move so that all the numbers are positive. It is easy to see that if we had first changed the sign of the negative numbers on the edges, we would have done $2$ moves, and we would be at $B = n-2$, needing another $[n/2] -1$ moves, and we arrive at the same conclusion. So finally, the answer is: $n/2$ if $n$ is even; $[n/2] + 1$ if $n$ is odd.