a) Do there exist $2$-element subsets $A_1,A_2,A_3,...$ of natural numbers such that each natural number appears in exactly one of these sets and also for each natural number $n$, sum of the elements of $A_n$ equals $1391+n$? b) Do there exist $2$-element subsets $A_1,A_2,A_3,...$ of natural numbers such that each natural number appears in exactly one of these sets and also for each natural number $n$, sum of the elements of $A_n$ equals $1391+n^2$? Proposed by Morteza Saghafian
Problem
Source: Iran 2nd round 2012-Day2-P4
Tags: inequalities, combinatorics proposed, combinatorics
mavropnevma
01.05.2012 12:02
a) is quite simply impossible, for any value $k$ instead of the Hegira year $1391$. For any $n$, the sum of the elements of the sets $A_1,A_2,\ldots,A_n$ will then be $kn + \frac {n(n+1)} {2}$; on the other hand it is at least $\frac {2n(2n+1)} {2}$, the sum of the least $2n$ distinct positive integers. Thus we must have $kn + \frac {n(n+1)} {2} \geq \frac {2n(2n+1)} {2}$, impossible for large $n$.
hadikh
01.05.2012 12:07
b) $A_1=\{ 1,1391 \}$
$A_{n+1}=\{x,1391+(n+1)^2-x : x=\min \{\mathbb{N}-\bigcup_{i=1}^{n}A_i\}\}$
MANMAID
17.05.2012 20:43
S$(\sum_{i=1}^{n}A_{i})_{min}=\frac{n(n+1)}{2}+(n-1)+2=\frac{n^2+n}{2}+n+1\le{1391+n}$ $\Rightarrow{n^2+n\le{2780}}$ then for large $n$ the inequality does not hold.hence ans. is no .