Number all the cups from 1 to $N$ in order. We will construct the strategy by induction. The case $k=1$ is obvious. Now suppose that for $k-1$ there exists a winning strategy which, on turns $i=1,2,\dots,(k-1)2^{k-2}$, chooses the cups numbered $a_i$ and $b_i$. Then for $k$, let $M_1 = 2^{k-1}$ and $M_2 = (k+1)2^{k-2}$, and consider the following strategy:

Stage 1: On turns $i = 1,2,\dots,M_1$, choose the cups numbered $i$ and $i + M_1$
(note that $i + M_1 \le 2M_1 = 2^k$);

Stage 2: On turns $i = M_1 + 1, \dots, M_2$, choose the cups numbered $a_{i-M_1}$ and $b_{i-M_1}$
(note that $i - M_1 \le M_2 - M_1 = (k-1)2^{k-2}$);

Stage 3: On turns $i = M_2 + 1, \dots, M$, choose the cups numbered $a_{i-M_2} + 2^{k-1}$ and $b_{i-M_2} + 2^{k-1}$
(note that $i - M_2 \le M - M_2 = (k-1)2^{k-2}$).

We now prove that this is indeed a winning strategy. Let $X$ denote the cups numbered 1 through $M_1$, and let $Y$ denote the cups numbered $M_1+1$ through $N$.
- First, note that only during Stage 1 can a ball in $X$ and a ball in $Y$ possibly be exchanged, and only the operation on turn $i$ can possibly move ball $i$ from $X$ to $Y$. Therefore, for every $i$ in Stage 1, we know that turn $i$ is a fake move if and only if ball number $i$ still remains in region $X$ at the end.
- Note that Stage 2 amounts to carrying out the winning strategy for $k-1$ on $X$, and we already know the full distribution of balls in region $X$ at the end of Stage 1; therefore, by the induction hypothesis, we can determine whether any given turn in Stage 2 was a fake move by observing the final distribution of balls in region $X$.
- Similarly, Stage 3 amounts to carrying out the winning strategy for $k-1$ on $Y$, and we already know the full distribution of balls in region $Y$ at the end of Stage 1; therefore, by the induction hypothesis, we can determine whether any given turn in Stage 3 was a fake move by observing the final distribution of balls in region $Y$.