On a certain proportion concerning sets and permutations Let $X$ be a finite set and let $f$ and $g$ be permutations with $f\ne g\ne f^{-1}$.
Can you show that the proportion of subsets $S$ with $|S\cap f(S)|=|S\cap g(S) |$ is at most $3/4$?
In other words
$$\frac{|\{S\subseteq X\mid|S\cap f(S)|=|S\cap g(S) | \} |}{|\{S\subseteq X\}|}\leq\frac{3}{4} \cdot 2^{|X|}$$
 A: True, of course (except the correct exception was given by Robert Israel, not by the OP), but nearly trivial. 
Let us consider all vectors $\delta=(\delta_1,\dots,\delta_n)$ consisting of $0$ and $1$. The question is just how often it can happen that $F(\delta)=\langle\delta,A\delta\rangle=0$ where the matrix $A=P-Q$ is the difference of the permutation matrices corresponding to $f$ and $g$. The claim is that either $A$ is antisymmetric, in which case the scalar product is always $0$, or $F(\delta)$ does not vanish for at least $1/4$ of possible choices of $\delta$. Indeed, if $a=A_{ij}+A_{ji}\ne 0$ for some $i\ne j$, then with all $\delta_k,k\ne i,j$ fixed, we can treat the scalar product as a function $F'(\delta_i,\delta_j)$ and write
$$
F'(1,1)+F'(0,0)-F'(1,0)-F'(0,1)=a\ne 0
$$ 
so at least one of $4$ choices should produce a non-zero value.
If $A_{ij}+A_{ji}=0$ for all $i\ne j$, then $F(\delta)=\sum_i A_{ii}\delta_i$, so if some $A_{ii}\ne 0$, we can do the same trick fixing all $\delta_k, k\ne i$ and see that one of every two choices of $\delta_i$ should produce a non-zero value.
Thus, the exceptions are exactly the permutations for which $P-Q$ is antisymmetric. Now let $I$ be the set of rows of $P-Q$ that vanish identically and let $J$ be the set of columns corresponding to these rows in each of the permutations $P$ and $Q$. Then $P-Q$ has non-zero rows $I^c$ but the non-zero columns can be only $J^c$, so, by the antysimmetry, $I^c=J^c$ and $I=J$. Thus, we found a common invariant set $I$ for $f$ and $g$ on which $f=g$ and its complement is also invariant. Moreover, if we forget about $I$, then $P$ consists of $1$'s and $-Q$ of $-1$'s, so $P-Q$ can be antisymmetric only if $Q=P^T$, i.e., if $g=f^{-1}$ on $I^c$.
A: Not true.  Try $f = (1,2,3)(4,5,6)$ and $g = (1,2,3)(4,6,5)$. Then $|S \cap f(S)| = |S \cap g(S)|$ for all subsets of $\{1,\ldots,6\}$.
