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

5 Answers 5

17
$\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$
0
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$
5
  • $\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, 2016 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$ Dec 24, 2016 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$ Dec 24, 2016 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$ Dec 24, 2016 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$ Dec 24, 2016 at 15:55
3
$\begingroup$

I've solved this for arbitrary values of $n$ and $N$ ($n \leq N$) where,

  • $n$ = glasses to select per move
  • $N$ = total number of glasses

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.

$\endgroup$
8
  • 1
    $\begingroup$ @FirstNameLastName I'll briefly explain my approach. Below each glass, put an odd number of dots representing the inversions it must have. Every glass will invert atleast once so the first row of dots is obvious. So, we are left with an even number of dots to work with (excluding the first row). Hence, we require N+2d total dots (d = 0, 1, 2..). Now at one step, select k dots and connect them through a line being careful not to connect any two dots in a column because a line represents one step of inverting k glasses at a time. Target forming N/k independent lines covering every dot. $\endgroup$ Mar 26 at 1:00
  • 1
    $\begingroup$ very Interesting: perhaps your generalization deserves a separate PE or ME post. Can you now elaborate what $k$ is for, e.g., $N=11$ and $n=3$ and in that particular case or for any case give strategy. $N=11$ and $n=3$ as concrete particular example. $\endgroup$ Mar 26 at 1:00
  • 1
    $\begingroup$ I'm really sorry for writing $k$ instead of $n$. In my original answer though, $k$ is the no. of steps to finally overturn every glass (with $n$ inversions per step). For $N=11$ and $n=3$, $k$ can be any from (5, 7, 9, 11, 13..) as given by the condition. When you work upon the strategy you'll find the boundary condition for k which is just that relation which I discussed. Here's my Python implementation for the same (desktop site): sololearn.com/compiler-playground/csgCLmBEcafe $\endgroup$ Mar 26 at 1:24
  • 1
    $\begingroup$ amazing!! well achieved ... now, to impress people, I need to figure out which concrete steps to take without that code to perform well. Clearly the (11,3) is a combination of (5,3) and (6,3) ... but how to mathematically build any (N,n) recursively with correct smaller solutions.? $\endgroup$ Mar 26 at 2:34
  • 2
    $\begingroup$ See this question and answer. $\endgroup$ Mar 26 at 6:26
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$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.