Does there exist two infinite positive integer sets $S,T$, such that any positive integer $n$ can be uniquely expressed in the form $$n=s_1t_1+s_2t_2+\ldots+s_kt_k$$,where $k$ is a positive integer dependent on $n$, $s_1<\ldots<s_k$ are elements of $S$, $t_1,\ldots, t_k$ are elements of $T$?
Problem
Source: China Team Selection Test 2016 Test 2 Day 2 Q5
Tags: number theory, algebra
21.03.2016 10:50
I have a question, since it doesn't say anything in the problem. Can $S$ and $T$ have some common elements ?
21.03.2016 11:09
Yup it must have else we can't represent $1$
21.03.2016 15:12
The answer is yes. We say that a pair of finite sets $(S,T)$ is $N$-good if every integer $m$ satisfying $0\leq m<N$ can be uniquely expressed in the form \[m=s_1t_1+s_2t_2+\cdots+s_kt_k, \]where $S=\{s_1,s_2,\ldots,s_k\}$ and $t_i\in T$, and all numbers expressible in that form is $<N$. Note that $(\{1\},\{0,1\})$ is 2-good. We claim that if $(S,T)$ is $N$-good, then there exists sets $S',T'$ such that $S\subset S',T\subset T'$, and $(S',T)$ and $(S,T')$ are both $N^2$-good. Let $S'=S\cup\{xN\mid x\in S\},T'=\{xN+y\mid x,y\in T\}$. Then every number $m<N^2$ can be expressed as $p+Nq$ where $0\leq p,q<N$, hence it can be uniquely expressed as \[m=s_1t_1+\cdots+s_kt_k+N(s_1u_1+\cdots+s_ku_k), \]where $S=\{s_i\},t_i,u_i\in T$. Thus it is uniquely expressible as $\sum s_i(t_i+Nu_i)$ and $\sum s_it_i+\sum Ns_iu_i$. It is easy to show only numbers $<N^2$ is expressible in that form. Thus our claim is proven. Now letting $S_0=\{1\},T_0=\{0,1\}$, we can define $S_i,T_i$ for $i=1,2,\ldots$ such that $(S_i,T_i)$ and $(S_{i+1},T_i)$ are something-good and $S_0\subset S_1\subset\ldots$ and $T_0\subset T_1\subset\ldots$. Finally, let $S=\bigcup_{i=0}^{\infty}S_i$ and $T=\bigcup_{i=0}^{\infty}T_i-\{0\}$ and we are done.
22.03.2016 15:20
The answer is yes! Firstly, let $K$ be the set of non-negative integers expressible as only 0's and 1's in base 4. Then clearly, all non-negative $k$ can be uniquely expressed in the form $k=a+2b$, where $a,b \in K$. Now let $S=\{2^a|a\in K\}$ and $T'=\{2^{2b}|b\in K\}$. Furthermore, let $T$ be the powerset of $T'$, i.e. $T=\left\{\sum_{x\in A} x|A\subseteq T\right\}$. Then it is clear that $S$ and $T$ satisfy the conditions of the problem.
10.03.2017 17:30
oneplusone wrote: The answer is yes. We say that a pair of finite sets $(S,T)$ is $N$-good if every integer $m$ satisfying $0\leq m<N$ can be uniquely expressed in the form \[m=s_1t_1+s_2t_2+\cdots+s_kt_k, \]where $S=\{s_1,s_2,\ldots,s_k\}$ and $t_i\in T$, and all numbers expressible in that form is $<N$. Note that $(\{1\},\{0,1\})$ is 2-good. We claim that if $(S,T)$ is $N$-good, then there exists sets $S',T'$ such that $S\subset S',T\subset T'$, and $(S',T)$ and $(S,T')$ are both $N^2$-good. Let $S'=S\cup\{xN\mid x\in S\},T'=\{xN+y\mid x,y\in T\}$. Then every number $m<N^2$ can be expressed as $p+Nq$ where $0\leq p,q<N$, hence it can be uniquely expressed as \[m=s_1t_1+\cdots+s_kt_k+N(s_1u_1+\cdots+s_ku_k), \]where $S=\{s_i\},t_i,u_i\in T$. Thus it is uniquely expressible as $\sum s_i(t_i+Nu_i)$ and $\sum s_it_i+\sum Ns_iu_i$. It is easy to show only numbers $<N^2$ is expressible in that form. Thus our claim is proven. Now letting $S_0=\{1\},T_0=\{0,1\}$, we can define $S_i,T_i$ for $i=1,2,\ldots$ such that $(S_i,T_i)$ and $(S_{i+1},T_i)$ are something-good and $S_0\subset S_1\subset\ldots$ and $T_0\subset T_1\subset\ldots$. Finally, let $S=\bigcup_{i=0}^{\infty}S_i$ and $T=\bigcup_{i=0}^{\infty}T_i-\{0\}$ and we are done. Your solution is wrong,you can write $S_1,T_1$ and find your claims all wrong…
03.05.2021 23:36
The main motivation is binary. This is the solution from my stream. Let $A \cdot B = \{ ab: a\in A, b\in B\}, A+B=\{a+b: a\in A, b\in B\}$ We consider the following process: start with $S=\{1,2\}$ and $T=\{0,1,4,5\}$ (0's don't affect the sum anyways). This can form all positive numbers less than $2^4$. $S$ and $T$ alternatively get their moves. When it's $S$ to move and we can form all positive integers less than $2^k$, then we consider $S'=S\cdot \{1,2^k\}$. $S'$ and $T$ can form all positive integers less than $2^{2k}$. Why? Suppose $x<2^{2k}$ and let $x=q2^k+r$ where $0\le q,r<2^k$. Then we form $q$ , except for each number uses the new set, and we form $r$, except for each number uses the old set. For example, if $q=\sum s_it_i$ and $r=\sum w_iz_i$ then $q2^k+r = \sum (2^k\cdot s_i)t_i + \sum w_iz_i$, where $(s_i), (w_i)$ are distinct elements of $S$ and $(t_i), (z_i)$ are elements of $T$. We will reassign $S'$ to $S$. When it's $T$ to move, then we define $T'= T+ (T\cdot \{2^k\})$, i.e., $T$ becomes $\{a+2^kb: a,b\in T\}$. This allows us to jump from $\mathbb{N}_{<2^k}$ to $\mathbb{N}_{<2^{2k}}$ because if I break each $t_i=2^ku_i+v_i$ then our sum becomes $\sum (s_i (2^ku_i+v_i))=2^k\sum (s_iu_i) + \sum (s_iv_i)$. Since $\sum (s_iu_i)$ and $\sum (s_iv_i)$ both have range $\mathbb{N}_{<2^k}$, this works. Since this process is indefinite, the conclusion follows.