Skip to main content
added 17 characters in body
Source Link

It can be done in

$6$ turns, and this is the minimum possible.

In general, if there are $n$ cups, and each turn we can flip $n-1$ cups, then:

If $n$ is even, the minimum number of turns to flip them all upside-down is $n$. If $n$ is odd, it is impossible to flip them all upside-down.

  • If $n$ is even, the minimum number of turns to flip them all upside-down is $n$.
  • If $n$ is odd, it is impossible to flip them all upside-down.

Proof:

If $n$ is odd, then we start with an odd number of right-side-up cups, and since $n-1$ is even, flipping $n-1$ cups always keeps the total number that are currently right-side-up an odd number. So the number that are right-side-up can never be $0$.

If $n$ is even, we may turn them all upside-down by flipping everything but the first, then everything but the second, then everything but the third, and so on. This will be $n$ turns, since there are $n$ cups. Each individual cup is flipped on all but one of the turns -- in total $n-1$ times, an odd number. So every cup ends up upside-down.

Finally, we need to show that it can't be done in fewer than $n$ moves. Suppose we have $a_1$ turns where we flip every cup except the first, $a_2$ where we flip every cup except the second, and so on, up to $a_n$ turns where we flip every cup except the last. If $A = a_1 + a_2 + \cdots + a_n$, then in order to flip cup $i$ upside-down, $A - a_i$ must be odd for each $i$. Summing all $n$ of these odd numbers up we get $nA - A = (n-1)A$, which must be even, so $A$ is even. Thus each $a_i$ must be odd, so we must flip every cup except cup $i$ at least once. In total, at least $n$ turns.

It can be done in

$6$ turns, and this is the minimum possible.

In general, if there are $n$ cups, and each turn we can flip $n-1$ cups, then:

If $n$ is even, the minimum number of turns to flip them all upside-down is $n$. If $n$ is odd, it is impossible to flip them all upside-down.

Proof:

If $n$ is odd, then we start with an odd number of right-side-up cups, and since $n-1$ is even, flipping $n-1$ cups always keeps the total number that are currently right-side-up an odd number. So the number that are right-side-up can never be $0$.

If $n$ is even, we may turn them all upside-down by flipping everything but the first, then everything but the second, then everything but the third, and so on. This will be $n$ turns, since there are $n$ cups. Each individual cup is flipped on all but one of the turns -- in total $n-1$ times, an odd number. So every cup ends up upside-down.

Finally, we need to show that it can't be done in fewer than $n$ moves. Suppose we have $a_1$ turns where we flip every cup except the first, $a_2$ where we flip every cup except the second, and so on, up to $a_n$ turns where we flip every cup except the last. If $A = a_1 + a_2 + \cdots + a_n$, then in order to flip cup $i$ upside-down, $A - a_i$ must be odd for each $i$. Summing all $n$ of these odd numbers up we get $nA - A = (n-1)A$, which must be even, so $A$ is even. Thus each $a_i$ must be odd, so we must flip every cup except cup $i$ at least once. In total, at least $n$ turns.

It can be done in

$6$ turns, and this is the minimum possible.

In general, if there are $n$ cups, and each turn we can flip $n-1$ cups, then:

  • If $n$ is even, the minimum number of turns to flip them all upside-down is $n$.
  • If $n$ is odd, it is impossible to flip them all upside-down.

Proof:

If $n$ is odd, then we start with an odd number of right-side-up cups, and since $n-1$ is even, flipping $n-1$ cups always keeps the total number that are currently right-side-up an odd number. So the number that are right-side-up can never be $0$.

If $n$ is even, we may turn them all upside-down by flipping everything but the first, then everything but the second, then everything but the third, and so on. This will be $n$ turns, since there are $n$ cups. Each individual cup is flipped on all but one of the turns -- in total $n-1$ times, an odd number. So every cup ends up upside-down.

Finally, we need to show that it can't be done in fewer than $n$ moves. Suppose we have $a_1$ turns where we flip every cup except the first, $a_2$ where we flip every cup except the second, and so on, up to $a_n$ turns where we flip every cup except the last. If $A = a_1 + a_2 + \cdots + a_n$, then in order to flip cup $i$ upside-down, $A - a_i$ must be odd for each $i$. Summing all $n$ of these odd numbers up we get $nA - A = (n-1)A$, which must be even, so $A$ is even. Thus each $a_i$ must be odd, so we must flip every cup except cup $i$ at least once. In total, at least $n$ turns.

Source Link

It can be done in

$6$ turns, and this is the minimum possible.

In general, if there are $n$ cups, and each turn we can flip $n-1$ cups, then:

If $n$ is even, the minimum number of turns to flip them all upside-down is $n$. If $n$ is odd, it is impossible to flip them all upside-down.

Proof:

If $n$ is odd, then we start with an odd number of right-side-up cups, and since $n-1$ is even, flipping $n-1$ cups always keeps the total number that are currently right-side-up an odd number. So the number that are right-side-up can never be $0$.

If $n$ is even, we may turn them all upside-down by flipping everything but the first, then everything but the second, then everything but the third, and so on. This will be $n$ turns, since there are $n$ cups. Each individual cup is flipped on all but one of the turns -- in total $n-1$ times, an odd number. So every cup ends up upside-down.

Finally, we need to show that it can't be done in fewer than $n$ moves. Suppose we have $a_1$ turns where we flip every cup except the first, $a_2$ where we flip every cup except the second, and so on, up to $a_n$ turns where we flip every cup except the last. If $A = a_1 + a_2 + \cdots + a_n$, then in order to flip cup $i$ upside-down, $A - a_i$ must be odd for each $i$. Summing all $n$ of these odd numbers up we get $nA - A = (n-1)A$, which must be even, so $A$ is even. Thus each $a_i$ must be odd, so we must flip every cup except cup $i$ at least once. In total, at least $n$ turns.