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



On a certain proportion concerning sets and permutations
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$.


