5

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

Community
  • 1
ghosts_in_the_code
  • 7,024
  • 1
  • 30
  • 100
  • 2
    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. –  Sep 03 '15 at 15:00
  • 1
    @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. – dmg Sep 03 '15 at 15:31
  • I believe a 3 sided table is impossible to solve unless you are allowed to feel all three cups. This is because you don't have the benefit of diagonals on a three sides table. – Dsel Sep 03 '15 at 16:11
  • @Dsel a 3 sided table can always be solved in 2 turns feeling only 2 cups. – Lampost42 Sep 03 '15 at 16:30
  • @Lampost42 you are absolutely correct. My mistake – Dsel Sep 03 '15 at 16:32
  • @dmg Okay, that makes sense. –  Sep 03 '15 at 18:22
  • 1
    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$. – Hackiisan Sep 03 '15 at 20:51
  • @Hackiisan for m = 5 it can always be solved in 2 turns if n = 4. You turn the 4 you check so they match on turn 1. Then if you haven't won, on turn 2 you will either find 1 cup different than the 3 others you feel, in which case flipping it means you've won, or all 4 will be the same and you will win by flipping them all. – Lampost42 Sep 03 '15 at 22:33
  • In fact for all $m$, if $n=k$ and and $n=m-1$ then it is solvable in 2 turns. – Lampost42 Sep 03 '15 at 22:41
  • I don't know why, but at the time of my previous comment I interpreted the question as forcing you to overturn exactly $k$ cups (where $k \leq n$ is a constant), which is absurd. You are of course correct. – Hackiisan Sep 03 '15 at 22:58
  • When you say the board rotates randomly do you mean: (1) The board rotates 1 side in a random direction? Or (2) The board rotates a random amount so you never have any information about which side is towards you? – Samthere Sep 04 '15 at 09:05
  • 1
    @Samthere It's just like the other question. It rotates a random angle between 0 and 360. – ghosts_in_the_code Sep 04 '15 at 10:07
  • 1
    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. – noedne Mar 07 '19 at 04:02

1 Answers1

3

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.

Tyler Seacrest
  • 9,174
  • 2
  • 28
  • 62
Dsel
  • 341
  • 2
  • 13
  • 1
    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. – f'' Sep 04 '15 at 19:18
  • 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. – Tyler Seacrest Sep 04 '15 at 22:00
  • @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 – Dsel Sep 04 '15 at 22:29
  • @TylerSeacrest At first I agreed with you, but I believe I have a solution for m=7, n=k=5. ill post it soon – Dsel Sep 04 '15 at 22:46
  • I'm not sure you're allowed to feel cups one at a time. If it isn't allowed, @TylerSeacrest is right. – f'' Sep 05 '15 at 00:26
  • @f'' Very true... Its probably up to us if thats allowed or not. What do you all think, fair game or not? – Dsel Sep 05 '15 at 00:29
  • I think it shouldn't be allowed. – f'' Sep 05 '15 at 01:22
  • @Dsel: I don't know if that feeling one at a time thing should be allowed or not, but I think that needs to be decided. Very clever solution to the m = 7, n = k = 5 case regardless! – Tyler Seacrest Sep 05 '15 at 02:48
  • @TylerSeacrest Thanks! But I thought about it more, I think I agree with f'' so I'm gonna take that solution down and lets say feeling one at a time is not allowed from here on out. – Dsel Sep 05 '15 at 05:09
  • @TylerSeacrest I added your theorem. Hopefully I did it justice, but if not please edit it. I also decided to make this a community wiki since 2/3 of the stuff up there is no longer my own work. Thanks for the help! – Dsel Sep 05 '15 at 05:31
  • @dsel, I have updated the proof of hypothesis 1. It might be helpful to have one of your diagrams. – Rohcana Sep 05 '15 at 12:50
  • @Dsel: Thanks, looks good. I added the case where $m$ is a perfect square and $n = k = m - \sqrt{m}$. I hope what I have makes sense and is correct. – Tyler Seacrest Sep 06 '15 at 05:37