For each integer $C>1$ decide whether there exist pairwise distinct positive integers $a_1,a_2,a_3,...$ such that for every $k\ge 1$, $a_{k+1}^k$ divides $C^ka_1a_2...a_k$. Proposed by Daniel Liu
Problem
Source: 2017 ELMO Shortlist N3
Tags: number theory, Hi
03.07.2017 19:04
My solution:i will prove that there is no sequence sastisfied the problem Let $p|C$ and $t=v_p(C)$ and $b_k=v_p(a_k)$ So we need $b_{k+1}.k<=tk+\sum_{i=1}$ Consider sequence $c_n=\sum_{k=1}^{n}\frac{1}{k}$ We can easily prove that $b_n<=[ta_n]+b_1$ But note that there exist m such that for all $n>m$,$n-b_1>[ta_n]$ Which implies there exist infinitive number i,j:$b_i=b_j$ Let S={(i,j),$b_i=b_j$} Consider prime $q=!p$ of C We found that in S there are infinitive (t,s):$v_p(a_t)=v_p(a_s)$ and $v_q(a_t)=v_q(a_s)$ Continue this with all prime divisor of C we are done
16.07.2017 11:48
22.08.2020 20:46
Nice problem. I will give a sketch. tastymath75025 wrote: For each integer $C>1$ decide whether there exist pairwise distinct positive integers $a_1,a_2,a_3,...$ such that for every $k\ge 1$, $a_{k+1}^k$ divides $C^ka_1a_2...a_k$. The answer is no. Suppose not for a fixed $C.$ Consider any prime $p.$ Then the problem gives $$k\nu_p (a_{k+1}) \le k\nu_p(C)+\nu_p(a_1)+\dots+\nu_p(a_k).$$Now we have the following key claim which can be proven by simple induction: Claim: Let $\text{H}_n$ denote the $n$th harmonic number. Then $$\nu_p( a_n)-\nu_p(a_1) \le \text{H}_n \nu_p(C).$$ The key hypothesis we need now is that $a_i$ are pairwise distinct. The claim gives $\nu_p(C)=0 \implies \nu_p(a_n) \le \nu_p(a_1).$ In particular $\nu_p(a_m)$ is eventually constant. So ignore primes for which $\nu_p(C)=0.$ This means we only have a finite set of prime factors to worry about for the sequence now. The claim clearly gives $\nu_p(a_n/a_1) \le A \log n$ for some constant $A$ and all primes $p.$ Now it is not too hard to see that we can find arbitrarily large intervals over which $\left \lfloor A\log x \right \rfloor$ is constant. Since the set of prime factors of $\{a_k\}$ is finite now, hence by pigeonhole two terms $a_i,a_j$ will have the same $\nu_p$ for all primes $p,$ hence will be equal, a contradiction. $\square$
25.01.2021 17:42
There is no such sequence for any $C$. For convenience, define $x_n = v_p(a_n)$ for every integer $n$. Furthermore, define $h_n = \frac{1}{1}+\frac{1}{2}+\dots+\frac{1}{n}$. Finally, let $S = v_p(C)$. The pith of the problem lies in the following claim: Claim: $x_n \leq x_1 + Sh_n$. Proof: By strong induction. Remark that the condition tells us $$x_n \leq S + \frac{x_1+x_2+\dots+x_{n-1}}{n-1}.$$ This claim implies that for any prime $p$, there exists an arbitrary long sub-sequence of terms $a_i,a_{i+1},\dots,a_j$ such that $\nu_p(a_i) = \nu_p(a_{i+1}) = \dots = \nu_p(a_j)$ for sufficiently large $i$ and $j$. Note that for primes $p$ in $a_1$ but not $C$, $\nu_p(a_i) \leq \nu_p(a_1)$, so there are only a finite number of possible terms with equal $v_p$ for all primes $p \in C$. Therefore, for sufficiently large $i$ there will be two equal terms, the end.
20.09.2021 08:47
tastymath75025 wrote: For each integer $C>1$ decide whether there exist pairwise distinct positive integers $a_1,a_2,a_3,...$ such that for every $k\ge 1$, $a_{k+1}^k$ divides $C^ka_1a_2...a_k$. Proposed by Daniel Liu Define $\mathbf{H}_n=1+\frac{1}{2}+.............+\frac{1}{n}$ The condition is equivalent to $k\nu_p(a_{k+1}) \le k \nu_p(C)+\sum_{j=1}^k \nu_p(a_j)$ Claim: $\nu_p(a_n)-\nu_p(a_1) \le\mathbf{H}_n \nu_p(C)$ Proof: Obvious by strong induction. This implies that $\nu_p(a_j)$ is bounded and when $j$ is sufficiently large we will get $\nu_p(a_j)=\nu_p(a_{j+1}),\forall p \implies a_j=a_{j+1} $, contradiction.
16.11.2021 20:09
I'll prove that for no $C$ there exists such a sequence. I'll start with the following claim: Claim: $v_p(a_{k+1})\leq (1+\frac12 + \cdots +\frac1k)v_p(C) + v_p(a_1)$ for every prime $p$. Proof : It's not hard to show this by induction. We can find arbitrarily large intervals over which $(1+\frac12 + \cdots +\frac1k)v_p(C) + v_p(a_1)$ is constant, but note that $a_{k+1}$ can take only values which are divisors of $a_1C^{X}$ where $X=\lceil (1+\frac12 + \cdots +\frac1k)v_p(C)\rceil $. Now at some point $d(a_1C^{X})$ is going to be smaller than the length of these intervals because $1+\frac12 + \cdots +\frac1k$ grows very slowly, so the $a_i$'s can't be distinct over these intervals.
05.02.2022 17:27
Here's a different proof (we will bound the $v_p$'s differently without the harmonic number). We will show for any $C$, such a sequence does not exist. Assume contrary. Fix $C$ and such a sequence. Call a prime nice if it divides some $a_i$. Note all nice primes must divide $C \cdot a_1$, in particular number of nice primes is finite. Fix a $c > 1$ such that $c > v_p(C)$ for all primes $p$. Fix any nice prime $p$. Let $b_i = v_p(a_i)$. Then we know that $$k b_{k+1} \le kc + b_1 + b_2 + \cdots + b_k ~~ \forall ~ k \ge 2 \qquad \qquad (1)$$Intuitively, we will show that $b_i$'s grow slowly. Call an $i \ge 2$ a peak if $b_i > b_{i-1},\ldots,b_1$. Let $i_1+1 < i_2 + 1< i_3 + 1 < \cdots$ be all the peaks. Claim 1: For all $n \ge 1$ we have $$\frac{i_1 + i_2 + \cdots + i_n}{i_n} \le c ~ \iff ~ \frac{i_1 + \cdots + i_{n-1}}{i_n} \le c-1$$ Proof: Define $$f(m) = (b_m - b_1) + (b_m - 2) + \cdots + (b_m - b_{m-1})~ \forall ~ m \ge 2$$. Note $(1)$ is equivalent to $$ \frac{f(k)}{k-1} \ge c \qquad \qquad (2) $$Observe that for any $n \ge 1$ that \begin{align*} f(i_{n + 1} + 1) &= \sum_{j=1}^{i_{n+1}}\left( b_{i_{n+1} + 1} - b_j \right) = \sum_{j= i_n + 1}^{i_{n+1}} (b_{i_{n+1} + 1} - b_j) + \sum_{j=1}^{i_n} (b_{i_{n+1} + 1} - b_j) \\ &\ge (i_{n+1} - i_n)(b_{i_{n+1} + 1} - b_{i_n + 1}) + \sum_{j=1}^{i_n} \bigg( (b_{i_{n+1} + 1} - b_{i_{n} + 1}) + (b_{i_n + 1} - b_j) \bigg) \\ &= i_{n+1}(b_{i_{n+1} + 1} - b_{i_n + 1}) + f(i_n + 1) \ge i_{n+1} + f(i_n + 1) \end{align*}Now note $f(i_1 + 1) \ge i_1$. So it follows that $$f(i_n + 1) \ge i_1 + i_2 + \cdots + i_n ~~ \forall ~ n \ge 1$$Plugging $k = i_n + 1$ in $(2)$ and using above implies our claim. $\square$ Claim 2: $\exists$ an $\alpha > 1$ such that $i_k \ge \alpha^{k-1} ~ \forall ~ k \ge c+2$. Proof: We will only use each $i_n \ge 1$ and Claim 1 to prove this. Observe $i_1 + \cdots + i_{c+1} > c+1$, since all of them cannot be $(1)$ (by Claim 1 for $n=c+1$). Now choose a very small $\alpha > 1$ such that: \begin{align*} i_1 + i_2 + \cdots + i_{c+1} \ge 1 + \alpha + \cdots + \alpha^c \\ \frac{1}{\alpha} + \frac{1}{\alpha^2} + \cdots + \frac{1}{\alpha^c} \ge c-1 \end{align*}We show this $\alpha$ works. Suppose for some $t \ge c+1$ it holds that $i_1 + \cdots + i_t \ge 1 + \alpha + \cdots + \alpha^{t-1}$. We will show $i_{t+1} \ge \alpha^t$ (note this would imply our claim by induction). $k=t+1$ in $(3)$ gives $$i_t \ge \frac{i_1 + \cdots + i_t}{c-1} \ge \frac{1 + \alpha + \cdots + \alpha^{t-1}}{c-1} = \frac{\alpha^t - 1}{(c-1)(\alpha - 1)} $$So it suffices to show \begin{align*} \frac{\alpha^t - 1}{(c-1)(\alpha - 1)} \ge \alpha^t \iff (c-1)(\alpha-1) \le \frac{\alpha^t - 1}{\alpha^t} = 1 - \frac{1}{\alpha^t} \iff (c-1)(\alpha -1) + 1 - \frac{1}{\alpha^t} \le 0 \end{align*}Indeed, \begin{align*} (c-1) (\alpha -1) + 1 - \frac{1}{\alpha^t} &= (\alpha -1) \left( (c-1) - \left( \frac{1}{\alpha} + \frac{1}{\alpha^2} + \cdots + \frac{1}{\alpha^{t-1}} \right) \right) \\ &\le (\alpha -1) \left(c-1 -\left( \frac{1}{\alpha} + \frac{1}{\alpha^2} + \cdots + \frac{1}{\alpha^c} \right) \right) \le 0 \end{align*}This proves our claim. $\square$ Claim 3 (Key Result): For large $t$, all of $b_1,b_2,\ldots,b_{\alpha^t}$ are at most $c(t+1)$. Proof: Observe that $b_{i_{n+1} + 1} - b_{i_n + 1} \le c ~ \forall ~ n \ge 1$. As $b_{i_1 + 1} = b_2 \le b_1 + c$, so it follows $$b_{i_m + 1} \le b_1 + cm ~~ \forall ~ m \ge 1$$Now $i_{t+1} + 1 \ge \alpha^t+1$, thus all of $b_1,b_2,\ldots,b_{\alpha^t-1}$ are $\le b_{i_t + 1} \le b_1 + tc$, and $b_1 + tc \le t(c+1)$ for large $t$. This proves our claim. $\square$ Now let $p_1,p_2,\ldots,p_k$ be all the nice primes, and $\alpha_1,\alpha_2,\ldots, \alpha_k > 1$ be any numbers for which Claim 3 is true. Let $\alpha = \min(\alpha_1,\alpha_2,\ldots,\alpha_k)$. For a large $t$, look at the numbers $$ a_1,a_2,\ldots,a_{\alpha^t} $$By Claim 3 we know that for any $p_i$ adic valuation of any of these numbers is $\le c(t+1)$. It follows number of distinct numbers between them is at most $$ \bigg(c(t+1) + 1 \bigg)^k$$As all $a_i$'s are distinct, so this forces $$ \bigg( c(t+1) + 1 \bigg)^k \ge \alpha^t \qquad \text{for all large } t $$But this is a contradiction as exponential functions grow faster than polynomial functions. This completes the proof. $\blacksquare$ Motivation: The problem isn't even true if $a_i$'s are not given to be distinct, so we somehow had to prove that. So we basically had to prove the $v_p$'s don't grow fast. Now $(1)$ was only interesting for peaks. So it was natural to consider peaks. Now after getting Claim 1, I was sure we only have to use Claim 1 and ignore all other conditions on peaks, which along with $b_{i_{n+1} + 1} - b_{i_n + 1} \le c$ would give us the sequence $\{b_k\}_{k \ge 1}$ doesn't grow fast. So we only had to prove Claim 2. Basically, we conjecture $i_k \ge \alpha^{k-1}$ for all $k$ (for some $\alpha > 1$). We then find the sufficient conditions on $\alpha$ for which we can prove this by induction. The two equations in proof of Claim 2 were precisely those. Now we had some problems like it might happen $i_1 = i_2 = 1$, but that was easy to fix by showing $i_k \ge \alpha^{k-1}$ for large $k$.
06.04.2022 16:58
The answer is no such $C$. Let $p$ be some prime, and let $\nu_p(C)=c$, $x_i=\nu_p(a_i)$ for $i \geq 1$. Viewing the divisibility condition in $p$-adic terms only, it is equivalent to $$kx_{k+1} \leq kc+x_1+\cdots+x_k.$$Let $(H_n)$ denote the sequence of harmonic numbers. The crux of the problem is the following: Claim: $x_n-x_1 \leq cH_{n-1}$. Proof: Shifting $(x_i)$ doesn't modify the truth of the condition, so WLOG let $x_1=0$. We now use strong induction: \begin{align*} (n-1)c+x_1+\cdots+x_{n-1}&\leq(n-1)c+c\left(\left(\frac{1}{1}\right)+\left(\frac{1}{1}+\frac{1}{2}\right)+\cdots+\left(\frac{1}{1}+\cdots+\frac{1}{n-2}\right)\right)\\ &=c\left(1+(n-2)+\frac{n-2}{1}+\frac{n-3}{2}+\cdots+\frac{1}{n-2}\right)\\ &=c\left(\frac{n-1}{1}+\frac{n-1}{2}+\cdots+\frac{n-1}{n-2}+\frac{n-1}{n-1}\right)\\ &=c(n-1)H_{n-1}, \end{align*}so $(n-1)x_n \leq c(n-1)H_{n-1} \implies x_n \leq cH_{n-1}$ as desired. The claim implies that $\nu_p(a_n)$ is zero if $p \nmid a_1C$, $O(1)$ if $p \nmid C$ but $p \mid a_1$, and $O(\log n)$ otherwise. Suppose there are $a$ distinct primes dividing $C$ and $b$ distinct primes dividing $a_1$ but not $C$. Then there are $O(1^b(\log n)^a)\sim O((\log n)^a)$ choices for the value of $a_n$—we have $O(1)$ options for $\nu_p(a_n)$ if $p \mid a_1$ and $p \nmid C$, and $O(\log n)$ options for $\nu_p(a_n)$ if $p \mid C$. But $n$ dominates $O((\log n)^a)$, so by Pigeonhole for sufficiently large $n$ there must exist two non-distinct elements of the sequence: contradiction. $\blacksquare$
19.04.2022 23:08
The anwser is, that there is no sequnce, which satisfies the problem. Proof: Now choose any $a_{k+1} < a_{k+2}$. First of all we see, that $a_{k+1}^k \mid C^k a_1 a_2 ... a_k$ $\Rightarrow$ $k \cdot v_p(a_{k+1}) \le k \cdot v_p(C) + v_p(a_1) + v_p(a_2) + ... +v_p(a_k)$ $\Rightarrow$ $k \cdot (v_p(a_{k+1} - v_p(C)) \le v_p(a_1) + v_p(a_2) + ... +v_p(a_k)$ $(1)$. Similarly and because of $a_{k+1} < a_{k+2}$, we get $(k+1) \cdot (v_p(a_{k+2} - v_p(C)) \le v_p(a_1) + v_p(a_2) + ... + v_p(a_{k+1})$ $(2)$, for every prime dividing both sides of the equations. Now we calculate $(2) - (1)$, which is equivalent after some boring basics in arithmetic to $(k+1) \cdot [v_p(a_{k+2}) - v_p(a_{k+1})] \le v_p(C)$ $\Rightarrow$ $v_p((\frac{a_{k+2}}{a_{k+1}})^{k+1}) \le v_p(C)$ $\Rightarrow$ $(\frac{a_{k+2}}{a_{k+1}})^{k+1} \mid C$ $\Rightarrow$ $(\frac{a_{k+2}}{a_{k+1}})^{k+1} \le C$. But this inequality is not true for a large $k$, hence we get a contradiction and we are done
19.06.2022 04:21
PianoPlayer111 wrote: {a_{k+1}})^{k+1} \le C$. But this inequality is not true for a large $k$, hence we get a contradiction and we are done :ninja:[/quote] Why ?If {a_{k+1}})^{k+1} \le C$. isn't very big ,how can explain the numer is larger than C?
19.06.2022 06:35
Nice problem
17.07.2023 06:37
How do the $\nu_p$'s grow? Define $S$ as the set of prime divisors of $a_1C$. Note that the given sequence has no prime factors outside of $S$. Let prime $p \in S$ be arbitrary. Denote $b_n = \nu_p(a_n)$ for all positive integers $n$. The given condition rewrites as: \[kb_{k + 1} \leq k\nu_p(C) + b_1 + b_2 + \cdots + b_k.\]Define $s_n = \frac{b_1 + b_2 + \cdots + b_n}{n}$ as the average of the first $n$ elements of our new sequence. Adding $k(b_k + \cdots + b_1)$ to both sides of this inequality and dividing through by $k(k + 1)$ lends us a useful inequality. \[\frac{b_{k+1}+\cdots + b_1}{k+1} \leq \frac{1}{k+1} \nu_p(C) + \frac{b_k + \cdots + b_1}{k}.\]Applying this inequality repeatedly gives us the following inequality. \[s_k \leq \left(\frac{1}{k} + \cdots + \frac{1}{2}\right)\nu_p(C) + s_1.\]Plugging back into the original inequality and bounding the harmonic series gives us: \[b_{k+1} \leq \nu_p(C) + s_k \leq \left(\frac{1}{k} + \cdots + \frac{1}{1}\right)\nu_p(C) + b_1 \leq \ln(k+1) + b_1.\]Something is seriously wrong, and we are very happy about it. Since the above is true for all primes $p$, there are $O((\ln k)^{|S|})$ different possibilities for the values of $a_1, \dots, a_k$. Since \[O((\ln k)^{|S|}) < k\]as $k$ approaches infinity, there must exist two terms in the sequence that are equal.
29.09.2023 17:15
Since $a_{k + 1}^k \mid C^k a_{1}a_{2}\dots a_{k}$ and $C$ is constant, so the set of primes dividing an element in $(a_{n})_{n \ge 1}$is finite. Let $p$ be a arbitrary prime dividing one of $a_{1}, a_{2}, \dots$. Then the divisibility condition becomes $k\nu_{p}(a_{k + 1}) \le k\nu_{p}(C) + \nu_{p}(a_{1}) + \nu_{p}(a_{2}) + \dots + \nu_{p}(a_{k})$. Now consider the following claim: Claim: For $n \ge 2$, we have $\nu_{p}(a_{n}) \le \nu_{p}(a_{1}) + \nu_{p}(C)(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n - 1})$. Proof: Apply strong induction on $n$. Base case is clear. For the induction step, $\nu_{p}(a_{n + 1}) \le \nu_{p}(C) + \frac{1}{n}(\nu_{p}(a_{1}) + \nu_{p}(a_{2}) + \dots + \nu_{p}(a_{n})) \le \nu_{p}(C) + \nu_{p}(a_{1}) + \frac{1}{n}(\nu_{p}(C)((\frac{1}{1}) + (\frac{1}{1} + \frac{1}{2}) + (\frac{1}{1} + \frac{1}{2} + \frac{1}{3}) + \dots + (\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n - 1}))) = \nu_{p}(a_{1}) + \nu_{p}(C)(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n})$. $\blacksquare$ Since the set of primes dividing an element in $(a_{n})_{n \ge 1}$is finite, let $a$ be a number of elements in the set of primes dividing an element in $(a_{n})_{n \ge 1}$. Then taking large $N$, we see that there are most $(O(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{N})^k) = O((\ln N)^k) < N$ distinct values in $a_{1}, a_{2}, \dots, a_{N}$, a contradiction. Therefore there are no such $C$. $\blacksquare$