Find the maximum number of pairwise disjoint sets of the form $S_{a,b} = \{n^{2}+an+b | n \in \mathbb{Z}\}$, $a, b \in \mathbb{Z}$.
Problem
Source: Turkey TST 1996 Problem 5
Tags: linear algebra, matrix, number theory proposed, number theory
31.07.2013 08:30
Suppose that there exist 3 pairwise disjoint sets $ S_{a_i,\, b_i}\: \: (1\leq i\leq 3) $. Define $ k_i=\left\{\begin{matrix} b_i-\frac{a_i^2}{4}\: \:\: (a_i\equiv 0\: \: (mod\: \: 2))\\\\b_i-\frac{a_i^2-1}{4}\: \:\: (a_i\equiv 1\: \: (mod\: \: 2)) \end{matrix}\right. $ Case 1) $ a_i\equiv a_j\equiv 1\: \: (mod\: \: 2) $ and $ k_i\equiv k_j\: \: (mod\: \: 2) $ : $ n=\frac{(k_i-k_j)-(a_i+1)}{2},\: m=\frac{(k_i-k_j)-(a_j-1)}{2}\: $ then $\: n^2+a_in+b_i=m^2+a_jm+b_j $ . Case 2) $ a_i\equiv a_j\equiv 0\: \: (mod\: \: 2) $ and $ k_i\equiv k_j\: \: (mod\: \: 4) $ : $n=\frac{(k_i-k_j)-2a_i}{4}-1,\: m=\frac{(k_i-k_j)-2a_j}{4}+1\: $ then $\: n^2+a_in+b_i=m^2+a_jm+b_j $ . Case 3) $ a_i\equiv a_j\equiv 0\: \: (mod\: \: 2) $ and $ k_i\equiv k_j+1\: \: (mod\: \: 2) $ : $ n=\frac{(k_i-k_j)-a_i-1}{2},\: m=\frac{(k_i-k_j)-a_j+1}{2}\: $ then $\: n^2+a_in+b_i=m^2+a_jm+b_j $ . Case 4) $ a_i\equiv 0\: \: (mod\: \: 2),\: a_j\equiv 1\: \: (mod\: \: 2) $ : $ n=(k_i-k_j)-\frac{a_i}{2},\: m=(k_i-k_j)-\frac{a_j-1}{2}\: $ then $\: n^2+a_in+b_i=m^2+a_jm+b_j $ . By Case 4, $a_1\equiv a_2\equiv a_3\: \: (mod\: \: 2)$ . If $a_1\equiv0\:\:(mod\:\:2)$, we can choose $i,\: j$ that satisfy $ \left \{ i,\: j \right \}\subset \left \{ 1,\, 2,\, 3 \right \} $ and $ k_i\equiv k_j\: \: (mod\: \: 2) $ and it is contradiction by Case 1. If $a_1\equiv1\:\:(mod\:\:2)$, we can choose $i,\: j$ that satisfy $ \left \{ i,\: j \right \}\subset \left \{ 1,\, 2,\, 3 \right \} $ and $ ( k_i\equiv k_j\: \: (mod\: \: 4) \:\: or \:\: k_i\equiv k_j+1\: \: (mod\: \: 2) ) $, and it is contradiction by Case 2, 3. So maximum number of pairwise disjoint sets is not larger than 2. It is trivial that $S_{0,\, 0},\: S_{0,\, 2} $ is pairwise disjoint, so the answer is 2.
11.09.2013 20:17
It's Pen O 17
07.01.2018 19:04
Remark This remark, should actually have come after the answer, but since often those are omitted, I have attached to the top. This problem bears a lot of similarity with, IMO 1995 Shortlist N2, https://artofproblemsolving.com/community/c6h219898p1219467 We claim that the answer is $2$. We will start by a series of observations. $a)$ $a$ is even. Let $a=2k$. We claim that, $S_{a,b}=S_{0,b-k^2}$. To see this, note that, if $x\in S_{a,b}$, then, $$ x=n^2+2kn+b = (n+k)^2 +b-k^2 \implies x\in S_{0,b-k^2} (\text{with $n\mapsto n+k$}) \implies S_{a,b}\subseteq S_{0,b-k^2} $$Similarly, if $x\in S_{0,b-k^2}$, then, $x=n_0^2 + b-k^2$ for some $n_0$. Letting $n=n_0-k$, we observe that, $n^2 + 2kn + b =n_0^2 - 2n_0k+k^2 +2kn_0+b-2k^2 = n_0^2 + b-k^2$, which implies, $S_{0,b-k^2}\subseteq S_{a,b}$. Combining this, with what was just found, we get the result. $b)$ $a$ is odd. Let $a=2k+1$. Then, $S_{a,b}=S_{1,b-k^2-k}$. To see this, simply observe that, $n^2 + 2kn + n + b = (n+k)^2 + (n+k) + b-k^2-k$, and carry out the previous argument. Hence, depending on the parity of $a$, and $b$, the sets can be reduced to a simpler family of sets, now parametrized by only one parameter (well, that parameter, depends on both $a,b$, but the point is, the polynomial has only one varying coefficient, that makes it easier to play with). Claim 1: For any $m$ and $m'$, we have, $S_{1,m}\cap S_{0,m'}\neq \emptyset$. Proof: Let us show, how to obtain an element, which lies in the intersection. We seek for a pair $(n_0,n_1)$ of integers, satisfying, $n_0^2 + n_0 + m = n_1^2 + m'$. Multiplying both sides by $4$, and completing to a square, we have, $$ 4n_0^2+4n_0+4m + 1 = 4n_1^2 + 4m' + 1 \implies (2n_0+1-2n_1)(2n_0+1+2n_1)=4m'-4m+1. $$Let, $2n_0-2n_1 + 1 =1$ (which gives, $n_0=n_1$), and, $4n_0+1 = 4m'-4m+1 \implies (n_0,n_1)=(m'-m,m'-m)$. Hence, for this pair, the two given sets intersect. Claim 2: Let $I_0$ and $I_1$ be two index sets, satisfying, $$ m,m' \in I_0, m\neq m' \implies S_{0,m}\cap S_{0,m'}=\emptyset, $$and, $$ n,n' \in I_1, n\neq n' \implies S_{1,n}\cap S_{1,n'}=\emptyset. $$Then, $|I_0|,|I_1|\leq 2$. Proof: Let us begin by the first claim. We want to ensure that, no pair $(x,y)$ satisfies, $x^2 + m = y^2 + m'$, namely, the following, $(x-y)(x+y) = m'-m$, has no solutions. We first make a useful observation. If $m'-m$ is an odd number, then, the following pair achieves the equality: $$ (x,y) =\left(\frac{m'-m+1}{2},\frac{m'-m-1}{2}\right). $$Continuing, if $4\mid m'-m$, then, letting, $x-y=2$ and $x+y=\frac{m'-m}{2}$, we get, $$ (x,y)=\left(\frac{m'-m}{4}+1,\frac{m'-m}{4}-1\right), $$yielding an equality. Hence, the only remaining case, is, $m'-m \equiv 2 \pmod{4}$. In this case, note that, we indeed do not have a solution, since, $x-y\equiv x+y \pmod{2}$, therefore, at least one must be divisible by $2$, thus the other, making the product divisible by $4$, contradiction. Now, suppose that, $|I_0|\geq 3$. Take, three distinct members $m,m'$, and $m''$ of $I_0$, and note that, from the given conditions, $m-m'\equiv 2 \pmod{4}$, and $m-m''\equiv 2 \pmod{4}$. However, subtraction gives us, $m'-m''\equiv 0 \pmod{4}$, therefore, $S_{0,m'}\cap S_{0,m''}\neq \emptyset$, contradiction. Similarly, for $I_1$, we want to ensure that, no pair $(x,y)$ solves, $$ x^2 + x + n = y^2 + y + n'. $$Again, multiplying by $4$, and completing to a square, we need to study, $$ (x-y)(x+y+1)=n'-n. $$Now, note that, $x-y$ and $x+y+1$ has opposite polarity in modulo $4$, hence, for $n'-n$, that is not divisible by $2$, we realize that this equation has no solutions. If, let's say, $n'-n\equiv 2 \pmod{4}$, then, letting, $n'-n=4u+2$, $x-y=2$, and $x+y =2u$, we get, $$ (x,y)=\left(u+1,u-1\right), $$achieves the pair. Similarly, if $4\mid n'-n$, then, letting $n'-n=4u$, we can simply let, $x-y=1$, and $x+y+1=4u$, and solve as, $$ (x,y)=\left(2u,2u-1\right). $$Hence, if $I_1$ is an index set of $n$'s for which, $\{S_{1,n}\}_{n\in I_1}$ are disjoint, then, the difference of any two must be an odd number. However, again, if $|I_1|\geq 3$, then, taking three members, $n,n'$, and $n''$, we get, $n-n'$ is odd; and $n'-n''$ is odd, and therefore, $n-n''$ must be even, making, $S_{0,n}\cap S_{0,n''}\neq \emptyset$, contradiction. Thus, at most two such sets can be taken.