Suppose $A\subseteq \{0,1,\dots,29\}$. It satisfies that for any integer $k$ and any two members $a,b\in A$($a,b$ is allowed to be same), $a+b+30k$ is always not the product of two consecutive integers. Please find $A$ with largest possible cardinality.
Problem
Source: China Team Selection Test 2003, Day 1, Problem 2
Tags: quadratics, modular arithmetic, combinatorics unsolved, combinatorics
20.12.2005 07:09
OK I HOPE THIS WORKS Problem. Suppose $A\subseteq \{0,1,\dots,29\}$ and that for any integer $k$ and any two members $a,b\in A$ (not necessarily distinct), $a+b+30k$ is always not the product of two consecutive integers. Find the maximum number of elements of $A$. Solution. Let us call a nonnegative integer $s$ bad iff there exists an integer $k$ such that $s+30k$ is the product of two consecutive integers. Thus, $s$ is bad iff $s+30k = n(n+1)$ has a solution with $n$ an integer. In other words, regarding the equation as a quadratic in $n$, we have $s$ is bad iff the discriminant $\Delta = 1+4(s+30k)$ is a perfect square. We need only to consider $0 \leq s \leq 58$ for this problem (why?). Note that there exists an integer $k$ such that $\Delta = 1+4s+120k$ is a perfect square iff there exists an integer $x$ such that $x^2 \equiv 1+4s \pmod 120$. Clearly, $x$ must be odd so we have $(x+30)^2 \equiv x^2+60x+900 \equiv x^2+60+60 \equiv x^2 \pmod {120}$ Thus, after a (somewhat tedious!) check of $x^2 \pmod {120}$ for $x = 1,3,\dots 29$, we conclude that the only possible values of $x^2 \pmod {120}$ are $1,9,25,49,81,105$. Thus, $1+4s$ must be congruent to these values, so we obtain all bad values: $s = 0,30,2,32,6,36,12,42,20,50,26,56$. Now, in particular, $0,15,1,16,3,18,6,21,10,25,13,28 \not\in A$. (why?) Thus, the only possible values of elements in $A$ are the following: $2,4,5,7,8,9,11,12,14,17,19,20,22,23,24,26,27,29$ and checking shows that the following pairs are the only even ones that can't be in $A$. (Note that the bad values of $s$ are all even, so we divide this up into even and odd). $(2,4), (2,24), (4,8), (4,22), (4,26), (8,12), (8,22), (8,24), (12,24), (12, 20), (12,24), (14,22),(20, 22), (24,26)$ and the best we can do is $2,14,20,26 \in A$ (these are the only ones which appear twice above, everything else appears four times... The proof is pretty boring and left as an exercise to the reader Well, I hope it's right... I haven't checked it) Similarly, we deal with the odd case as follows. $(5,7), (5,27), (7,19), (7,23), (7, 29), (9, 11), (9, 17), (9, 23), (9, 27), (11, 19), (17, 19), (19, 23), (23, 27), (27, 29)$ and we can get by with $5,11,17,29 \in A$ (same comments as above) Thus, the maximum number of elements in $A$ is $4 + 4 = 8$. (I hope )
08.07.2006 21:06
hmm.. I think I've found a 10 number solution, I'll provide the details later. EDIT: Ok, here's my solution: First notice that \[(n+15)(n+16) = n^{2}+31n+240 = n^{2}+n = n(n+1) \quad (\textrm{mod }30).\] So a product of two consecutive numbers must be $0, 2, 6, 12, 20, 26 \textrm{ mod }30$. (check all possibilities of n) Now the condition $a+b+30k$ is never a product of two consecutive integers is equal to the condition that $a+b=0, 2, 6, 12, 20, 26 \textrm{ mod }30$. Then notice that $a$ cannot be $0, 1, 3, 6, 10, 13 \textrm{ mod }15$. We deduce that \[A \subseteq \{2, 4, 5, 7, 8, 9, 11, 12, 14, 17, 19, 20, 22, 23, 24, 26, 27, 29\}\] Since products of two consecutive numbers are always even, it suffices to check the cases that $a$ and $b$ are both even or both odd. If $a$ and $b$ are both even, notice that there are 9 even numbers, and that \[2+4=6; 8+12=20; 14+22=36; 24+26=50,\] so there are fewer or equal to 5 even elements in $A$. If $a$ and $b$ are both odd, notice that there are 9 odd numbers, and that \[5+7=12; 9+11=20; 17+19=36; 23+27=50,\] so there are fewer or equal to 5 odd elements in $A$. So there are fewer or equal to 10 elements in $A$. Now it is easy to check that \[A =\{2,5,8,11,14,17,20,23,26,29\}\] satisfies the conditions. (checking mod 6, or even mod 3, might be easier, now I look at this...) So the maximum value of $|A|$ is 10.
09.08.2018 19:54
Here is the solution.$n(n+1)$ can be congruent to $0,2,6,12,20,26$ , so if $a+b\equiv 0,2,6,12,20,26 \pmod {30}$ then there exists $k$ such that $a+b+30k=n(n+1)$ .Proof; Let $a+b=30m+t$ with $t=(0,2,6,12,20,26)$ . Now equation looks like this $a+b+30k=30m+t+30k=n(n+1)$ $30m+t+30k=n(n+1)$ We take $n\ge 10^{m+300} $(take it large so that $r$ is bigger than m) and $n(n+1)\equiv t \pmod {30}$ ,so $n(n+1)=30r+t$ and $r> m$ ; $30m+t+30k=n(n+1)=30r+t$ Now just take $k=r-m$ and proof is finished.Now we can see that $0,1,3,6,10,13,15,16,18,20,21,25,28 \not\in A$ (because if some $x\in A$ then $2x$ is congruent to $0,2,6,12,20,26$) Next pair rest of them like this $(2,4),(5,7),(9,11),(8,12),(14,22),(19,23),(24,26),(27,29)$ . From any pair we can take at most $1$ (if we take two then their sum is $0,2,6,12,20,26$) .So from pairs we take at most 8 numbers and we are left with two that are not in any pair and that are not disregarded ($17$ and $20$ ). From this follows that $|A| \le 8+2=10$ and equality is all that are congruent to $2$ $mod 3$ (sum of any two can not be $n(n+1)$ because their sum is $\equiv 1 \pmod {3}$ but $n(n+1)\equiv 0 or 2 \pmod {3}$ ) and we are done .