Prove that there are 100 natural number $a_1 < a_2 < ... < a_{99} < a_{100}$ ( $ a_i < 10^6$) such that A , A+A , 2A , A+2A , 2A + 2A are five sets apart ? $A = \{a_1 , a_2 ,... , a_{99} ,a_{100}\}$ $2A = \{2a_i \vert 1\leq i\leq 100\}$ $A+A = \{a_i + a_j \vert 1\leq i<j\leq 100\}$ $A + 2A = \{a_i + 2a_j \vert 1\leq i,j\leq 100\}$ $2A + 2A = \{2a_i + 2a_j \vert 1\leq i<j\leq 100\}$ (20 ponits )
Problem
Source: Iranian 3rd round Number Theory exam P6
Tags: modular arithmetic, arithmetic series, number theory proposed, number theory
dibyo_99
08.10.2014 08:37
Probably, you mean the sets are disjoint. Note that if we take all elements of $A$ to be $1 \pmod{5}$, then all elements of $A+2A$ are all $3 \pmod{5}$ and those of $2A+2A$ are $4 \pmod{5}$. Also, $A+A$ and $2A$ have only $2 \pmod{5}$ elements. Therefore, the only two sets which may not be disjoint are $A+A$ and $2A$. Now, we show that is is possible to explicitly construct an $A$ with the property. If $A+A$ and $2A$ weren't disjoint, we would have numbers $x,y,z$ such that $(5x+1)+(5y+1) = 2(5z+1) \Longleftrightarrow x+y = 2z$. Now, if we can create a set $B$ of non-negative integers such that no element is the arithmetic mean of some other two, we could make $A = 5B+1$ and be done. We claim that numbers which don't have any $2$'s in their ternary expansion do the trick. Suppose to the contrary, i.e., $\exists$ distinct $x,y,z \in \mathbb{N}_0$ with no $2$'s in their base $3$ representation such that $x+y = 2z$. Since $z$ has only $1$'s and $0$'s, so $2z$ has only $0$'s and $2$'s in its ternary representation. Now, consider the first position from the right where $x$ and $y$ have a different digit (this exists because $x \neq y$). Adding, up until this position, all digits in the sum are $0$ or $2$ ($0+0=0$, $1+1=2$) and there are no carries. In this position, the $2$ digits must be $0$ and $1$, which add up to $1$. However, $1$ is not present in $2z$, contradiction. Taking the first $100$ non-negative integers with no $2$ in its ternary representation in $B$, we find that the maximum element of $B$ is $976$. So, the maximum element of $A = a_{100} = 5 \times 976+1 < 10^6$. Therefore, there does exist such a set $A$.
Particle
14.10.2014 12:16
Call a number good, if it is the product of one or more $4k-1$ primes(not necessarily distinct). Suppose $g_i$ denotes $i$-th good number. Then take $a_i=5g_i^2+1$
When we have this sort of problems, we basically have two choices, either to approach indirectly to arrive at a contradiction or to construct a set/series/function following the given conditions. Here the first option would complexify the whole thing. So I chose the second.
Now how can we find a 'nice and simple series'? First choice would be the series of consecutive integers which actually don't work, not even any other arithmetic series. But a simple series should involve some arithmetic sequence. Because in problems with set addition, the terms of an arithmetic series can make the derived sets disjoint. ( This experience is from IMO SL 2012 A2). So I loosed the condition a bit. Suppose $a_i=cb_i+d$ Now if we take $c\ge 5$ all the sets except $A+A$ and $2A$ become disjoint. Note that we can set any value $\ge 5$ for $c$. But why $c=5$? Because provides the largest range for $b_i<2\cdot 10^5$. Also notice that if the series $\{b\}_{i=1}^{100}$ has no three $a,b,c$ such that $\frac {a+b}2=c$, the sets $2A$ and $A+A$ become disjoint. Because squares and other higher powers hardly produce such special arithmetic series, my first choice was to take the series of squares(with some modification) as $b_i$. After some experiments, I realized if I take $b_i=g_i^2$, it produces my desired series.
(A short proof for rigorousness)
If $b_i=g_i^2$ contained any 'special' arithmetic subsequence, then
$g_p^2+g_q^2=2g_r^2$ Note that $g_p$ and $g_q$ must be of same parity, So we can assume $g_p=m+n$ and $g_q=m-n\Longrightarrow m^2+n^2=g_r^2$. Since they form a Pythagorean Tripple, we must have $g_r=z(x^2+y^2)$ but $x^2+y^2$ can't divide any $4k-1$ type prime or their products. A contradiction. Now it is left to show $g_{100}^2<400^2<2\cdot 10^5$ We can do it like this.
There are $40$ good primes less than $400$. And multiplying any two from $\{3,7,9,11,19,21,\}$ we can make more $35$ good numbers. After that multiplying $3$ with $23,31,..., 131$ we get $17$ more. Now add the numbers $23\cdot 7,...,47\cdot 7$ and $23\cdot 9,..., 43\cdot 9$. So there are at least $40+35+17+5+3=100$ good numbers less that $400$. Hence $g_{100}<400$
TheOverlord
26.10.2014 21:28
Actually the problem at ghe exam wasn't this, it was a bit harder. Similar to http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=17475& The first and second set had to include 100 different members and third and fifth had to include 9900 different members and the fourth had two include 10000 different members, in addition to the sets being disjoint.
Gaussian_cyber
27.07.2020 15:40
TheOverlord wrote: The first and second set had to include 100 different members and third and fifth had to include 9900 different members and the fourth had two include 10000 different members, in addition to the sets being disjoint. Any proof for this one? I didn't get it I have a bit better bound but it is sometimes not true for the set 4 and sometimes not true for the set (2,3). so