Say a set $X \subseteq \{1,\ldots,n\}$ is alternating if successive elements of $X$ are of opposite parity. That is to say for any $x \in X$, if $y = \min \{z \in X \mid x < z\}$ then $x \not\equiv y \pmod 2$.
For a permutation $\pi \in S_n$, say that a set $X \subseteq \{1,\ldots,n\}$ is good for $\pi$ if $X$ is alternating and $\pi(X)$ is alternating.
What I would like to prove is that for a randomly chosen permutation $\pi$ (say, under the uniform distribution), the number of good sets is just as likely to be odd as even. Any pointers on relevant results or methods would be much appreciated.
Actually, for my application, I only need that the number of good sets is odd with probability bounded away from $0$ as $n$ grows. It doesn't have to be $1/2$, but my guess is that this is indeed the case.
