Find the maximum number of pairwise disjoint sets of the form \[S_{a,b}=\{n^{2}+an+b \; \vert \; n \in \mathbb{Z}\},\] with $a,b \in \mathbb{Z}$.
Problem
Source:
Tags:
05.10.2007 19:43
Firstly we show that if for some numbers $ a,b,c,d$, $ a-c$ is odd then $ S_{a,b}\cap S_{c,d}\neq\emptyset$. WLOG, let $ a$ be even and $ c$ odd. We're looking for solutions for $ n^2+na+b=m^2+cm+d$, or $ (2n+a)^2+4b-a^2=(2m+c)^2+4d-c^2$, or $ (2m+c+2n+a)(2m+c-2n-a)=4(b-d)+c^2-a^2=4k+1$, for some $ k$. Trying $ 2m+c-2n-a=1$ and $ 2m+c+2n+a=4k+1$, we add and get $ 4m+2c=4k+2$, from where $ m=k+\dfrac{1-c}2\in\mathbb{Z}$. We also get $ n=k-\dfrac a2\in\mathbb{Z}$. So if several such disjoint sets exist, all must have the $ a$'s of the same parity. Suppose they're all odd. Then it's easy to see that $ (2n+a)^2+L=(2m+c)^2$ is solvable iff $ L=8k$. Since in our case $ L=4(b-d)+c^2-a^2$, and $ c^2-a^2$ is divisible by $ 8$, we need $ b-d$ to be even. This shows there do not exist $ 3$ pairwise disjoint sets as required, having all $ a$'s odd. But $ 2$ do exist and their $ b$'s are of different parity. Suppose they're all even. Again it's easy to see that $ (2n+a)^2+L=(2m+c)^2$ is solvable iff $ L=8k+4$ or $ L=16k$. Suppose that we have several pairwise disjoint sets as required having all $ a$ even. Note that no $ 3$ sets can have all $ a$'s congruent modulo $ 4$, as for these sets, say $ S_{a,b}$, $ S_{c,d}$, $ S_{e,f}$, we have $ a^2-c^2,c^2-e^2,e^2-a^2$ all divisible by $ 16$ (remember $ a,c,e$ are even), and for some $ 2$ of them, say first $ 2$ we have either $ b-d$ odd, or $ b-d$ multiple of $ 4$ which lead to the cases $ L=16k+4=8k'+4$ and $ L=16k$. Take now $ 2$ sets $ S_{a,b}$, $ S_{c,d}$ with $ a-c$ divisible by $ 4$. In order for them not to intersect, we need $ L=4(b-d)+c^2-a^2$ to be equal to $ 16k+8$, or $ b-d$ to be equal to $ 2$ modulo $ 4$. As we have proved, no other set with same residue of its $ a$ modulo $ 4$ can be added. Suppose we can add another set $ S_{e,f}$. Then $ e-a=e-c=2$ modulo $ 4$. For $ S_{e,f}$ not to intersect with any of $ S_{a,b}$ and $ S_{c,d}$ we need the respective $ L$ for both of them to be $ 16k+8$. Since $ e^2-c^2=e^2-a^2$ modulo $ 16$ we must have $ f-d$ equal $ f-b$ (and equal $ \pm1$) modulo $ 4$, which is impossible, as $ b-d=2$ modulo $ 4$. So at most $ 2$ sets exist. I hope I analyzed all cases correctly and that I didn't miss any case...