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