Let $X$ be a set with $n\ge 2$ elements. Define $\mathcal{P}(X)$ to be the set of all subsets of $X$. Find the number of functions $f:\mathcal{P}(X)\mapsto \mathcal{P}(X)$ such that $$|f(A)\cap f(B)|=|A\cap B|$$whenever $A$ and $B$ are two distinct subsets of $X$. (Sergiu Novac)
Problem
Source: Science ON 2021 grade X/2
Tags: algebra, combinatorics, functional equation
08.03.2021 15:59
The answer is $n!$, i.e. the number of permutation on ${1,\dots,n}$. Note that $|f(A)|=|A|$ for all sets. Let $\sigma$ be the map given by $f(\{i\})=\{\sigma(i)\}$; $\sigma$ is well-defined as $f$ preserves the size of the set. Also, $\sigma$ is bijection as $f(\{i\}) \cap f(\{j\})$ is the empty-set for distinct $i,j$. Note that for any $A$, if $i \in A$ we have $|f(A)\cap \{\sigma(i)\}| = |A \cap \{i\}| = 1$, so $\sigma(i) \in A$. Converesely, if $i \not \in A$ we have $|f(A)\cap \{\sigma(i)\}| = 0$, so $\sigma(i) \not \in A$. Hence, $f(A)=\{\sigma(i) : i \in A\}$. In particular, any function is uniquely defined by its image on the $n$ singleton sets $\{1\}, \dots, \{n\}$, and conversely any permutation can be extended to a valid function in this way. Thus the set of such functions bijects with permutations on ${1,\dots,n}$, which completes the proof.
21.04.2022 09:15
This was also Romania NMO 2022 Grade 10 Problem 4, with the only exception that $A$ and $B$ needn't be different. This only made the problem easier, but anyhow, getting $|A|=|f(A)|$ without plugging in $A=B$ is not too hard either.