I just realized this is wrong, because the counter, A, could be faced with 6 down chalices which he flips up and C could not have even entered the room (given N =3 and K =2):

A enters, chalice down, flips up (1).
King enters, flips down (1).
A enters, flips up (2).
King enters, flips down (2).
A enters, flips up (3).
B enters, flips down (1).
A enters, flips up (4).
B enters, flips down (2).
A enters, flips up (5).
B enters, flips down (3).
A enters, flips up (6).


This leaves me with a problem.... If the counter toggles the cup 7 times -- generally NK - K + N times -- he can confidently say that all the prisoners have visited the room. However, sometimes the chalice will only be toggled by the counter (N-2)(K+1)+1 times, or with K=2 and N=3 4 times:

B flips down (1)
K flips up (1)
B flips down (2)
K flips up (2)
B flips down (3)
A flips up (1)
C flips down(1)
A flips up (2)
C flips down (2)
A flips up (3)
C flips down (3)
A flips up (4)

So, if the counter flips the chalice up NK - 2K +N +1 times, and the chalice never moves again, can he ever be sure? This is an interesting problem....