There are 6 water glasses as shown in the picture below:
You need to turn all of them upside down with the rules below:
So, at least, how many turns do you need to turn all 6 of them upside down?
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 takes
6 goes
Here's a diagram, U being up ad D being down
1. U U U U U U - Start
2. U D D D D D - Choose 2, 3, 4, 5 and 6
3. D D U U U U - Choose 1, 3, 4, 5 and 6
4. U U U D D D - Choose 1, 2, 4, 5 and 6
5. D D D D U U - Choose 1, 2, 3, 5 and 6
6. U U U U U D - Choose 1, 2, 3, 4 and 6
7. D D D D D D - Choose 1, 2, 3, 4 and 5
It's actually quite a simple method:
You turn every cup except the first over. Then you turn them all except the second over, then the third, fourth etc.
This method works for any even amount of cups, where you have to turn all of them except one. This is also why the amount of turns will be the same as the amount of cups, because as you can see above, each cup will be left alone once before getting the result.
n cups and turn n-1.
$\endgroup$
I've solved this for arbitrary values of $n$ and $N$ ($n \leq N$) where,
My method showed no solution is possible when $n$ is even and $N$ is odd, because $n*k - N$ $(=p)$ must be even ($k$ is a positive integer). The minimum number of moves required is the smallest $k$ satisfying the following condition:
$$k \geq 1 + \left( \lfloor \frac{p}{2N} \rfloor + bool(mod(p,2N))\right) \cdot 2$$
$k$ is guaranteed to be in the range $[\lceil N/n \rceil, N]$. You can check for the smallest $k$ in this range that satisfies the relation.
To turn all of them upside down, you have to choose all of them an odd number of times. For convenience's sake, bar the player from choosing the same 5 glasses (hence, excluding one) more than once.
Let's indicate the glasses facing up with u and the ones upside down with d.
1. Starting configuration is uuuuuu. Since the state of all the glasses are the same, it doesn't matter which 5 are chosen. We can exclude the last and get dddddu.
2. Only one of the glasses upside down can be excluded now. It doesn't make a difference which one is, so we can just choose all of them bar the 5th, getting uuuudd.
3. Only one of the glasses facing up can be excluded now. It doesn't make a difference which one is, so we can just choose all of them bar the 4th, getting ddduuu.
4. Only one of the glasses upside down can be excluded now. It doesn't make a difference which one is, so we can just choose all of them bar the 3rd, getting uudddd.
5. Only one of the glasses facing up can be excluded now. It doesn't make a difference which one is, so we can just choose all of them bar the 2nd, getting duuuuu.
6. Now just choose the last 5 and it's done in 6 steps.
With induction, we can see that if we've gone right to left while excluding glasses, with every glass to the left of the excluded one being of the same state, and that of the others being the opposite so far, we can just keep the pattern.
Another solution:
Clearly, it can be done by excluding different glasses in 6 moves. That there's no better solution can be proven: since each glass must be chosen an odd number of times but there are 6 glasses, it takes an even $x$ number of turns (2 or 4 if it's better than 6). If x is even, a glass can't be chosen more times than x, and it can't be chosen x times either, so it can be chosen $x-1$ times at most. For $x<6$, even the maximum number of choices, $(x-1)6$, is less than $5x$. That means there's no better solution.
A mathier method than the others for reaching the same answer:
The orientations of the six glasses correspond to the basis elements $e_1, ..., e_6$ of the vector field of dimension six over the binary field $\mathbb{F}_2$, and this question asks for a linear combination $\sum c_i v_i = \sum e_i$, where $v_i = \sum_{j \neq i} e_i$ is the operation corresponding to flipping every glass but the $i^{\text{th}}$, and $c_i$ represents whether or not we performed this operation ($c_i = 1$ if we did, $0$ otherwise). Seeing as the $v_i$ are linearly independent (to see this, one can verify that the $6 \times 6$ determinant is nonzero, by rote or by argument), the only possible solution is $c_i = 1$ for all $i$, that is, it will require six moves and no less.
