Two positive integers $p,q \in \mathbf{Z}^{+}$ are given. There is a blackboard with $n$ positive integers written on it. A operation is to choose two same number $a,a$ written on the blackboard, and replace them with $a+p,a+q$. Determine the smallest $n$ so that such operation can go on infinitely.
Problem
Source: 2018 China Team Selection Test 2 Problem 3
Tags: combinatorics, TST, China TST
08.01.2018 19:33
Answer. The smallest such $n$ is $\tfrac{p + q}{\gcd(p, q)}$. Solution. WLOG $\gcd(p, q) = 1$. Observe that under one operation, the size $p + q$ multiset $S = \{1, \dots, p\} \cup \{1, \dots, q\}$ is transformed into \[\{2, \dots, p\} \cup \{2, \dots, q\} \cup \{p + 1, q + 1\} = S + 1.\]It follows that the operation can be performed ad infinitum. Now suppose that $S$ is a multiset of size less than $p + q$; interpret $S$ as a multiset of elements of $\mathbb{Z}/(p + q)\mathbb{Z}$. We contend that the elements of $S$ must be distinct after sufficiently many moves. Consider a graph with vertex set $\mathbb{Z}/(p + q)\mathbb{Z}$ and edges $x \to x + p$ and $x \to x + q = x - p$ for every $x$. Since $\gcd(p, p + q) = 1$, undirecting edges, this is a connected graph with $p + q$ edges $x \leftrightarrow x + p$. By a standard lemma on chip-firing games, every chip-firing game with less than $p + q$ chips (the number of edges) must terminate.
09.01.2018 00:53
Note that the graph here is a cycle, so the problem is easier to prove. BTW, same solution as above.
19.01.2018 06:28
The answer is $\frac{p+q}{\gcd(p,q)}$. Obviously we may assume that $\gcd(p,q)=1$ by scaling; we prove in that case $n \ge p+q$ is optimal. To see $n = p+q$ is sufficient, consider a board with $\{1, \dots, p\} \sqcup \{1, \dots, q\}$; this clearly can last forever. We now show $n \ge p+q$ is necessary. Assume $n$ minimal, which implies that every entry is changed infinitely many times. We'll consider the entire blackboard as generating an infinite table with $n$ columns, such that each row is obtained from the previous one by replacing $a$, $a$ with $a+p$, $a+q$ (for some $a$), and each column is unbounded. Now, WLOG (by shifting and rearranging) and first two entries of first row are $0$, and all others are nonnegative. We then add the additional condition (as we may) that whenever the first column is erased we increment that entry by $p$, and whenever the second column is erased we increment that entry by $q$. Thus the first column will contain all positive multiples of $p$ and the second column will contain all positive multiples of $q$. Claim: Let $S = \left\{ p, 2p, \dots, (q-1)p \right\} \cup \left\{ q, 2q, \dots, (p-1)q \right\}$. Then for every $s \in S$, there exists a column $C$ other than the first or second column such that $\max (S \cap C) = s$. Proof. Let $t \in S$ and assume $p \mid t$ (other case similar). Since it is incremented by $p$ in the first column, there must be some column containing $t$ followed immediately by $t+q$. That column then cannot contain any larger elements of $S$. Indeed, the next smallest multiples of $p$ and $q$ exceeding $t+q$ are $t+pq$ and $pq+q$, respectively. $\blacksquare$ Hence the number of columns is at least $2 + \# S = p+q$, as needed.
18.02.2018 17:50
Another idea that helps: Since every entry is changed infinitely many times, in each moment if $x$ is the value of the minimal number on the blackboard, there must be at least two numbers on it equal to $x$. Now it easily follows that $$a,a,a+1,a+1\ldots a+p-1,a+p-1,a+p,a+p+1,\ldots ,a+q-1$$should be on the board initially. So the desired number is $p+q$ indeed.
27.07.2019 05:59
Kirilbangachev wrote: Another idea that helps: Since every entry is changed infinitely many times, in each moment if $x$ is the value of the minimal number on the blackboard, there must be at least two numbers on it equal to $x$. Now it easily follows that $$a,a,a+1,a+1\ldots a+p-1,a+p-1,a+p,a+p+1,\ldots ,a+q-1$$should be on the board initially. So the desired number is $p+q$ indeed. That's not correct. For example,{a, a+p, a+2p, …, a+(q-1) p, a, a+q, a+2q, …, a+(p-1) q} is OK(it can be proved by induction). Sorry for my poor English.
24.06.2020 21:31
14.01.2023 06:00
I was really bad at writing up 2.5 years ago... Here is a full solution, with a motivated and mostly rigorous writeup, where we will just show that if $\gcd(p,q)=1$ and $n<p+q$, then $n$ numbers cannot make our number-writing game infinite. If two numbers with value $a$ are replaced with $a+p, a+q$, we call this operation a toggle at $a$. We say two numbers interact if they start at $a,a$ and are replaced with $a+p, a+q.$ Motivated solution:
Now we label the numbers on the board $b_1,\cdots,b_n$. The labels now have nothing to do with size. So if $b_i,b_j$ increment, then the new $b_i$ becomes the old $b_i+p$ and the new $b_j$ becomes the old $b_j+q$
By our rules, the number with label 1 always get +p, and the number with label $n$ always get +q. We focus on after making $N$ moves (for some $N$), each number gets incremented by the same amount, call $K$. Here is the central claim that finishes the problem: The numbers with label 1,2, ..., q always get +p.
Now, we can easily show that $b_1$ increments by $p$ with at least $q$ other elements that are not $b_2,\cdots,b_p$, which implies there are at least $p+q$ numbers on the board.
10.02.2023 22:38
Amazing problem. First, we may assume $\gcd(p, q) = 1$. If otherwise, then we must partition the numbers on the board into $\gcd(p, q)$ disjoint groups based on their remainder modulo this, which don't interact. The answer is $n=p+q$. For construction, use $\{1, 2, 3, \cdots, p \} \cup \{1, 2, 3, \cdots, q\}$. Step One: Simplification. Suppose that $n$ is minimal and the condition is true. Then, minimality implies that every element must be toggled infinitely many times. On the other hand, this implies that we can assume we are always able to toggle the minimal entry; otherwise, as the numbers are nondecreasing, the minimal entry will only be toggled finitely many times. Step Two: Collapsing. The idea is now to construct the board piecemeal. In the opening, shift the two identical numbers down to zero, and consider the list $\ell_i = (a_{1i}, a_{2i}, \cdots, a_{ni})$ after $i$ toggles. Because the list remains the same upon ordering, fix the first two entries of each list to be strict multiples of $p$ and $q$ respectively. Furthermore, set $0=a_{10} =a_{20} < a_{30}<a_{40}<\cdots<a_{n0}$. It follows that at each step we toggle elements of the form $a_{ji}$ for $j < k$ with priority and else introduce the element $a_{(k+1)i}$. Inductively, these introduced elements must be multiples of $p$ or $q$. Claim. [Uniqueness of Representation] Each element in these first two entries corresponds uniquely to one of the remaining $n-2$ entries across all lists. Proof. In each column that is not the first two, suppose that a number $kp$ appears. The first entry of the same list must be incremented by $p$ during the next toggle, on which this element is incremented by $q$. On the other hand, as $\gcd(p, q) = 1$, the next smallest multiples that could appear are $kp+pq$ and $pq+q$, respectively, which are both too large with $n < p+q$. $\blacksquare$ As a result $n \geq (p-1) + (q-1) + 2 = p+q$, as needed.
25.11.2024 05:05
Bit too long, I am not sure it's fully right, but whatever We prove that smallest $n$ is $\frac{p+q}{gcd(p,q)}$ First we assume $p,q$ are coprime to each other. Suppose we have $a_1 \leq a_2 \leq \cdots \leq a_k$ write on board, with $k$ smallest. Lemma:
Now using it , will not depend on any other number. Therefore for sake of brevity we will always choose smallest. Take a note that we can start with $0,0$ as anything $a,a$ we are just adding $p,q$ so it doesn't matter. Claim: $$S = \{0,p,2p,\cdots (q-1)p\} \cup \{0,q,2q,\cdots (p-1)q\}$$is set of $p+q$ number required to achive infinite sequence. We will prove this by greedy algorithm. Let's consider set $M$ be set of number $\{a_1,a_2,\cdots a_k\}$ required for $(p,q)$. We will be consturcting sequence which can achive max number of board. Important part is, if it's ever happen that smallest number don't have his partner, then it should exits in sequence. Note this is only way otherwise smallest number will not have partner. So this is force algorithm. In this way, we can prove that nothing less then $p+q$ won't works and also how $S$ works. Assume that $q= pk+r$. Take smallest number of board with no partner. Add this number on board and in set $M$. This is necessary by lemma. For example we start with $$(0,0) \rightarrow (p,pk+r)$$so we add $p$ in set $M$. (adding number in $M$ is equvilent to adding in blackboard) Now $$(p,p) \rightarrow (2p,p(k+1)+r)$$Note smallest number is still $2p$, hence we add $2p$ in set $M$ and continue this process. Each time we take multiple of $p$ and combine which make next multiple of $p$ and some sequence after $pk+r$. Now once we add $pk$ in $M$ we get \[\{p(k+1),p(k)+r,p(k+1)+r,p(k+2)+r \cdots p(2k)+r\} \]on blackboard. Now smallest number is $pk+r$ hence we add that which give us \[(pk+r,pk+r) \Rightarrow (p(k+1)+r,p(2k)+2r)\]Now we start adding multiple of $p$ again. Important to note that each time smallest number is either multiple or $p$ or $q=pk+r$. This is because way of this sequence constructed. We denote set $R_i$ by set of numbers of form $ i \equiv \mod {p}$. We define starter of $R_i$ as smallest number in $R_i$ which is multiple of $q=pk+r$. Note $m$th number in $R_i$ will be just $p(ik+m-1)+ir$ Note if operation is happen in some number in $R_i$ on $h$th number which is $$p(ik+h-1)+ir$$, then we will get $(h+1)$th copy and $R_{i+1}$ set's $h$th number or $$p((i+k)+h-1)+(i+1)r$$ Therefore we always continue this algorithm till each $R_i$'s end there is multiple of $q$ and so we choose starter there as again multiple of $q$. Here is brief photo how $R_i$'s looks till $i = 1,2,\cdots p$ (for now we consider $R_i$ and $R_p$ sequence different) \begin{align*} R_0 &=\{ p,2p,\cdots ,pk,p(k+1),\cdots \cdots p(pk+r-1)\} \\ R_1 &= \{p(k)+r,p(k+1)+r \cdots \cdots \} \\ R_2 &= \{p(2k)+2r,p(2k+1)+2r \cdots \cdots \} \\ \cdots \\ \cdots \\ \cdots \\ R_{p-1} &= \{p((p-1)k)+(p-1)r,p((p-1)k+1)+(p-1)r \cdots \cdots \} \\ \\ R_p &= \{p(pk)+pr \} \end{align*} Now till number $p(pk)+pr$ comes in $M$ we have used all multiples of $p,q$. Observe we get one $p(pk)+pr$ from $R_{p-1}$ and one from $R_0$. Hence we won't need $p(pk)+pr$ in $M$. Finally we prove whatever number we have now on blackboard can make infinite numbers. end number of $R_i$'s (or closest to $p(pk+r)$) now are more then $p(pk)+pr = p(pk+r)$ but note they can't be more then $p(pk+r)+p$. These number comes $2$ times, as In process we always get starter from $R_{i-1}$ and from $R_i$ itself. and all of these are \emph{starter} So number $p(pk)+l_ip+ir$ for $R_i$ set numbers for $i \leq p-1$ come two times. From this what we have is $$(l_i-1)p+r < pr < l_ip+r $$ Now we consider $R_i$ sequences and making means +q only consider for now in context. Last term of $R_0$ is $p(pk+r-1)$ which will make $p((pk)+k+r-1)+r = p(pk)+p(k+r-1)+r$. Now from here $R_1$ gose till $p(pk)+(l_1-1)p+r$, which makes $R_2$'s number $p(pk)+(l_1+k-1)p+2r$. Similary $R_i$ covers number from $$p(pk)+(l_{i-1}+k-1)p+ir \rightarrow p(pk)+(l_i-1)p+ir$$This number will produce new number which only comes $1$'s. As there is no other way to produce them. Total number of number which come ones only is $L$ then $$ L = (l_1 - (k+r)) + (l_2 - (l_1+k)) + \cdots (l_{i} - (l_{i-1}+k)) \cdots (l_{p-1} - (l_{p-2}+k)) - (l_{p-1}+k-1) $$$$L= r - pk -p = pk+r -p $$Few fact to be notice, our board don't have $p(pk)+(l_{i-1}+k-1)p+ir$ hence we won't consider it. All of number of type $p(pk)+l_ip+ir$ each comes $2$ times. Note all of them cover Whole module $p$, hence it cover all $p(pk+r)$ to $p(pk+r)+p-1$ number , each twice. (All the details that how only this comes $2$ times , and how all cover all module class is easy to see). Therefore we have $2p + pk+r-p = pk+r + p$ numbers on board Hencefore Now we have $p+q$ number of board , which are \[ \{pq,pq,pq+1,pq+1, \cdots pq+p-1,pq+p-1,pq+p,pq+p+1,pq+p+2,\cdots ,pq+q-1 \} \]If we operate on $(pq,pq)$ we get $(pq+p,pq+q)$ which is same as above list. Hence It can be check that this works infinitely many times. For any $(dp,dq)$ same process works just we multiple all set of $S$ by $d$, but number required are $p+q$ only. Remarks: Throughout proof we will prove some optimizations. we won't mention them again but all of them used repeactedly. Some of easye details are not mentioned. To understand process try for first few $R_i's$.