The $n$-tuple $(a_1,a_2,\ldots,a_n)$ of integers satisfies the following: (i) $1\le a_1<a_2<\cdots < a_n\le 50$ (ii) for each $n$-tuple $(b_1,b_2,\ldots,b_n)$ of positive integers, there exist a positive integer $m$ and an $n$-tuple $(c_1,c_2,\ldots,c_n)$ of positive integers such that \[mb_i=c_i^{a_i}\qquad\text{for } i=1,2,\ldots,n. \] Prove that $n\le 16$ and determine the number of $n$-tuples $(a_1,a_2,\ldots,a_n$) satisfying these conditions for $n=16$.
Problem
Source: Czech-Polish-Slovak Match, 2009
Tags: number theory unsolved, number theory
anonymouslonely
10.02.2012 13:59
let be $ b_{i}=p_{1}^{v_{i,1}}p_{2}^{v_{i,2}}.......p_{t}^{v_{i,t}} $. then $ m=kp_{1}^{v_{1}}p_{2}^{v_{2}}...........p_{t}^{v_{t}} $ and $ (k,p_{i})=1 $ for each $ i $. then we must have $ v_{i}+v_{i,j} $ divisible by $ a_{i} $ for each $ i $. because $ v_{i,j} $ are chosen arbitrarly then $ (a_{i},a_{j})=1 $ for each $ i<> j $. then it is easy to see that if this condition is satisfied the numbers $ c_{i} $ exist from chinese theorem. then we make the following partition: $ 1 $ $ 2t, 1 \leq t \leq 25 $ $ 3,9,15,21,27,33,39,45 $ $ 5,25 $ $ 7,49 $ $ 11,13,17,19,23,29,31,37,41,43,47 $. then from $ n \leq 1+1+1+1+1+11=16 $. the number of solutions for $ n=16 $ is $ 5*3*2*2=60 $ because the first and the last sequence must be taken. then from the others we must take exactly one element from each one. then from the second we must take $ 2^{a} $,from the third $ 3^{b} $,from the forth $ 5^{c} $ and from the fifth $ 7^{d} $.
AFSA
06.11.2019 14:45
anonymouslonely wrote: let be $ b_{i}=p_{1}^{v_{i,1}}p_{2}^{v_{i,2}}.......p_{t}^{v_{i,t}} $. then $ m=kp_{1}^{v_{1}}p_{2}^{v_{2}}...........p_{t}^{v_{t}} $ and $ (k,p_{i})=1 $ for each $ i $. then we must have $ v_{i}+v_{i,j} $ divisible by $ a_{i} $ for each $ i $. because $ v_{i,j} $ are chosen arbitrarly then $ (a_{i},a_{j})=1 $ for each $ i<> j $. then it is easy to see that if this condition is satisfied the numbers $ c_{i} $ exist from chinese theorem. then we make the following partition: $ 1 $ $ 2t, 1 \leq t \leq 25 $ $ 3,9,15,21,27,33,39,45 $ $ 5,25 $ $ 7,49 $ $ 11,13,17,19,23,29,31,37,41,43,47 $. then from $ n \leq 1+1+1+1+1+11=16 $. the number of solutions for $ n=16 $ is $ 5*3*2*2=60 $ because the first and the last sequence must be taken. then from the others we must take exactly one element from each one. then from the second we must take $ 2^{a} $,from the third $ 3^{b} $,from the forth $ 5^{c} $ and from the fifth $ 7^{d} $. your solution is right but in case $n=16$ you forgot that $a_{i}$ can be equal to one.