Mathematics Asked by Stranger Forever on January 5, 2021
QUESTION: There are $nge 3$ girls in a class sitting around a circular table, each having some apples with her. Every time the teacher notices a girl having more apples than both of her neighbours combined, the teacher takes away one apple from that girl and gives one apple each to her neighbours. Prove that, this process stops after a finite number of steps.
(Assume that, the teacher has an abundant supply of apples.)
MY ANSWER:
We define the girls as gears. Now, let any gear which has more number of apples than it’s immediate neighboring gears rotate clockwise, and consequently the neighbors rotate counterclockwise..
(Note: The gears rotate only in groups of $3$ and the rotation of any group does not affect the other groups)
Any clockwise rotation decreases the number of apples by $1$ and any counter rotation increases the number by $1$.
We define, a group of $3$ gears to be in a stationary state if the gear that is trapped on both the sides has $leq$ number of apples than the sum of its neighboring gears. In such a case, the group does not rotate, and remains stationary..
Now, firstly, since we are considering positive integers, any group must come to a stationary state after finite number of rotations..
Define $Omega_k = a_{1k}+a_{2k}+a_{3k}+….+a_{nk}$ as the sum of the number of apples in any $k^{th}$ step. Here each $a_{ik}$ denotes the number of apples possessed by the $i^{th}$ girl, at the $k^{th}$ step.
Define $Delta_k=max(a_{1k},a_{2k},…..,a_{nk})$ as the maximum number of apples possessed by some girl at any $k^{th}$ step.
Say, $Delta_0=a_j$, for some $jin{1leq{a}leq{n}, ainBbb{N}}$ (where $Delta_0$ represents the initial step)
Define $V(a_g)$ to be the maximum number of apples possessed by some girl, which is $leq$ girl $g$, or in the set excluding girl $g$.
$color{red}{Claim :}$$Delta_kleq{a_j}$, $forall k in {1,2,3,……,n}$
$color{red}{Proof:}$ Let us start the process with the group $(a_{j-1},a_j,a_{j+1})$..
Since, we have already proved that the number of rotations will be finite for this group to attain a stationary state. Let us say, after the $m^{th}$ step,
$a_{jm}<V(a_j)$
From this step onwards until the completion of the last step (say $p$) of this group, $Delta_k=V(a_j)$, where $mleq{k}leq{p}$
And $forall k<m$, $Delta_k$ was clearly $=a_j$.
Therefore, we see that in the whole process the value of $Delta$ never increases..
So, following the same pattern, we can say, for any group which attains a stationary state, the value of $Delta$ either remains same or decreases by $1$.
$therefore Delta_kleq{a_j}$, $forall k in {1,2,3,……,n}$
This completes the proof of our claim. $blacksquare$
Hence, we can say, $Delta_1geqDelta_2geq…….geqDelta_n$.
This clearly proves $Delta$ is a non-increasing function..
But, we also observe that the value of the sum $Omega$ increases by $1$ after every step.
$Omega_{k}= a_{1k}+a_{2k}+…….+a_{nk}$
$Omega_{k}<Delta_{k}+Delta_{k}+…… n$ times
$implies Omega_{k}<n.Delta_{k}$.
$implies Omega_{k}<n.Delta_{0}$
But, $Delta_{0}$ is a constant.. $Omega$ increases constantly by $1$.
Hence, for this inequality to hold true, $Omega$ cannot increase indefinitely, and therefore, the process must terminate after finite number of steps…
Q.E.D. $square$
Is my proof correct? If not, can someone please prove it in a more elegant way?
A simpler argument:
For each configuration $c$ we define the $textit{unfairness}$ function by $$F(c)=sum max(0, a_i-(a_{i-1}+a_{i+1}))$$
Here, of course, $a_i$ is the number of apples the $i^{th}$ girl currently has and the indices are handled cyclically.
Then each iteration of the "smoothing" operation lowers $F$ hence the whole thing must halt after at most $F(c)$ iterations, and we are done.
Note: to see that one iteration of smoothing lowers $F$, let $$F_i(c)=max(a_i-(a_{i-1}+a_{i+1}))$$ and consider one girl, $#3$, say, who has more apples than her neighbors combined. Then, of course, we have $F_3(c)=a_3-(a_2+a_4)>0$. When we smooth we leave all the $a_i$ the same except that $a_3'=a_3-1$, $a_2'=a_2+1$ and $a_4'=a_4+1$. Now we need to look at each term in the sum to see if it might have increased. Of course $F_3(c)$ has dropped by either $1$ or $2$. What about the other terms that may have changed? Well, to compute $F_2(c')$ we remark that $a_3>a_2+a_4$ implies that $a_3>a_2+1$ (since each girl has some apples) so $a_3≥a_2+2$ so $a_3'=a_3-1≥a_2+1=a_2'$. It follows that $F_2(c')=0$ so it did not increase. The same argument applies to $F_4(c')$ and, as these are the only ones that might have increased, we are done.
Correct answer by lulu on January 5, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP