5
$\begingroup$

I'm asking for a generalisation of this question.

There is an $m$ sided board with $m$ cups. Some of the glasses are facing upwards and some upside-down. Your goal is to arrange the glasses so that they are all facing up or all facing down.

On each turn, you can check any $n$ cups. You are allowed to turn up to $k$ of them. After each turn, the board rotates randomly.

Here, $m\geq n\geq k$

Give an algorithm or a formula, if possible, that tells the minimum turns required.

P.S. Maybe start-off with $n=k$.

$\endgroup$
  • 2
    $\begingroup$ You can't have a guaranteed minimum if the board rotates randomly. Maybe it gives you the same $n$ cups every time while all the others are a random mix of face up / face down. $\endgroup$ – Joe Z. Sep 3 '15 at 15:00
  • 1
    $\begingroup$ @JoeZ. What ghosts_in_the_code seems to have not mentioned is that (if we assume the original problem statement) you can "feel" any n cups and flip any k of them. Not only those in front of you. $\endgroup$ – dmg Sep 3 '15 at 15:31
  • 1
    $\begingroup$ There is no need to include the trivial $m = n$ case. Anyhow, the question seems too broad. I can see many odd $m$ cases not working, since we no longer have the diagonal symmetry to exploit. For example, for $m = 5$, even with full knowledge of what the full table configuration is, if the table rotates randomly after each turn, none of the 3 cases ($\bullet\circ\circ\circ\circ$, $\bullet\bullet\circ\circ\circ$ or $\bullet\circ\bullet\circ\circ$) can be solved with any $n < m$. $\endgroup$ – Hackiisan Sep 3 '15 at 20:51
  • 1
    $\begingroup$ @Samthere It's just like the other question. It rotates a random angle between 0 and 360. $\endgroup$ – ghosts_in_the_code Sep 4 '15 at 10:07
  • 1
    $\begingroup$ This generalization is solved by Laaser and Ramshaw in Probing the Rotating Table. I do not have access to the article, but the lower bound of $k\ge(1-1/p)n$ where $p$ is the greatest prime factor of $n$ can be easily shown by applying the same argument when there are $p$ cups in total to $n/p$ groups of cups. $\endgroup$ – noedne Mar 7 at 4:02
3
$\begingroup$

Observations:

  1. For $m=2r\ (r>1, r \in N)$ and $n=k=m-2$, the solution can be achieved in 5 moves or less.

    If $m=4$, see the original cup problem. Now, suppose, $m\ge6$

    • First feel a row of $m-2$ cups and flip all of them down. If the bell doesn't ring, we have $m-2$ consecutive down cups and two unknown cups.

    • Then feel a one offset (row of $m-3$ cups (chain) and one disconnected cup) of cups and flip them all down. If the bell doesn't ring, we have only a single up cup.

    • Again feel a one offset.

      • If you feel an up cup, flip it and we are done.
      • Else, flip the second cup of the chain. Now we have, exactly two cup with $1$ or $3$ cups between them
    • We feel a row of $m-2$ cups

      • If you feel 2 up cups, flip them and we are done.
      • Else, We can feel exactly one up cup. We flip every other cup starting from the up cup. This creates a alternating up-down pattern.
    • Finally, we feel a alternating pattern ($r$ cups none of which are consecutive) and flip all of them.

    For a specific example ($m=6$, $n=k=4$) see below.
    Note: It might be possible to finish in less than 5 moves.

  2. If $n=k < (m/2)$ it will always be impossible. (Thanks to f")

    This is because if $n=k < (m/2)$ any pattern you choose will always have two adjacent, unchosen cups. If, in the original state of the table, there are two adjacent cups that are different, the table can rotate so that you never choose those two cups. Thus making it impossible to guarantee a solution.

  3. If m is prime, $n=k ≤ (m−2)$ is impossible. (Thanks to Tyler Seacrest )

    To show this, suppose the two cups you choose not to feel are $i$ distance apart. Regardless of the initial state of the table, there must be two cups $i$ distance apart that are in different states (as long as the initial table is not solved). Hence the two cups you don't feel might always be in different states, making a sure win impossible.

Summary of results

TestNote: Due to item 2 above, all values of n=k < m/2 are omitted
Key: ? = Not yet proven if solution exists or not
     X = Not possible

m   n=k   moves
3    3      1   
3    2      2

4    4      1
4    3      2
4    2      5  (see solution to original cup problem)

5    5      1
5    4      2
5    3      X  (see item 3 above)

6    6      1
6    5      2
6    4      5  (see proof below)
6    3      ?  

7    7      1
7    6      2
7    5      X  (see item 3 above)
7    4      X  (see item 3 above)

8    8      1
8    7      2
8    6      5
8    5      ?
8    4      ?

If anybody notices an error in the information above please let me know. Also if anybody can prove solutions for any of the question marks, or even for higher m values, those solutions might help us notice a pattern.


Proof of $m=6,\ n=k=4$

Note: this method can also be used to solve $m=8,\ n=k=6$

m=6 n=k=4


I have a strong hunch that $m=6,\ n=k=3$ is impossible, but can't prove it.


Proof for $m = s^2$, $n = k = m - s$. (five moves max)

I hope you can follow this despite not being as clear as Dsel's images. In a way it is very similar to the $m = 6$, $n = k = 4$ case above. A "clump" is when you feel all cups except $s$ consecutive cups. A "spread" is when you feel all cups except $s$ cups evenly spread around the table (i.e. you don't feel every $s$th cup).

  • Feel a clump and turn them all down.

  • Feel a spread and turn them all down. At this point, at most one cup is up or we hear a bell.

  • Feel a spread. If we feel the one up cup, then bell time. Otherwise, turn them all up. We know have $s - 1$ down cups spread out so that there is a down cup every $s$th cup all the way around the table, except one up cup. All other cups are up as well.

  • Feel a clump. If there are $s-1$ down cups, turn them all up and hear a bell. If there are $s-2$ down clumps: group the cups into $s$ groups, where each group consists of $s$ consecutive cups, and one of the groups is all the cups you are not currently feeling. Then all the groups have exactly one down cup in exactly the same spot, except one group which has all up cups. Mimic the rest of the groups by turning one of cups down in the appropriate spot.

  • Feel a spread. From the last step, we know that all cups are up except $s$ cups are down, one down cup every $s$ cups. By feeling a spread, we can see all the down cups or none of them. If we see all the down cups, turn them up and hear a bell. If we see none of the down cups, then turn all the cups down and hear a bell.

$\endgroup$
  • 1
    $\begingroup$ If (n=k)<(m/2), then whatever pattern you choose will always have two unchosen cups next to each other. If there are two adjacent cups that are different, then the table can rotate so that you never choose those two cups, making it impossible. $\endgroup$ – f'' Sep 4 '15 at 19:18
  • $\begingroup$ If $m$ is prime, then $n = k \leq m-2$ is impossible. Suppose the two you choose not to feel were $i$ distance apart. There must be two cups $i$ apart in different states ($m$ being prime and not all the cups are in the same state). Hence the two cups you don't feel might be in different states, making a sure win impossible. $\endgroup$ – Tyler Seacrest Sep 4 '15 at 22:00
  • $\begingroup$ @f'' Great point, I like how succinct that proof is. Ill add it to this answer but you definitely deserve rep for it so feel free to post it as your own answer as well $\endgroup$ – Dsel Sep 4 '15 at 22:29
  • $\begingroup$ @TylerSeacrest At first I agreed with you, but I believe I have a solution for m=7, n=k=5. ill post it soon $\endgroup$ – Dsel Sep 4 '15 at 22:46
  • $\begingroup$ I'm not sure you're allowed to feel cups one at a time. If it isn't allowed, @TylerSeacrest is right. $\endgroup$ – f'' Sep 5 '15 at 0:26

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.