There is a game. The magician let the participant think up a positive integer (at least two digits). For example, an integer $ \displaystyle\overline{a_1a_2 \cdots a_n}$ is rearranged as $ \overline{a_{i_1}a_{i_2} \cdots a_{i_n}}$, that is, $ i_1, i_2, \cdots, i_n$ is a permutation of $ 1,2, \cdots, n$. Then we get $ n!-1$ integers. The participant is asked to calculate the sum of the $ n!-1$ numbers, then tell the magician the sum $ S$. The magician claims to be able to know the original number when he is told the sum $ S$. Try to decide whether the magician can be successful or not.
Problem
Source: China TST 2002 Quiz
Tags: combinatorics unsolved, combinatorics
19.10.2016 11:20
The answer is affirmative,By considering size,we can get n,then by module 9,we can know $\sum a_{i}$,thus the answer.
28.10.2019 05:26
We claim that the answer is yes, the magician can succeed. It suffices to show that for any $x, y \in \mathbb{N}_{ \ge 10}$, the sum that the participant computes is not the same. Case 1. $x, y$ have different numbers of digits. Suppose that $x, y$ have $m, n$ digits respectively, where $m < n$. Note that the participant's computed sum for $x$ is at most $(m! - 1) (10^m - 1)$, while that for $n$ is at least $((n-1)! - 1)(10^{n-1})$. Since $10^{n-1} > 10^m$, $(n-1)! \ge m!$, we're done in this case. Case 2. $x, y$ have the same number of digits If that number of digits is $2$, we are easily done. Let's prove it when the number of digits is $3.$ We want to show that $222(s(x)) - x \neq 222(s(y)) - y$, where $s(n)$ denotes the sum of the digits of $n$. Suppose not. We must clearly have that $x \equiv y$ (mod $222$). Hence, $3 | x-y \Rightarrow 3| s(x) - s(y) \Rightarrow 666| x - y \Rightarrow 9| s(x) - s(y) \Rightarrow 1998 | x-y.$ Hence $x = y$, contradiction. Now let's show it when the number of digits is $4.$ We want to show that $6666(s(x)) - x \neq 6666(s(y)) - y.$ Suppose not. Then $6666 | x-y \Rightarrow 3 | s(x) - s(y) \Rightarrow 19998 | x-y \Rightarrow x = y$, contradiction. If they both have $\ge 5$ digits, say they have $t \ge 5$ digits, then we must have $(t-1)! \frac{10^t-1}{9} | x-y$. This easily implies $x = y$ for $t \ge 5$. As we've exhausted all cases, we're done. $\square$