Let $S$ be the set of $10$-tuples of non-negative integers that have sum $2019$. For any tuple in $S$, if one of the numbers in the tuple is $\geq 9$, then we can subtract $9$ from it, and add $1$ to the remaining numbers in the tuple. Call thus one operation. If for $A,B\in S$ we can get from $A$ to $B$ in finitely many operations, then denote $A\rightarrow B$. (1) Find the smallest integer $k$, such that if the minimum number in $A,B\in S$ respectively are both $\geq k$, then $A\rightarrow B$ implies $B\rightarrow A$. (2) For the $k$ obtained in (1), how many tuples can we pick from $S$, such that any two of these tuples $A,B$ that are distinct, $A\not\rightarrow B$.
Problem
Source: China TST 2019 Test 2 Day 1 Q2
Tags: combinatorics, algorithms
Math1Zzang
17.03.2019 16:22
Answer. We claim that the smallest integer $k$ is $8$.
Proof.
1. $k\leq 7$ does not satisfy the condition
Set the counterexample as $A=\left(1956,7,7,7,7,7,7,7,7,7\right), B=\left(1938,9,9,9,9,9,9,9,9,9\right)$
It is trivial that $A\rightarrow B$. Now we show $B\not\rightarrow A$.
If $B\rightarrow A$, then each of the $i$th entry for $2\leq i\leq 10$ should be subtracted by $9$ at least once.
For $2\leq i\leq 10$, suppose the last time $i$th entry was subtracted by $9$ was the $f\left(i\right)$th move.
Now think of $i$ such that $f\left(i\right)$ is minimum.
Then after the $f\left(i\right)$th move, for all $j\left(2\leq j\leq 10, j\neq i\right)$ there was a move such that
the $j$th entry was subtracted by $9$, and the other entries were added by $1$.
Therefore in the final tuple, the number in the $i$th entry should be greater than or equal to $8$, a contradiction.
2. $k=8$ does satisfy the condition
Denote the number in the $i$th entry as $x_{i}$. We first notice that for any $i$ and $j$, $x_{i}-x_{j}$ mod $10$ is conserved.
Denote the number in the $i$th entry of $A$ as $a_{i}$. $WLOG$ we'll assume $8\leq a_{1}\leq a_{2}\leq \cdots \leq a_{10}$.
Now we will prove that for each $i$, we can operate on $B$ so that $x_{1}-a_{1}=x_{2}-a_{2}= \cdots =x_{i}-a_{i}$.
We prove this by induction on $i$. The initial condition is trivial. Suppose we have $x_{1}-a_{1}=x_{2}-a_{2}= \cdots =x_{i}-a_{i}$.
Since $x_{i}-x_{j}$ mod $10$ is conserved and $A\rightarrow B$, $x_{i}-a_{i}$ mod $10$ should be equal for all $i$.
Repeat operations on $x_{1},x_{2}, \cdots ,x_{i+1}$ equal times so that $x_{1}$ or $x_{i+1}\leq 8$.
If $x_{i+1}-a_{i+1}<x_{i}-a_{i}$, then let $t=\frac{\left(x_{i}-a_{i}\right)-\left(x_{i+1}-a_{i+1}\right)}{10}$
After some calculations, we know we can subtract $9$ from all $x_{j}\left(j\neq i+1\right)$ $t$ times,
including operations subtracting $9$ from all $x_{j}\left(j\geq i+2\right)$ is necessary,
while not subtracting $9$ from $x_{i+1}$, and we're done.
If $x_{i+1}-a_{i+1}>x_{i}-a_{i}$, we proceed similarly, and I'll skip because of laziness.
I have practically proved in the upper solution that $A\rightarrow B$ is equivalent to $a_{1}-b_{1}\equiv a_{2}-b_{2}\equiv \cdots \equiv a_{10}-b_{10} \pmod {10}$.
I'll leave the details to the readers.
And we can easily count the number of tuples that cannot be derived from each other...
Just be careful that $x_{1}+x_{2}+\cdots +x_{10}=2019\equiv 9 \pmod {10}$
If my calculations are correct, I get $10^{8}$.
CANBANKAN
20.12.2020 08:42
Nice problem that features constructive algorithms and invariants.
(1) I claim the answer is $k=8$.
First I show $k=8$ works. Let $(a_i)_{i=1}^{10}$ be the elements of $A$, and define $(b_i)_{i=1}^{10}$ similarly. I instead prove that as long as $a_i-a_j\equiv b_i-b_j(\bmod\; 10)$ then it is possible to go from $A\rightarrow B$ if $A,B\in S$ and have minimum number $\ge 8$. This is sufficient because the operation preserves $a_i-a_j(\bmod\; 10)$.
Define toggling $i$ to be the operation that decrements $a_i$ by $9$ and increments $a_j\forall j\ne i$ by 1. We first toggle $a_i$ as long as $a_i-b_i\ge 9$. Let $f(A)=\sum\limits_{i=1}^{10} |a_i-b_i|$, and I claim it strictly decreases after each operation. Note after each such operation, if I toggled at $i$, $|a_i-b_i|$ decrements by 9. If it doesn't strictly decrease, it follows that all the other $|a_i-b_i|$ incremented by 1, which implied $a_i-b_i\ge 0$ for all $i$ before toggling, which is absurd. Therefore, we would arrive at a position where $a_i-b_i\le 8$ for all $i$.
If $a_i-b_i=0$ for all $i$, we're trivially done. Otherwise, note $a_j-a_i\equiv b_j-b_i(\bmod\; 10)$, so $a_j-b_j\equiv a_i-b_i(\bmod\; 10)$. Let $x_i=a_i-b_i$. Note $x_1\equiv x_2\equiv \cdots \equiv x_{10}(\bmod\; 10)$ and all the positive $x_i$s take on the same value, call $v$. Let $m$ be the number of solutions to $x_i=v$.
The negative $x_i$s are at most $v-10$, so it easily follows that $m+v\ge 10$ (1).
We call a round of fire toggling $i$ for all $x_i>0$. After the round of fire, if $x_i>0, x_i=m+v-10$, and otherwise, $x_i$ increments by $m$. Note a round of fire holds because $a_i>b_i>8$. Notice at any moment, (1) holds, so $m$ never decreases. When $m+v=10$, in which case there would be no positive elements and $x_i=0$ for all $i$ as $\sum x_i=0$. Otherwise, we can see no negative numbers became positive, but it is clear $m+v$ decreases. As long as $x_i$ is not a zero sequence, we bring out a round of fire. Since the smallest negative number in the sequence always increases, the process is finite and we are done.
Now I show $k=7$ fails.
Let $A=(7,7,7,7,7,7,7,7,7,1956), B=(8,8,8,8,8,8,8,8,8,1947)$. By toggling $10$, $A\rightarrow B$. I claim $B\not\rightarrow A$. I claim at any moment, there exist at least 2 numbers that are $\ge 8$. In fact, it is true that for $1\le i\le 10$, at least $i$ numbers are at least $\ge 10-i$.
Notice how the size of the elements is similar to the number of elements. Let $f(i)$ be the last time $a_i$ is toggled, and $f(i)=0$ if it hasn't been toggled. In the first ten moves, this is clearly impossible. Then note $a_j\ge \max_{i=1}^{10} f(i)-f(j)$, which is good enough because there exist $j\ne k, f(j)\le f(k)\le \max_{i=1}^{10} f(i)-8$.
(2). Let $d_i\equiv a_{i+1}-a_i(\bmod\; 10), 0\le d_i\le 9$ for $1\le i\le 9$. A sequence is uniquely determined by $d_i$. We have shown that all sequences with same $d_i$ are reachable to each other in (1), so the answer is simply the number of 9-tuples $(d_1,\cdots,d_9)$ where $0\le d_i\le 9$ and $\sum\limits_{i=1}^9 (10-i)d_i\equiv -1(\bmod\; 10)$.
For each $(d_1, \cdots,d_8)$, there is a unique $d_9$, so the answer is $10^8$.
guptaamitu1
11.01.2022 14:52
We call a tuple bad if for some $i$, it contains $i+2$ numbers which are all $\le i$ and good otherwise. For $A = (a_1,\ldots,a_{10})$, define $f_i(A)$ obtained by toggling $a_i$ (note that $f_i(A)$ is defined only when $a_i \ge 9$) and $f^{-1}_i(A)$ as one would expect (which is defined only when all elements of $\{a_1,\ldots,a_{10}\} \setminus \{a_i\}$ are $\ge 1$). Moreo precisely,
\begin{align*}
f_i(A) = (a_1+1,\ldots,a_{i-1} + 1,a_i - 9,a_{i+1} + 1,\ldots,a_{10} + 1 ) \\
f^{-1} _i(A) = (a_1-1,\ldots,a_{i-1}-1,a_i + 9,\ldots,a_{10} - 1)
\end{align*}Let sets $f(A) = \{f_1(A),\ldots,f_{10}(A) \}$ and $f^{-1}(A) = \{f^{-1}_1(A),\ldots,f^{-1}_{10}(A)\}$. Also, we say $B$ is reachable from $A$ if $A \to B$.
Claim 1: If $A$ is bad, then all elements of $f^{-1}(A)$ are bad.
Proof: Note that $f^{-1}$ decreases all but $1$ numbers of $A$ by $1$, implying our claim. $\square$
Corollary 2: If $A$ is good, then any tuple obtained by applying $f$ repeatedly on $A$ is good.
Claim 3: If $A$ is good, then $A$ is reachable from all elements of $f(A)$.
Proof: We will show $A$ is reachable from $f_1(A)$. WLOG $a_2 \le \cdots \le a_{10}$. As $A$ is good, so $a_{2} \ge 0,a_3 \ge 1, \ldots,a_{10} \ge 8$. Then,
$$A = f_1(f_2 ( \cdots f_{9} (f_{10}(A)) \cdots ))$$where everything is defined because of the inequalities. $\square$
$\boxed{ \textbf{Key Claim:}}$ For good tuples $A = \{a_1,\ldots,a_{10}\},B = \{b_1,\ldots,b_{10}\}$, $B$ is reachable from $A$ iff $(a_1-a_2,a_1-a_3,\ldots,a_1 - a_{10})$, $(b_1-b_2,b_1-b_3,\ldots,b_1-b_{10})$ are equal modulo $10$.
Proof: One direction just follows by a simple invariant, now we prove the other direction. Because of Claim 3, it suffices to show by applying $f$ repeatedly to both $A,B$, we can make them equal. First we may assume $|a_i - b_i| \le 8$ for all $i$, as otherwise say if $a_1 \ge b_1 + 9$, then we change $A \to f_1(A)$ and observe that value of $\sum |a_i - b_i|$ has decreased (this is not hard to see). Because of the original congruence, for some $0 \le u,v \le 8$ with $u + v = 10$, we have $a_i - b_i = u$ for $v$ values of $i$ and $b_i - a_i = v$ for $u$ values of $i$. WLOG $u \ge v$, $a_1 - b_1 = \cdots = a_v - b_v = u$ and $b_1 \le b_2 \le \cdots \le b_v$. As $B$ is good, so $b_1 \ge 0,b_2 \ge 1,\ldots,b_v \ge v-1$. Then,
$$f_1(f_2( \cdots f_{v-1}(f_v(A)) \cdots )) = B$$where everything is again defined. This proves our claim. $\square$
$k=7$ doesn't work as we can consider
$$(\underbrace{7,\ldots,7}_{9 \text{ times }} , \text{blah}) \qquad , \qquad (\underbrace{8,\ldots,8}_{9 \text{ times }} , \text{blah})$$where the second tuple is clearly reachable from the first, while the first isn't reachable from second as it is good while the first one is bad.
Now $k=8$ works for sure as any tuple with all elements $\ge 8$ is good.
For $(2)$, note that $(a_1-a_2,\ldots,a_1 - a_9)$ modulo $10$ has $10^8$ choices, and moreover it will determine the tuple uniquely as $\sum (a_1 - a_i) \equiv 9$ (mod 10). We conclude that
Answer of $(1)$ is $\boxed{k=8}$.
Answer of $(2)$ is $\boxed{10^8}$.