Let $|A| = N$ (your $4n$). As Fedja observes, the easy lower bound is $\binom{N}{4}/\binom{N/2}{2} \approx N^2/3$, since there are $\binom{N}{4}$ quadruples and each pairing covers $\binom{N/2}{2}$ of them. Fedja gives you a solution that achieves $\approx N^2$. I will do a bit better and get $\approx N^2/2$.

I will explain my solution in the case that $N = p+1$ for $p$ prime; more generally, choose $p$ a little above $N$, use my solution for $p+1$ points, and whenever my solution tells you to pair something in $[1,N]$ with something in $[N+1, p+1]$, choose some arbitrary alternate pairing instead.

First, I'll present Fedja's solution in a more sophisticated way. There are $p^2-p$ involutions in the group $\text{PGL}_2(\mathbb{F}_p)$. In terms of matrices, we are looking at matrices $\left[ \begin{smallmatrix} a&b \\ c&-a \end{smallmatrix} \right]$ where the determinant $a^2+bc$ is nonzero. These involutions act on the projective line $\mathbb{P}^1(\mathbb{F}_p)$ by Mobius transformations: $z \mapsto \tfrac{az+b}{cz-a}$.

For any $4$ distinct elements $(u,v,w,x)$ in $\mathbb{P}^1(\mathbb{F}_p)$, there is an involution with $\text{PGL}_2(\mathbb{F}_p)$ which acts by $u \leftrightarrow v$, $w \leftrightarrow x$. Fedja takes the pairings given by the action of these involution. (I suppose, if he were being careful, he should note that many of these involutions have two fixed points; if so, pair off the fixed points and the solution still works.)

So, I'll do a little better. There are two conjugacy classes of involutions: Those whose determinant is square, and those where the determinant is not square. Each conjugacy class contains $p(p-1)/2$ elements. The upshot of this argument will be that just using the conjugacy class with square determinant is enough, saving a factor of $2$ over Fedja.

For any ordered quadruple $(u,v,w,x)$, let $\rho$, $\sigma$ and $\tau$ be the involutions switching the three pairings of this quadruple. Then $\rho \sigma \tau$ fixes $(u,v,w,x)$, so it is $c \text{Id}$ for some scalar $c$, and
$$\det(\rho) \det(\sigma) \det(\tau) = c^2.$$
Thus, an odd number of these involutions have square determinant. This, just using the conjugacy class with square determinant is enough.

"Since we have naturally divided the pairings into 3 types"Well, only for a set of 4 elements. How would you extend this partition for larger sets? $\endgroup$6more comments