A very intuitive problem

For discussing Olympiad Level Number Theory problems
User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:
A very intuitive problem

Unread post by *Mahi* » Thu Oct 09, 2014 2:10 pm

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 disjoint sets.

$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\}$

(Iranian 3rd round Number Theory exam P6)
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: A very intuitive problem

Unread post by Phlembac Adib Hasan » Tue Oct 14, 2014 1:54 pm

The answer:(Spoiler)
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$
Reason:
I totally agree with the title, I only followed my guts to decide what I should do and what shouldn't.
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 $\small \textit{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)
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$
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Post Reply