Find all positive integer $n(\ge 2)$ and rational $\beta \in (0,1)$ satisfying the following: There exist positive integers $a_1,a_2,...,a_n$, such that for any set $I \subseteq \{1,2,...,n\}$ which contains at least two elements, $$ S(\sum_{i\in I}a_i)=\beta \sum_{i\in I}S(a_i). $$where $S(n)$ denotes sum of digits of decimal representation of $n$.
Problem
Source: 2021ChinaTST test4 day1 P3
Tags: number theory, sum of digits, decimal representation, China TST, China, number theory proposed
24.04.2021 15:26
For $n=2$ Consider 2 numbers $999\hdots 9999\text {(with m 9's)}$ $111\hdots 1111\text {(with k 1's)}$ $\textbf {LHS} $ sum evaluates to $k. $ $\textbf {RHS} $ sum evaluates to $(k+9m) . $ Let $\beta=\frac {a}{b}< 1$ take $9a=k $ and $(b-a)=m. $ $n>2$ Split $11111\hdots 1111$ into many numbers. Eg. $1111$ splits into $1000,100\hdots$ Then double or triple $m,k \implies\,\text{same values of}\, \beta $
10.05.2021 14:27
bump
10.05.2021 14:41
Physicsknight wrote: For $n=2$ Consider 2 numbers $999\hdots 9999\text {(with m 9's)}$ $111\hdots 1111\text {(with k 1's)}$ $\textbf {LHS} $ sum evaluates to $k. $ $\textbf {RHS} $ sum evaluates to $(k+9m) . $ Let $\beta=\frac {a}{b}< 1$ take $9a=k $ and $(b-a)=m. $ $n>2$ Split $11111\hdots 1111$ into many numbers. Eg. $1111$ splits into $1000,100\hdots$ Then double or triple $m,k \implies\,\text{same values of}\, \beta $ I don't get your solution at all when n >2. Can you write more clearly?
24.05.2021 13:02
For $n\le 10$, all the rational $\beta \in (0,1)$ satisfies. Just let (these Sth else depend on $\beta$) $a_1=9......990......01......0......01$ and Sth else $a_2=0......019......99......0......01$ and Sth else ........ $a_n=0......010......01......9......99$ and Sth else I believe there is no that kinds of $\beta$ when $n\ge 11$
08.06.2021 12:53
Any solution?
07.01.2022 03:20
Proof of n=11 failing. Let $B$ be the rightmost bit such that $a_i+a_j$ carry for some $i,j$. (1) Let $b_i$ denote $a_i$'s $B$th bit. WLOG, $b_1\ge b_2\ge \cdots \ge b_{11}$. We are given that $b_1+b_2\ge 10$. All capital letters denote subsets of $\{1,\cdots,11\}$ with cardinality at least 2. First, if $|S|, |T|\ge 2$ and $S\cap T=\emptyset$ then $\sum\limits_{j\in S} a_j$ and $\sum\limits_{k\in T} a_k$ cannot carry because $S(\sum\limits_{j\in S} a_j)+S(\sum\limits_{k\in T} a_k)=S(\sum\limits_{j\in S} a_j+\sum\limits_{k\in T} a_k)$. However, I claim there must exists two such sets that carry at this bit. First, note there is no carrying for two-element subsets from lower bits to upper ones other than $B$ to $B+1$, so if we have $(b_1+b_{11})+(b_2+b_{10})>10$ then we must have $\max\{b_1+b_{11}, b_2+b_{10}\} \ge 10$. In particular, $b_1+b_{10}\ge 10$ so $b_{10}\ge 1$. Also, the smaller bits for a subset of $k$ elements can contribute at most $\lfloor \frac{k-1}{2} \rfloor$ to the $B$th bit of the sum of the elements in this subset. Let $B(S)=$ remainder of $\sum\limits_{j\in S} b_j$ when divided by 10. If $r_j$ is the remainder when $a_j$ is divided by $10^{B+1}$, then $B'(S)=\lfloor 10^{-B} \sum\limits_{j\in S} r_j \rfloor$. Note $B$ ignores the contribution due to lower bits but $B'$ actually takes care of it. By (1) we know for two element subsets $S$, $B(S)=B'(S)$. If we consider the sum of 5 disjoint 2-element subsets, there exists $B(S_1)+B(S_2)+B(S_3)+B(S_4)+B(S_5)=B'(S_1)+B'(S_2)+B'(S_3)+B'(S_4)+B'(S_5)\ge 10$. (If this is false, then the only possibility for $b_i$ is $9,1,1,1,1,1,1,1,1,1,0$, which falls to $(b_1+b_{11}) + (b_2+b_3)$; we need $n=11$ to pass this step because $9,1,1,1,1,1,1,1,1$ seems okay for $n=10$) If $S\cap T=\emptyset$, $B'(S)+B'(T)<10$ and $B'(S\cup T)\ge 10$ we are done by picking $S,T$. Therefore, $B(S_1\cup S_2)<10$ and we apply the same argument on $S_1\cup S_2, S_3$, then $S_1\cup S_2\cup S_3, S_4$... This implies that $B'(S_i)+B'(S_j)\ge 10$ for all pairs of disjoint 2-element subsets $(S_i,S_j)$. We also know for 2-element subsets, $B'(S)=B(S)$. Therefore, $B(S)+B(T)\ge 10$ for all $S\cap T=\emptyset$. In short, $b_8+b_9+b_{10}+b_{11}\ge 10$. Now, if there are no carries to $(b_8+b_{11}) + (b_9+b_{10})$ then $\max\{b_8+b_{11}, b_9+b_{10}\} \ge 10$. Furthermore, this implies $b_8\ge 5$. Let $c_i=b_i-5$ for $1\le i\le 8$. If $c_i+c_j+c_k+c_l\ge 10$ then $40\ge b_i+b_j+b_k+b_l\ge 30$. It follows that $10\le b_i+b_j, b_k+b_l < 20$ so $B(\{i,j\}) > B(\{k,l\})$, false. Similarly, $c_i+c_j+c_k\ge 5$. This implies $b_4=b_5=b_6=b_7=7$ and thus $B'(\{4,5,6,7\}) \in \{8,9\} (\bmod\; 10)$. Now, if $b_9\ge 2$ then $\{6,7,9\}, \{4,5\}$ carry. However, $b_4+b_9>b_8+b_{11}\ge 10$, contradiction.
07.01.2022 03:42
Motivation for the above solution: I tried to solve the binary case and realized all $\beta$ work for $n=3$. For $n=4$ we have the non-carrying property. I thought of $a_1+a_2, \cdots, a_3+a_4$ as subsets $X_{12}, \cdots, X_{34}$ and took some intersections. Unfortunately this not only doesn't work but also not generalize. Then I thought of a minimal example. If $a_i$ is nonzero on a fixed bit, then it can be 0000, 1110, 1000, 1111. I figured out what happens with 0000 and 1000 as the last "nontrivial" combination, but 1110 and 1111 are SO CUMBERSOME. I flailed around but was not able to reach anything conclusive. A big reason is that I have few sets satisfying "no carrying" property (in particular, what if $a_1+a_2+a_3+a_4$ is 1 at that bit? Then $a_1+a_2, a_3+a_4$ may never carry...). But going back to base 10, this works because there are SO MANY SUBSETS that satisfy this property... sometimes small numbers are anomalies after all.
07.01.2022 17:48
Comment: Probably the hardest NT I've ever completed. For $n \le 10,$ all $\beta \in (0,1)$ work. It suffices to construct for $n=10.$ First, let $\beta = \frac{p}{q}$ where $\gcd(p,q) = 1.$ Start off defining $$a_1 = \overbrace{99 \dots 9}^{k \text{ digits}}\overbrace{00 \dots 1}^{k \text{ digits}} \dots \dots \overbrace{00 \dots 1}^{k \text{ digits}} $$$$a_2 = \overbrace{00 \dots 1}^{k \text{ digits}}\overbrace{99 \dots 9}^{k \text{ digits}} \dots \dots \overbrace{00 \dots 1}^{k \text{ digits}} $$$$ \dots \dots $$$$a_{10} = \overbrace{00 \dots 1}^{k \text{ digits}}\overbrace{00 \dots 1}^{k \text{ digits}} \dots \dots \overbrace{99 \dots 9}^{k \text{ digits}},$$where there are $10$ blocks of $k$ digits, each integer has one of these blocks (different for each one) being $99 \dots 9$ and have the rest as $00 \dots 1.$ Now for any positive integer $l,$ we may add on the end of each $a_i$ a string of some large length (fixed over all $a_i$) with digit sum $l,$ making sure to keep no two strings from carrying with each other. This results in a $\beta$ of $$\frac{18+l}{18+18 \times k+l}.$$If we set $k = q-p$ and $l = 18(p-1)$ this works. $\square$ For $n = 11$ or above, no $\beta \in (0,1)$ exists. The key idea is that for two disjoint subsets $I_1, I_2 \subset \{1,2, \dots 11\},$ $$S\left(\sum_{i\in I_1}a_i\right) + S\left(\sum_{i\in I_2}a_i \right) = \beta \sum_{i \in I_1 \cup I_2} S(a_i) = S\left(\sum_{i\in I_1 \cup I_2}a_i \right).$$So when you add $\sum_{i\in I_1}a_i$ and $\sum_{i\in I_2}a_i,$ no carrying occurs. Look at the smallest digit $D$ where $a_i + a_j$ carry for some $i,j.$ This must exist otherwise $\beta = 1.$ We claim there are $I_1,I_2$ where $\sum_{i\in I_1}a_i$ and $\sum_{i\in I_2}a_i,$ carry at $D,$ causing contradiction. Call $a_i$'s $D$th digit $d_i.$ Suppose WLOG $d_1 \ge d_2 \ge \dots \ge d_{11},$ where $d_1 + d_2 \ge 10.$ Take $I_1 = \{1,10\}$ and $I_2 = \{2,11\};$ noting $d_1+d_2+d_{10}+d_{11} \ge 10,$ we have $d_1 +d_{10} \ge 10.$ So $d_{10} \ge 1$ and only one digit can be $0.$ Call a pair of digits $d_i, d_j$ cool if $d_i+d_j$ has units digit $>1.$ Greedily choose cool pairs until there are no more left. Let's say we have chosen $0 \le m \le 5$ cool pairs leaving $11-2m$ digits unused, no two of which are cool. If there are $3$ or more, one of them must be $0$ or $5.$ Suppose $0$ is unused. If some unused digit is $>1,$ it forms a cool pair with $0.$ Otherwise, two unused digits are $1,$ but then they are cool. So $5$ must be unused. No pair of cool unused numbers exists, so either the unused digits are all $5$s, or all $5$s and one $6.$ Greedily group together triples of unused digits. Each of these sum to $5$ or more. Verify $$5 \left \lfloor \frac{11-2m}{3} \right \rfloor + 2m \ge 10.$$So we have disjoint groups $B_1,B_2, \dots B_k$ of multiple digits each, where if we let their sums have units digits of $b_1,b_2, \dots b_k$ respectively, we have $b_1+b_2 + \dots + b_k \ge 10.$ Take the smallest index $i$ where $b_1+ \dots + b_i \ge 10.$ Put $B_1$ through $B_{i-1}$ in $I_1$ and $B_i$ in $I_2;$ the end. $\square$
08.01.2022 18:14
Does anyone know the motivation for guessing n=10? I have no idea how to figure out the answer.