Let $({{A}_{n}})_{n=1}^{\infty }$ and $({{a}_{n}})_{n=1}^{\infty }$ be sequences of positive integers. Assume that for each positive integer $x$, there is a unique positive integer $N$ and a unique $N-tuple$ $({{x}_{1}},...,{{x}_{N}})$ such that $0\le {{x}_{k}}\le {{a}_{k}}$ for $k=1,2,...N$, ${{x}_{N}}\ne 0$, and $x=\sum\limits_{k=1}^{N}{{{A}_{k}}{{x}_{k}}}$. (a) Prove that ${{A}_{k}}=1$ for some $k$; (b) Prove that ${{A}_{k}}={{A}_{j}}\Leftrightarrow k=j$; (c) Prove that if ${{A}_{k}}\le {{A}_{j}}$, then $\left. {{A}_{k}} \right|{{A}_{j}}$.
Problem
Source: Turkish NMO 1996, 1. Problem
Tags: number theory proposed, number theory
11.12.2017 22:13
Here is a solution, but I am still not fully sure that part $c)$ is bug-free. Anyways, there it goes. First, note that for each $A_n$, we have the following representation: $(\underbrace{0,0,\dots,0}_{n-1},1)$. From the preamble of problem, this must be the unique representation, and the key tool to the contradiction argument of below. $a)$ Let $x=1$, and $N^*$ be the corresponding, unique positive integer associated to $1$. Then, we claim that $A_{N^*}=1$. Indeed, $$ 1=A_{N^*} x_{N^*} + \sum_{k=1}^{N^*-1}A_k x_k\geq A_{N^*}x_{N^*}\geq A_{N^*} \geq 1. $$Hence, $A_{N^*}=1$. $b)$ Now, assume that there exists two distinct (positive) integers $k$ and $j$ such that $A_k=t=A_j$. Then, $t$ can be expressed in two different ways: $(\underbrace{0,0,\dots,0}_{j-1},1)$, $(\underbrace{0,0,\dots,0}_{k-1},1)$, a contradiction. $c)$ Suppose that $A_k\leq A_j$ but $A_k \nmid A_j$. Apply the division algorithm, and write $A_j = mA_k + r$, where $0<r \leq A_k-1$. We have two distinct cases: Case 1: $m\leq a_k$. In this case, we claim that, $A_j$ has two different representations, hence a contradiction. First one is already mentioned. For the second one, notice that $1\leq r\leq A_k -1$ has a representation, that doesn't place any weight ($x_k$) on $A_k$. On the other hand, $mA_k$ has the reprensentation $(\underbrace{0,0,\dots,0}_{k-1},m)$. We can safely combine these two (as the representation for $mA_k$ does not use any location other than $A_k$, and the reprensetation of $r$ does not use $k^{th}$ location), and get an alternative representation for $A_j$, hence a contradiction. Case 2: In this case, suppose that $m\geq a_k+1$, hence the previous argument doesn't work directly. First, we will divide the set $A=\{a_k+1,a_k+2,\dots\}$ into the following slots. $$ A=\{a_k+1,a_k+2,\dots,2a_k+1\} \bigcup \{2a_k+2,2a_k+3,\dots,3a_k+2\}\bigcup \{3a_k+3,\dots,4a_k+3\}\bigcup \cdots, $$or equivalently, $$ A=\bigcup_{n=1}^\infty \{na_k+n,\dots,(n+1)a_k+n\}. $$Now, we start by noticing that $(a_k+1)A_k$ does not have any weight at $k^{th}$ location, in its representation. To see why, suppose it has a non-negative weight $t\in \{1,2,\dots,a_k\}$. Then, the number, $(a_k+1-t)A_k$ will have a representation, other than, $(\underbrace{0,0,\dots,0}_{k-1},a_k+1-t)$, again a contradiction. Having proven this, it is a simple matter to show that $(a_k+2)A_k$ has a weight $1$ at $A_k$ (simply place $1$ at $k^{th}$ location, and put the rest of weights, according to the representation of $(a_k+1)A_k$). If we go in this manner, we see that the weights in each slot, in the representation of $A$ above, is $\{0,1,2,\dots,a_k\}$ (in this order). Now, suppose $A_j = mA_k + r$, $m>a_k$, and $1\leq r\leq A_k-1$. Here is the algorithm to arrive at the contradiction: $\bullet$ First, assign $m$ to its corresponding slot. $\bullet$ Next, let $t$ be the amount, that $m$ is off, by the largest element of the slot that it belongs to (note that, the largest element of any slot, is of form $na_k+(n-1)$ for some $n$). Now, look at $A_j+tA_k$. This has a clear representation, $(\underbrace{0,0,\dots,0}_{k-1},t,\underbrace{0,0,\dots,0}_{j-k-1},1)$. On the other hand, according to representation above, this also admits another representation, where we have $a_k$ at $k^{th}$ location, and the remaining weights are distributed, according to $r$. Notice that since $r<A_k<A_j$, the representation of $r$ does not place any weights at $k^{th}$ and $j^{th}$ locations, and therefore, such two representations are indeed legitimate, and distinct. Hence, we arrive at a contradiction, that $r$ must be 0, i.e. $A_k\mid A_j$ if $A_k\leq A_j$.