14
$\begingroup$

There are 6 water glasses as shown in the picture below:

enter image description here

You need to turn all of them upside down with the rules below:

  • You have to choose any 5 of them at every turn.
  • Chosen ones need to be turned upside down (if they are at the original position) or back to the original position (if they are already upside down).

So, at least, how many turns do you need to turn all 6 of them upside down?

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That last assertion... is not quite true. Unless you mean situations where you have n cups and turn n-1. $\endgroup$ – Sumurai8 Dec 24 '16 at 15:12
  • $\begingroup$ @Sumurai8 yeah I'm talking about examples such as these where you have to turn all the cups except one $\endgroup$ – Beastly Gerbil Dec 24 '16 at 15:13
  • $\begingroup$ The last comment, "This method works for any amount of cups, where you have to turn all of them except one", is not true. It only works for an even number of cups. $\endgroup$ – 6005 Dec 24 '16 at 15:30
  • $\begingroup$ @6005 does it? That's very interesting and now I realise I actually have only trialled that method on even numbers. I'll add that $\endgroup$ – Beastly Gerbil Dec 24 '16 at 15:40
  • $\begingroup$ @BeastlyGerbil Yes, in fact it is impossible to flip them all over if the number of cups is odd. I have added an answer with a proof. $\endgroup$ – 6005 Dec 24 '16 at 15:55
2
$\begingroup$

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.

$\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.