# Number of distinct elements between two sets

Let it be two independent sets $$A=\{a_1,a_2,...,a_n\}$$ and $$B=\{b_1,b_2,...,b_n\}$$ such that (i) $$a_i\neq b_i$$, (ii) if $$a_i=a_j$$ then $$b_i\neq b_j$$, and (iii) if $$b_i= b_j$$ then $$a_i\neq a_j$$. I am trying to find the minimum number of distinct elements between both sets $$\min(\mid A\mid+\mid B\mid)$$.

My first guess was that the restriction implies $$\min(\mid A\mid+\mid B\mid)=n+1$$; for instance, if $$a_1=a_2=\dots =a_n$$, then $$b_1\neq b_2\neq \dots \neq b_n$$, yielding this result. However, empirical results seem to point to $$\min(\mid A\mid+\mid B\mid) in some cases. For instance, if we consider the elements of set $$A$$ as all distinct pairwise sums from a set of certain positive integers, and the elements of set $$B$$ as all distinct pairwise products from that same set of certain positive integers, the sum product problem literature points to $$\min(\mid A\mid+\mid B\mid) in many cases. I would like to understand how the restrictions described allows that empirical result, if possible with an example.

• I don't understand what you are asking. Do you want to solve the problem which is stated at the beginning (how to find a formula for the minimum...) or do you simply want to prove that $\min |A|+|B| \le n$? For $n=9$ I built a very simple example which has nothing to deal with sums or whatever: $$A=(x,x,x,y,y,y,z,z,z)$$ $$B=(x,y,z,x,y,z,x,y,z)$$ here $|A|+|B|=6$ Commented Mar 2, 2022 at 12:07
• Thanks for your comment @Crostul; it has pointed out that I forgot to add the restriction $a_i\neq b_i$, which I had in mind but not wrote. Also, I edit the question to make it more concrete Commented Mar 2, 2022 at 15:25
• @JuanMoreno The restriction $a_i\neq b_i$ does not matter at all, since you can just replace everything in $B$ with a new symbol different from anything in $A$. To make the example in the previous comment work with your new restriction, just do $$A=(x,x,x,y,y,y,z,z,z)\\\\B = (p,q,r,p,q,r,p,q,r)$$ Commented Mar 2, 2022 at 16:13

Roughly, $$\min(|A|+|B|)=2\sqrt n$$.
Given two lists $$A$$ and $$B$$ satisfying your constraints, it must be true that $$|A|\cdot |B|\ge n$$ because the given restrictions imply that the ordered pairs $$(a_1,b_1),(a_2,b_2),\dots,(a_n,b_n)$$ are all distinct. Indeed, if $$(a_i,b_i)=(a_j,b_j)$$, that would contradict the condition $$a_i=a_j\implies b_i\neq b_j$$. Since there are at most $$|A|\cdot |B|$$ distinct ordered pairs, the size of the above list is at most $$|A|\cdot |B|$$.
The fact that $$|A|\cdot |B|\ge n$$ readily implies that $$|A|+|B|\ge 2\sqrt n$$: $$|A|+|B|\ge |A|+\frac{n}{|A|}=2\sqrt n+\left(\sqrt{A}-\sqrt{n\over |A|}\right)^2\ge 2\sqrt n$$ To see that this bound is achievable, given $$n$$, let $$m=\lceil \sqrt n\rceil$$, and define $$a_i=\lfloor i/m\rfloor ,\\ b_i= i\;\text{ rem }\;m$$ for each $$i\in \{1,\dots,n\}$$. Here, $$i\;\text{ rem }\;m$$ means the remainder when $$i$$ is divided by $$m$$, and is the unique element of $$\{0,1,\dots,m-1\}$$ which is congruent to $$i$$ modulo $$m$$. (This is the % operator in many programming languages).
Since the ordered pairs $$(a_i,b_i)$$ are all distinct (which is a consequence of how integer division works), this satisfies your constraints. Furthermore, there are only $$n/m\le m$$ distinct values for $$A$$ and $$m$$ distinct values for $$B$$, so $$|A|+|B|\le 2m\approx 2\sqrt n$$.