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

Improve this question
$\endgroup$
13
  • 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$
    – user88
    Sep 3, 2015 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, 2015 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, 2015 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, 2015 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, 2019 at 4:02

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
12
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 0:26

Your Answer

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

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