March 18th
Today I learned a cute combinatorial proof from the AIME II. Here's the main statement.
Proposition. Fix finite sets $A$ and $B.$ If $|A|\cdot|B|=|A\cap B|\cdot|A\cup B|,$ then either $A\subseteq B$ or $B\subseteq A.$
Finiteness gives us a pretty clear way in. For brevity, let $a=|A|,$ $b=|B|,$ and $x=|A\cap B|,$ and we can see that $|A\cup B|=a+b-x$ by the Principle of inclusion-exclusion. Plugging in, we see\[ab=x(a+b-x),\]which rearranges to\[0=ab-ax-bx+x^2=(a-x)(b-x).\]It follows that one of $a=x$ or $b=x.$ Because $A\cap B\subseteq A,B$ already, having $|A\cap B|=|A|$ or $|A\cap B|=|B|$ immediately requires $A\cap B=A$ or $A\cap B=B,$ which means $A\subseteq B$ or $B\subseteq A.$ This is what we wanted. $\blacksquare$
Of course, if one expects the statement to be true a priori (which I did not while taking the AIME), a faster way to do this is by saying the unordered pairs\[\{|A|,|B|\}\quad\text{and}\quad\{|A\cap B|,|A\cup B|\}\]have equal sum (by PIE) and equal product (by hypothesis). So by Vieta's (i.e., build the quadratic), our pairs must be equal, and we finish by casework on how the unordered pairs are equal. I believe this is the intended solution.
It's worth mentioning that finiteness is actually crucial to the proposition. That is, we have\[|A\times B|=|(A\cap B)\times(A\cup B)|\]does not in general imply that $A\subseteq B$ or $B\subseteq A.$ This is perhaps unsurprising; we might feel like $(A\cap B)\times(A\cup B)$ to be smaller than $A\times B$ (by an AM-GM argument, say), but $2\ZZ$ feels smaller than $\ZZ$ in a similar way when in fact they have the same size.
To make an explicit counterexample, we take\[A=\left\{n^2:n\in\ZZ\right\}\quad\text{and}\quad B=\left\{n^3:n\in\ZZ\right\}.\]Note $A$ and $B$ are both countable, so $A\cup B$ is countable. Further, $A\cap B=\left\{n^6:n\in\ZZ\right\}$ is also countable. So, bijecting everything to $\NN,$ we see\[|A\times B|=|\NN\times\NN|=|(A\cap B)\times(A\cup B)|.\]However, $4\in A\setminus B$ and $8\in B\setminus A,$ so we see $A\not\subseteq B$ and $B\not\subseteq A.$
As an addendum, we remark that the AIME question actually asked to count the number of $A,B\subseteq S:=\{1,2,3,4,5\}$ satisfying. This is not hard to do either, again by a clean combinatorial argument. Without loss of generality, we will count $A\subseteq B,$ and PIE will let us count $(A,B)$ with $A\subseteq B$ or $B\subseteq A.$ Now, an element $k\in S$ has three options.
-
$k$ belongs to neither $A$ nor $B.$
-
$k$ belongs to $B$ but not $A.$
-
$k$ belongs to both $A$ and $B.$
Thus, each element of $S$ has three options, so there are $3^{|S|}$ total pairs $(A,B)$ with $A\subseteq B.$ More generally, we can say that\[\left\{(A,B)\in\mathcal P(S)^2:A\subseteq B\right\}\longleftrightarrow(S\to\{1_\emp,1_B,1_A\}),\]for any $S,$ with the same argument.