For positive integers $a_1,a_2 ,\ldots,a_{2006}$ such that $\frac{a_1}{a_2},\frac{a_2}{a_3},\ldots,\frac{a_{2005}}{a_{2006}}$ are pairwise distinct, find the minimum possible amount of distinct positive integers in the set$\{a_1,a_2,...,a_{2006}\}$.
Problem
Source: China NMO 2006, Problem 2
Tags: number theory unsolved, number theory
leepakhin
30.01.2006 18:51
I think this is a combinatorial problem...
Gabriel(fr)
31.01.2006 22:02
The minimum possible amount of distinct integers of the sequence $[a_n]_1^{2006}$ can be given when we repeat in a maximum possible way,the numerator or denominator of the distinct elements of the set $\{\frac{a_1}{a_2},\frac{a_2}{a_3},\ldots,\frac{a_{2005}}{a_{2006}}\}$ and its happens keeping constant a member of the sequence, for example:
If $a_1=x$, $a_2=y$ and $\{x,y \in Z|x$ ≠ $y\}$, $x$ is the constant and $y$ is fixed,a example of a set in the condition described above is:
$\{\frac{x}{y},\frac{y}{x},\frac{x}{2y},\frac{2y}{x},\frac{x}{3y},\frac{3y}{x},...,\frac{x}{1003y}\}$ such that $a_{2k-1}=x$, $a_{2k}=ky$ for $1 \le k \le 1003$.
note that the set follows the division postulate,since two fractions with equal numerator or denominator to be distinct must have different denominator or numerator,consequently the distinct members of the sequence are:
$x,y,2y,3y,...,1003y$ and the amount is $1004$.
nthd
04.02.2006 04:24
My answer is$46$ with $k\le 45$Let$(a_1,a_2,...,a_{2006})=(b_1,b_2,...,b_k)$with$b_1<b_2<...<b_k$ $B=$ { $(b_i,b_j)|1\le i\neq j \le k$ }$\rightarrow |B|=2.C^2_k<2005$ $(a_i,a_{i+1})\in B\forall 1\le i<2006\newline\rightarrow\exists 1\le i<j<2006: (a_i,a_{i+1})=(a_j,a_{j+1})\newline\rightarrow \frac{a_i}{a_{i+1}}=\frac{a_j}{a_{j+1}}$ Contraction! With$k=46$Choose$p_1,p_2,...p_{46}$are $46$ distinct prime number.$(a_1,...a_{46}),(a_{47},...a_{92}),....(a_{1933},...a_{1978}),(a_{1979},...a_{2024})$ are distinct permuations of$(p_1,...p_{46})$
gauss2
15.09.2006 19:20
who true? nthd or gabriel?
Rust
15.09.2006 19:45
nthd. But for n (n=2006) and k we have k is minimum, suth that $k(k-1)+2\ge n$. For example if n=8, then k=3 $a_{1}=1,a_{2}=1,a_{3}=2,a_{4}=1,a_{5}=3,a_{6}=2,a_{7}=3,a_{8}=1.$