nooooooob

Every step will increase the total apples by 1 but it won't increase the maximal number of apples that one girl has.

tarzanjunior wrote: The monovariant is the sum of difference between consecutive girls. It decreases at every step. You meant: the sum of the squares of the differences between consecutive girls. Otherwise that is just zero And the squares is the solution that I gave

...................

Each time the sum of difference of two consecutive numbers decreases by $2$.

Call a girl poor if she has less apples than her neighbor, rich otherwise. Show a initially poor girl will always remain poor.Prove no two rich girls can't be neighbours. Then the problem becomes trivial.

Kayak wrote: Call a girl poor if she has less apples than her neighbor, rich otherwise. Show a initially poor girl will always remain poor.Prove no two rich girls can't be neighbours. Then the problem becomes trivial. Not true, a poor girl won't remain poor always, Consider 1,0,0,0,0,0.

Idea_lover wrote: Not true, a poor girl won't remain poor always, Consider 1,0,0,0,0,0. Each girl has positive integraal apples.

Kayak wrote: Idea_lover wrote: Not true, a poor girl won't remain poor always, Consider 1,0,0,0,0,0. Each girl has positive integraal apples. DId they mention that ? They said each girl has some apples with her... I proved the problem for even the girls having 0 apples !!

Anybody with me ?

My problem INMO 2018 wrote: There are $n\ge 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.) Suppose the process never stops. Let $a_i$ be the number of apples held by girl $i$ for all $1 \le i \le n$. Let $s \overset{\text{def}}{=} (a_1+\dots+a_n)$ and $t \overset{\text{def}}{=} (a_1^2+\dots+a_n^2)$. Observe that $s$ always increases by $1$ while for $t$, we see that the change is $$a_i^2+a_{i+1}^2+a_{i-1}^2-(a_i-1)^2-(a_{i+1}+1)^2-(a_{i-1}+1)^2=2(a_{i-1}+a_{i+1}-a_i)+3 \le 1.$$Thus, after $k$ moves, the new value of $t$ is no more than $t+k$ while the new value of $s$ is $s+k$. However, at any stage we must have $$a_1^2+\dots+a_n^2 \ge \frac{(a_1+\dots+a_n)^2}{n}$$yielding $n(t+k) \ge (s+k)^2$. Clearly, for $k$ sufficiently large, this inequality cannot be true. $\blacksquare$ EDIT: Good way to do the 1500th post EDIT: Observe that it also gives a bound on how long the process can last. I'm curious if it's a good one or not.

Nice solution.

Wizard_32 wrote: tarzanjunior wrote: The monovariant is the sum of difference between consecutive girls. It decreases at every step. You meant: the sum of the $squares$ of the differences between consecutive girls. Otherwise that is just zero And the squares is the solution that I gave Yes, that is the solution I gave as well. By the way, do the girls have positive integer number of apples or non-negative number of apples? I assumed the former in my proof.

Can anybody please tell if this is false or right ? Kayak wrote: Call a girl poor if she has less apples than her neighbor, rich otherwise. Show a initially poor girl will always remain poor.Prove no two rich girls can't be neighbours. Then the problem becomes trivial.

Supercali wrote: By the way, do the girls have positive integer number of apples or non-negative number of apples? Positive, as far as I could tell. Kayak wrote: Call a girl poor if she has less apples than her neighbor, rich otherwise. Show a initially poor girl will always remain poor.Prove no two rich girls can't be neighbours. Then the problem becomes trivial. Is being rich defined as having apples greater than the sum of apples of neighbours being or having more apple than any one of the neighbours? Similar question for poor.

Number the girls $G_1, \cdots, G_n$, and at some instant, let $V(G_i)$ denote the number of the apples of $G_i$ at that instant. At that instant, $G_j$ is called poor if $V(G_j) \leq V(G_{j-1}) + V(G_{j+1})$, and rich if $V(G_j) > V(G_{j-1}) + V(G_{j+1})$. And basically the sketch of the proof of the fact that an initially poor girl will always remain poor is to consider the penultimate step and step where the poor girl becomes rich, and deriving a contradiction (I don't remember the details)

If you were able to prove all the claims to be true then it is definitely true. Nice proof.

CZRorz wrote: Every step will increase the total apples by 1 but it won't increase the maximal number of apples that one girl has. I did the same but I wrote the maximum doesn't change instead of the maximum doesn't increase. It doesn't affect the rest of my proof in any meaningful way. Any ideas about how many marks will be cut?

I did it by induction (to be precise,strong induction)on n.

Define $S=\sum{ a_i-a_{i-1}-a_{i+1}}$ Does this work? ofc: it doesnt

cop wrote: Define $S=\sum{ a_i-a_{i-1}-a_{i+1}}$ Isn't $S=-\left(\sum a_i\right)$?

Let $S$ be the sum of cubes of the number of apples each girl has. We show that this is strictly decreasing. Let $x$, $y$ and $z$ be the number of apples a trio of girls have before a step, with $y > x+z.$ We see that the only change in $S$ is due to these $3$ girls, and computation shows that we need to prove \[0 >(3x^2 +3x +1) +(3z^2 +3z +1) -(3y^2-3y+1).\]Setting $y=x+z+k$, where k is a natural number we need to show \[0 >6(x+z)-6k(x+z) +3k+1 -3k^2 -6xz.\] For $k>1$ , this is obvious. Suppose $k=1$, then we need to show $0>1-6xz$. This is obvious if $x$ and $z$ are non zero. Suppose one of them is zero. Then, since the girls began with a non zero number of apples, consider the first $0$ to appear, and the corresponding girls neighbours. It is not hard to see that we get a contradiction. Hence, we are done, since the sum of cubes at the start is a finite number, and an infinite number of steps would imply an infinite sequence of strictly decreasing naturals, which isn't possible.

My method matches with none!!!

Ranger1042 wrote: My method matches with none!!! Same here !

Kayak wrote: Call a girl poor if she has less apples than her neighbor, rich otherwise. Show a initially poor girl will always remain poor.Prove no two rich girls can't be neighbours. Then the problem becomes trivial. Even I did it almost the same way.....

GeronimoStilton wrote:

Edit: 888th post! It may occur that some girl has zero apples. If n_(i+1) =0 then this does not work. However, we can modify it. Note that the number of girls with 0 apples(T) is a non_increasing monovariant. And if sum of the absolute differences(S) does not decrease then T necessarily decrease. (In case n_(i-1), n_(i-1)+1,0 (n_(i-1)>0): in this case S remains same and T decreases by 1; and in the case 0,1,0: in this case S increases by 2 and T decreases by 1. So, S decreases always but only a finite no. of times. So the process must terminate.

What if we allow the girls to have negative number of apples? There is still a solution.

anantmudgal09 wrote: My problem INMO 2018 wrote: There are $n\ge 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.) $$(a_{i-1}+a_{i+1}-a_i) \le -1.$$ Hello to everyone.Where do you know this inequality?

Nobody???

It's in the problem itself and he has chosen the $i$ accordingly.

Defining $S=\sum{ (a_i-a_{i-1}-a_{i+1})^2}$ helps.

.............

integrated_JRC wrote: There are $n\ge 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.)

Lets say it will go on for infinity so there exists a second where the max apples in one girls hand gets increased and you can easily check this wont happen

$\text{Approach this problem using monovariance}$ $\text{ Solution : Let the person i have}$ $a_i$ $\text{apples}$ $\text{Define}$ $ S= \sum_{k=1}^{n} a_i ^3 $ $\text{Let}$ $S_i$ $\text{be the sum at step-i}$ $\text{Let person m have more apples than person (m-1) and (m+1) combined}$ $\text{When teacher performs the operation}$ $S_{i+1}= S_i + 1-3[a_k(a_k -1) -a_{k+1}(a_{k+1} +1)-a_{k-1}(a_{k-1}+1)]$ $\text{We have been also given that}$ $a_k>a_{k+1} +a_{k-1}$ $\text{So}$ $S_{i+1}< S_i +1 - 3a_k[a_k-a_{k+1} - a_{k-1} -1]<1+S_i$ $\text{Now notice}$ $S_i \neq S_{i+1} \forall i.$ $\text{Since}$ $S_i$ $\text{is a natural number for any i. So we have}$ $S_{i+1}<S_i.$ $\text{By Well ordering principle the set of}$ $S_i$ $\text{has a least value as the sequence is decreasing, let this value be A.}$ $\text{Thus after a finite number of steps we reach A. At this step the process terminates.}$

I have a simpler solution to this one. 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 $j\in\{1\leq{a}\leq{n}, a\in\Bbb{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$. Claim : $\Delta_k\leq{a_j}$, $\forall k \in \{1,2,3,......,n\}$ 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 $m\leq{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_k\leq{a_j}$, $\forall k \in \{1,2,3,......,n\}$ This completes the proof of our claim. $\blacksquare$ Hence, we can say, $\Delta_1\geq\Delta_2\geq.......\geq\Delta_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$

Consider the Quantity $S=\sum{|a_{k+1}-a_{k}|}$ where $a_{n+1}=a_1$. Assertion 01: No girl ever has $0$ apples. Proof 01: Suppose at some point, a girl gets 0 apples. Lets consider the first time it happens. Then, since the number must have decreased to become 0, the girl must have 1 apple prior to this operation. Then we have that 1 is greater than the sum of the number of apples belonging to her neighbors, contradiction. Assertion 02: If $a_l \geq a_{l-1}+a_{l+1}$, then $a_{l}-1 \geq a_{l-1}+1, a_{l}-1 \geq a_{l}+1$ Proof 02: Only way this fails is when $a_{l-1}$ or $a_{l+1}=a_l-1$. But then either $a_{l+1}$ or $a_{l-1}$ must equal $0$ for the process to even happen, which is a contradiction by Assertion 01 Assertion 03: $S$ is strictly decreasing Proof 03: $(a,b,c)->(a+1,b-1,c+1)$, by above assertions, initial $S$ for this pair was $2b-a-c$ and final $S$ for this pair is $2b-a-c-4$. $S$ for neighours of $a,c$ which are not $b$ can increase at most by $1$. Therefore, the final value of $S$ is at least $2$ less than initial value, hence proved. By above assertions, $S$ is strictly decreasing but by common sense, $S$ is at least $0$, so this process must halt. H.P.

I constructed an algorithm which the teacher can follow to ensure that no girl has more apples than both of her neighbors combined. $\textbf{ALGORITHM.}$ Let $G_1,G_2,\cdots,G_n$ be the girls in cyclic order. Let girl $G_i$ have $a_i$ apples. Define $b_i=a_{i-1}+a_{i+1}-a_i$, where subscripts are taken $\text{mod }n$. Every time the teacher takes away an apple from a girl (say $G_i$ and call it an $i-$switch) and gives an apple to each of the neighbors (here $G_{i-1}$ and $G_{i+1}$), then: $(1)$ $b_i$ increases by $3$; $(2)$ Each of $b_{i-1}$ and $b_{i+1}$ decrease by $1$; $(3)$ Each of $b_{i-2}$ and $b_{i+2}$ increase by $1$. Call this Let $b_{i_1}=\text{min}\{b_1,b_2,\cdots,b_n\}$. We take $b_{i_1}<0$. (Or else the the teacher does not do anything!) Let $b_{i_1}=-m$. The teacher should perform an $i_1-$ switch exactly $\lceil{\frac{3m}{7}}\rceil$ times. After that, $b_{i_1}$ becomes $-m+3\lceil{\frac{3m}{7}}\rceil$, which is surely positive. It is easy to see that this does not give $a_{i_1}<0$, as before the $i_1-$switches, $a_i>\lceil\frac{3m}{7}\rceil$. Note that $b_{i_1-1}$ and $b_{i_1+1}$ decrease by $\lceil\frac{3m}{7}\rceil$. Also, $b_{i_1-2}$ and $b_{i_1+2}$ increase by $\lceil\frac{3m}{7}\rceil$. We now perform an $(i_1-1)-$switch and an $(i_1+1)-$switch, each exactly $\lceil\frac{m}{7}\rceil$ times. This makes sure that $b_{i_1-1}$ and $b_{i_1+1}$ are restored to a now higher value (than their initial value), because $3\lceil\frac{m}{7}\rceil\ge\lceil\frac{3m}{7}\rceil$. Also, $b_{i_1}$ finally becomes $\lceil\frac{9m}{7}\rceil-m-2\lceil\frac{m}{7}\rceil$, which is still a positive quantity. Also, final total change in value of $b_{i_1-2}$ and $b_{i_1+2}$ is $\lceil\frac{3m}{7}\rceil-\lceil\frac{m}{7}\rceil$, which is also a positive quantity. Also, $b_{i_1-3}$ and $b_{i_1+3}$ are also increase by $\lceil\frac{m}{7}\rceil$. This completes our algorithmic step on $b_{i_1}$. In this step, $b_{i_1}$ becomes positive and none of its neighbors' $b_i$'s are really "disturbed", as their change is also either positive or zero. We keep performing this step for $b_{i_2},b_{i_3},\cdots$ where $G_{i_k}$ is the girl with minimum $b_{i_k}$ after $k-1$ steps, and this eventually gives all $b_i$ as positive, completing the algorithm.

Consider girl $G_{i}$ has $b_{i}$ number of apples where $1 \leqslant i \leqslant n.$ FTSOC consider that the process never stops. Consider $\mathcal{C}=\sum_{i=1}^{n} b_{i}$ every time $\mathcal{C}$ increaes by $\mathcal{C}+1$ Also we consider $\nabla=\sum_{i=1}^{n} b_{i}^2$. Every time $\nabla$ increases by: $(b_{j}-1)^2+(b_{j-1}+1)^2+(b_{j+1}+1)^2-b_{j-1}^2-b_{j}^2-b_{j+1}^2=3+2(b_{j-1}+b_{j+1}-b_{j}) \leqslant 1$ which implies that after $\ell$ moves $\nabla$ increases by at most $\ell$ and new value of $\mathcal{C}$ after $\ell$ moves is $\mathcal{C}+\ell$ which gives that $n(\nabla+\ell) \geqslant (\mathcal{C}+\ell)^2$ ( from C-S inequality) $\qquad \qquad (\dagger)$ but we also have $n \cdot \nabla \geqslant (\mathcal{C})^2$ (yet again from C-S inequality) which gives contradiction for $(\dagger)$ for arbitarily large choice of $\ell$ (becasue teacher has abundant apples) hence we have a contradiction , and problem statement follows $\blacksquare$

सबसे पूर्व यह देखो कि सारे सेबों की संख्या प्रति चरण एक से बढ़ती है। दूसरा यह कि प्रत्येक बालिका के सेबों के वर्गों का योग अधिकतम एक से बढ़ सकता है। दोनों बिंदुओं से प्रेरित होकर यदि हम $\sum a_k^2-2a_k +1$ का निर्माण करें तो पाएँगे कि यह सदैव ह्रासमान है (जहाँ $k$-वीं बालिका के पास $a_k$ सेब हैं)। किंतु यह वर्गों का योग होने के कारण सदा एक ऋणेत्तर संख्या है। अतः यह प्रक्रिया अनन्त नहीं।

Is there any flaw with the following proof? I don't see this proof above ig? It is easy to note that a move cannot be directly applied on a girl who is neighbor to a girl containing the maximum number of apples. Now if at some move the maximum increases, it must mean that a move was applied on a girl beside a maximal girl which is a contradiction. Thus the maximum is bounded above. Now FTSOC the process goes on forever. Note that at every move, the total number of apples with the girls increases by $1$. Thus by infinite PHP, we get that some girl has infinitely many apples after infinitely many moves which gives a contradiction to the upper bound of the number of apples with a girl.

Let $\mathcal{G}$ denote the set of girls $g_i$ where $i=1,2,\ldots,n $ and let $\alpha_j(g)$ denote the number of apples with $g$ after $j^{\text{th}}$ iteration for $j=0,1,\ldots,n$. Something cool pops up when we study the extremal object $\displaystyle\max_{g\in\mathcal{G}}\alpha_j{(g)}$. Proposition 1. $\displaystyle\max_{g\in\mathcal{G}}\alpha_{j}{(g)}\ge \displaystyle\max_{g\in\mathcal{G}}\alpha_{j+1}{(g)}$. By Proposition 1 we have an upper bound for the total number of apples in the class i.e, $$\sum_{g\in\mathcal{G}}\alpha_{j}(g)\le |\mathcal{G}|\max_{g\in\mathcal{G}}\alpha_{0}{(g)}.$$But the total number of apples after each iteration seems to be increasing by $1$ which forces this process to terminate after a finite number of iterations.$\square$