There are 20 people at a party. Each person holds some number of coins. Every minute, each person who has at least 19 coins simultaneously gives one coin to every other person at the party. (So, it is possible that $A$ gives $B$ a coin and $B$ gives $A$ a coin at the same time.) Suppose that this process continues indefinitely. That is, for any positive integer $n$, there exists a person who will give away coins during the $n$th minute. What is the smallest number of coins that could be at the party? Proposed by Ray Li
Problem
Source: ELMO Shortlist 2013: Problem C8, by Ray Li
Tags: combinatorics, Chip firing, Hi
23.07.2013 08:36
The answer is 190. First, we construct a solution using 190 total coins; the people have 0, 1, ..., 19 coins in some order. After every minute, the coin counts remain the same up to permutation. The party is valid because it never ends. Now, we show that all parties must have at least 190 coins total.
We will prove the stronger statement: all parties lasting at least 19 rounds will require at least 190 coins total. So we will truncate the infinite party to its first 19 rounds. Let a person be useless if he will not perform the act of giving a coin to everyone else in the remainder of the party. A coin given to a useless person will never be passed on to anyone else. Initially, there are 19 minutes of the party remaining. Each of those minutes is an opportunity to give, so there are at most 19 distinct people who will give, and at least 1 person who will not give; 1 person who is useless. Since one coin is distributed to everyone, at least 1 coin will be given to useless people in the first minute. In the second minute, there are 18 minutes remaining so at least 2 people who will not give again; in the second minute, at least 2 coins will be given to useless people. Continuing the pattern tells us that in the $k$-th minute, at least $k$ coins will be given to useless people. Hence $1 + 2 + \ldots + 19 = 190$ coins will be given to useless people. Those $190$ coins will all be distinct; the party must have at least $190$ coins total, and we are done.
07.07.2014 16:04
31.08.2017 12:17
07.08.2018 09:35
27.08.2018 02:45
rmtf1111 wrote:
30.01.2019 04:40
The answer is that we need at least $\boxed{190}$ coins. To achieve this bound, start with the coin distribution $19,18,\ldots,2,1,0$. Note that every minute, the distribution is simply permuted, so the process continues on forever. It suffices now to show that this is a lower bound. Split the sequence into turns where only one person donates, where if many people want to simultaneously donate, arbitrarily order the donations (it is easy to see that the final position is the same as if all donated at the same time). Given a person $p$, let $a_p$ denote the number of times they donate in the first $19$ turns, and let $x_p$ be the last turn they donate on. If they started with $c_p$ coins, then we see that \[c_p+x_p-a_p\ge 19a_p\]since $x_p-a_p$ is the number of coins they gain till their last turn, and overall they ended up giving away $19a_p$ coints. Therefore, $c_p\ge 20a_p-x_p$, so the total number of coins is \[C=\sum_{p=1}^{20}20a_p-x_p=20\sum_p a_p - \sum_p x_p=20\cdot 19-\sum_p x_p.\]We see that \[\sum_p x_p\le 1+2+\cdots+19=190,\]so $C\ge 190\cdot 2-190=190$, as desired.
30.01.2019 13:04
This solution seems very silly for C8. Can anyone check it? As everyone said, the answer is $190$ which can be archieved by giving $0,1,2,...,19$ coins to each person initially. It suffices to prove that less than $190$ coins are not possible. Claim : If $x_i$ is the number of coins that the $i$-th person have, then $\sum_{1\leqslant i < j\leqslant 20}(x_i-x_j)^2$ is always decreasing. Proof : WLOG the move is $(x_1,x_2,...,x_{20})\to (x_1-19,x_2+1,x_3+1,...,x_{20}+1)$. Then the resultant change is $$\sum_{i=2}^{20}(x_1-x_i-20)^2 - (x_1-x_i)^2 = \sum_{i=2}^{20} 400 - 40(x_1-x_i) = 40(190 - 20x_1 + (x_1+x_2+x_3+...+x_{20}))$$which is negative as $x_1+x_2+...+x_{20} < 190$ and $x_1 \geqslant 19$. Since the sum is always non-negative, the process cannot go indefinitely, contradiction. Motivation : The process should make the distribution of coins smoother, hence it's natural to try $\sum (x_i-x_j)^2$, which turns out to be worked.
25.05.2021 07:44
The Concept is somehow similar to ISL 1994 C5 (a.).. Coins get Stuck..
24.06.2021 09:33
Why is this sooo similar to IMOSL 1994 C5
08.07.2021 19:57
Thanks to @quirtt for that hint of sum of squares. Let the people be labelled $(P_1 , P_2 , \cdots , P_{20})$. The answer is $0 + 1 + 2 + \cdots + 19 = 190$, for construction WLOG let the number of coins with $(P_1 , P_2 , \cdots , P_{19} , P_{20})$ be $(0,1,\cdots ,18, 19)$, after the first minute the number of coins with the people in that order would be $(1,2,\cdots , 19, 0)$ which is basically a permutation of the previous set of number of coins, thus it's an invariant and hence the process can continue indefinitely. Now it's enough to show that the if the sum is $< 190$, the process must terminate. For obvious reasons if everyone has $\ge 19$ coins, the process will continue indefinitely. So WLOG let the first $n$ people labelled have $\ge 19$ coins and last $20-n$ people have $<19$ coins. Let $(Q_{1} , Q_{2} , \cdots Q_{n})$ be the number of coins with $(P_1 , P_2 , \cdots P_{n})$ and $(R_{n+1} , R_{n+2} , \cdots R_{20})$ be the number of coins with $(P_{n+1},P_{n+2} , \cdots , P_{20})$ at any minute. After first minute the number of coins with $$(P_1 , P_2 , \cdots , P_{n}) = (Q_{1} - (20 - n) , Q_{2} - (20-n), \cdots Q_{n} - (20-n))$$and number of coins with $$(P_{n+1} , P_{n+2} , \cdots , P_{20}) = (R_{n+1} + n , R_{n+2} + n , \cdots , R_{20} + n)$$(Note that we are working when $\sum Q_i + \sum R_i < 190$) Sum of squares of number of coins after first minute $=$ \begin{align*} \sum_{i=1}^n (Q_i + n - 20)^2 + \sum_{i=n+1}^{20} (R_i + n)^2 &= \sum_{i=1}^n Q_i ^2 + \sum_{i=n+1}^{20} R_i ^2 + n^2(20-n) + 2n \sum_{i=n+1}^{20} R_i + 2(n-20)\sum_{i=1}^n Q_i + n(n-20)^2 \\ &= \sum_{i=1}^n Q_i ^2 + \sum_{i=n+1}^{20} R_i ^2 + 400n - 20n^2 + 2n(\text{sum of numbers}) - 40\sum_{i=1}^{n}Q_i \\ &< \sum_{i=1}^n Q_i ^2 + \sum_{i=n+1}^{20} R_i ^2 + 2n(\text{sum of numbers}) - 40\sum_{i=1}^{n}Q_i \\ &< \sum_{i=1}^n Q_i ^2 + \sum_{i=n+1}^{20} R_i ^2 + 2n(190) - 40 \cdot 19 \cdot n \\ &< \sum_{i=1}^n Q_i ^2 + \sum_{i=n+1}^{20} R_i ^2 + 380n - 760n \\ &< \sum_{i=1}^n Q_i ^2 + \sum_{i=n+1}^{20} R_i ^2 - 380n \\ &< \sum_{i=1}^n Q_i ^2 + \sum_{i=n+1}^{20} R_i ^2 \\ &= \text{sum of squares of number of coins before the minute} \end{align*}Thus the sum of squares decreases monotonically but since it cannot keep decreasing forever, thus the process must terminate.
05.08.2021 16:53
We first note that for the process to continue indefinitely ,each person must make moves infinitely many times. This is because if a person moves only finitely many times,at the end of his moves,he will start piling up coins,which is not possible. Now,we assign a special coin between two different people such that they keep passing it between themselves whenever they move. Thus there are at least $\binom {n}{2}$ coins. Actually,I first found the construction with the help of $1+2+...n-1$ and then noticed its resemblance to $\binom {n}{2}$.
09.11.2022 19:44
Generalize for $n$ instead of 20. The answer is $\frac{n(n-1)}{2}$. First of all we define some notations: Let $B_1,B_2,...B_n$ denote the people in the party. $M$ is the needed smallest number of coins. In the step $i$, let $a_i$ be the number of people who have $\geq n-1$ coins, and let $A_i$ be the set containing those people. there exists an index $k$ such that $$\sum_{i=1}^{k-1}a_i < n \leq \sum_{i=1}^{k}a_i$$if $k>1$, otherwise choose $k=1$ (since the process never ends, $a_i\geq 1$) For each person in $A_i$ where $1<i\leq k$ we assign the number $(n-1-a_1-a_2-...-a_{i-1})$. While for each person in $A_1$ we assign the number $n-1$. Notice that each assigned number for a person determine the least possible value for his number of coins initially that allow him to give $(n-1)$ coins at a specific step. So if a person has more than one assigned number, then he must have initially at least the sum of those assigned numbers. Define the numbers $x_i$ such that: $\forall i\in\{1,2,...,k-1\}: a_i=x_i$ $x_k=n- \sum_{i=1}^{k-1} a_i$ Now we can bound $M$ by the following: \begin{align*} M &\geq a_1(n-1)+a_2(n-1-a_1)+a_3(n-1-a_1-a_2)+...+a_k(n-1-a_1-a_2-...-a_{k-1})\\ &\geq x_1(n-1)+x_2(n-1-x_1)+x_3(n-1-x_1-x_2)+...+x_k(n-1-x_1-x_2-...-x_{k-1})\\ &=\sum_{i=1}^{k}x_i(n-1)-\sum_{1\leq i<j\leq k}x_ix_j\\ &=(n-1)\sum_{i=1}^kx_i- \frac{1}{2}((\sum_{i=1}^kx_i)^2-\sum_{i=1}^kx_i^2)\\ &\geq(n-1)n-\frac{1}{2}(n^2-n)\\ &=\frac{n(n-1)}{2}\\ \end{align*} for the construction, just start with $(n-1,n-2,...,2,1,0)$. $\blacksquare$
19.07.2023 05:07
Answer: 190 Construction is easy. Let $a_1 \cdots a_{20}$ be the number of coins people i have. WLOG, $a_1\leq \cdots a_{20}$. If there are less than 190 coins, there exists an i s.t. $a_i<i-1$. So after n-i rounds, anyone has less than 19 coins. Contradiction.
20.01.2024 04:18
The answer is $190$. Notice that at every minute after the very beginning, every person will have at most $19$ coins. Furthermore, if two people $i$ and $j$ have the same number of coins, they will continue to have the same number of coins. Therefore, we may split the sharing process into cycles of period $\ell \leq 20$; during every minute, some $a_\ell$ people will have at least $19$ coins to share; because every person must share at least once, $a_1+a_2+\cdots+a_\ell = 20$. Furthermore, after these $\ell$ turns, every person will have given away exactly $19$ coins and received $19$, so the process is cyclic. The total number of coins is given precisely by \begin{align*} C &= 19a_1+a_2(19-a_1) + a_3(19-a_1-a_2)+\cdots+a_\ell(19-a_1-a_2-\cdots-a_{\ell-1}) \\ &= 380 - \frac{(a_1+a_2+\cdots+a_\ell)^2 - a_1^2-a_2^2-\cdots-a_\ell^2}2 \\ &= 180 + \frac 12 \sum_{i=1}^\ell a_i^2 \\ &\geq 180+\frac 1{2\ell} \cdot 20^2 \geq 190 \end{align*}as $\ell \leq 20$. Equality occurs when we give the $i$th person exactly $i-1$ coins to begin.
22.01.2024 20:25
The answer is $190$. Let $S$ denote the sum, we first provide a lower bound on $S$. First, note that the sum of squares cannot strictly decrease after every operation, since this would eventually get a negative sum of squares which cannot hold. Thus, consider the operation where the sum of squares does not decrease. If we let student $i$ have $c_i$ coins. If we operate on student $1$ then we have... \[ \implies c_1^2 + c_2^2 + \cdots + c_{20}^2 \geq (c_1-19)^2 + (c_2+1)^2 + \cdots +(c_{20}+1)^2 \geq 0 \]\[ \implies -19c_1 + c_2 + c_3 + \cdots + c_{20}+190 \geq 0 \]\[ \implies -19c_1 + (S-c_1) \geq -190\]\[\implies S \geq 20c_1-190 \geq 20 \cdot 19 -190 = 190\] Construction id given by $0,1,2, \ldots, 19$ whic trivially works.
12.04.2024 16:23
Let us assign the weight $w_i$=$\binom{x_i}{2}$ to each person $i$ with $x_i$ coins. Consider $f(x_1,...,x_n)=\sum_{i=1}^{20}w_i$ In order for the game to go on indefinitely, we must have that $f(x_1,...,x_n)$ is not strictly decreasing entirely. Thus:(wlog assume that $x_1$ changed where $x_1\ge 19$) $$\Delta f= \sum_{i=2}^{20}\binom{x_{i}+1}{2}+\binom{x_1-19}{2}-\sum_{i=1}^{20}\binom{x_i}{2}>0$$for some $x_1,...,x_n$ since $\Delta f$ is not always negative. Then rewriting the expression gives: $$\sum_{i=1}^{20}x_i \ge \binom{x_1}{2}-\binom{x_1-19}{2}+x_1$$And the minimum of $R.H.S$ is when $x_1=19$ Thus; Number of coins $\ge$ $\binom{19}{2}+19=190$. Equality case for the starting position of $(0,1,2,...,19)$
24.04.2024 20:26
Am I stupid, or do 189 (and fewer) coins simply not work by the chip-firing theorem which states that an infinite cycle can only be achieved with at least (# of edges) chips?
24.04.2024 21:52
meduh6849 wrote: Am I stupid, or do 189 (and fewer) coins simply not work by the chip-firing theorem which states that an infinite cycle can only be achieved with at least (# of edges) chips? yes, you are right. Just consider $K_{20}$ and chip-firing states atleast $190$ required for possibility to infinite moves.