A machine accepts coins of $k{}$ values $1 = a_1 <\cdots < a_k$ and sells $k{}$ different drinks with prices $0<b_1 < \cdots < b_k$. It is known that if we start inserting coins into the machine in an arbitrary way, sooner or later the total value of the coins will be equal to the price of a drink. For which sets of numbers $(a_1,\ldots,a_k;b_1,\ldots,b_k)$ does this property hold?
Problem
Source: Russian TST 2021, Day 7 P1
Tags: combinatorics, number theory
21.03.2023 23:02
Answer: $\boxed{(a_1,a_2,\cdots ,a_k)=(1,2,\cdots, k)\; ;\; (b_1,b_2,\cdots ,b_k)=(n+1,n+2,\cdots ,n+k)\text{ or }(a_1,a_2,\cdots ,a_k)=(b_1,b_2,\cdots ,b_k)}$ Let's begin arbitrarily inserting the coins so that the total value of the coins is never equal to the price of a drink. By the problem condition, there must be a time when our greedy algorithm fails, (let $A$ be the total value of the coins inserted till that time, $A\ge 0$) which means that for all $i\in[1,k]$, there exists a $j\in[1,k]$ such that $A+a_i=b_j$. As $(a_x)_{x=1}^k$ and $(b_y)_{y=1}^k$ are increasing sequences, we must have $A+a_i=b_i$ for all $i\in[1,k]$. If $A=0$, then $(a_x)_{x=1}^k\equiv (b_y)_{y=1}^k$. Assume that $A\ge 1$. By inserting the coin $a_1=1$ ($A-1$ times), we can get a total value of $A-1$. After this, let's insert the coin $a_2$ and then $a_k$. We know that $A-1+a_2< b_2=A+a_2$. If $a_2\ge 3$, then $A-1+a_2>b_1=A+1$. Hence, $A-1+a_2$ is not equal to the prince of a drink. After we insert the coin $a_k$, our new total value is $A-1+a_2+a_k>A+a_k=b_k$. Thus, we can just add the coin $a_1$ infinite times and the total value will never be equal to the price of a drink. Then, we must have $a_2=2$. Now, assume that we have shown $a_i=i$ for all $i\leq t-1$ where $k\ge t\ge 3$. Let's prove that $a_t=t$. By inserting the coin $a_1=1$ ($A-1$ times), we can get a total value of $A-1$. After this, let's insert the coin $a_t$ and then $a_k$. We know that $A-1+a_t<b_t=A+a_t$. If $a_t\ge t+1$, then $A-1+a_t>b_{t-1}=A+a_{t-1}=A+t-1$. Thus, $A-1+a_t$ is not equal to the prince of a drink. After we insert the coin $a_k$, our new total value is $A-1+a_t+a_k>A+a_k=b_k$. Thus, we can just add the coin $a_1$ infinite times and the total value will never be equal to the price of a drink. Hence, we must have $a_t=t$, which completes the induction. You can easily check that both solutions eventually yield a total value equal to the prince of a drink.