I used induction and casework during the inductive step to solve it. I first found that if a or b is even, it is possible and if a and b is odd, it is not possible.

I used parity for odd/even values. If a and b are both odd, then there exists $\frac{a+1}{2}$ odd and $\frac{a-1}{2}$ apples, $\frac{b+1}{2}$ even and $\frac{b-1}{2}$ odd pears.

I said that it takes ab moves and each move either increases or decrease s the number of fruits on an odd bowl by two so ab must be even. Then I said it can be switched to show it works when ab is even

A successful process must terminate in exactly $ab$ steps. A move consists of moving two odd-indexed fruit to even-indexed bowls, or vice versa. Clearly the two types of moves should happen equally often, so the task is impossible if $ab$ is odd. Now we prove that if $ab$ is even, the task is always possible. Call a pair $(x, y)$ valid if the process is possible for $(a, b) = (x, y)$. First, note that $(1, 2)$ and $(2, 1)$ are clearly valid, and it is not hard to see that if $(x, y)$ is valid then $(p x, q y)$ is also valid for any $p$ and $q$, which solves the problem.

paint the bowls such that odd = black; even # = white s_b = # of FRUITS in bowls 1 + 3 + .... + last odd s_w = # of FRUITS in bowls 2 + 4 + .... + last event each mod s_b-s_w changes by 4 mod 8 the whole thing lasts only a*b moves if a*b is odd, you get 0 = 4 mod 8 which is obviously not true otherwise it checks out will this get full creditr?

Let $A_1$, $A_2$, $P_1$, $P_2$ be the numbers of apples and pears in odd and even bowls respectively. Then the quantity $(A_1 - A_2)-(P_1 - P_2)$ is invariant.

kevinmathz wrote: I used parity for odd/even values. If a and b are both odd, then there exists $\frac{a+1}{2}$ odd and $\frac{a-1}{2}$ apples, $\frac{b+1}{2}$ even and $\frac{b-1}{2}$ odd pears. same

$a$ apples and $b$ pears becomes either $a$ apples and $0$ pears, then it's solved when $b$ is even, or $a$ apples and $1$ pear when $b$ is odd. This is only solvable if $a$ is even.

I wrote down bananas instead of pears so many times...

Brendanb4321 wrote: I wrote down bananas instead of pears so many times... Same Good thing I proof-read.

s333neb wrote: Let $A_1$, $A_2$, $P_1$, $P_2$ be the numbers of apples and pears in odd and even bowls respectively. Then the quantity $(A_1 - A_2)-(P_1 - P_2)$ is invariant. Nice observation - if $a$ and $b$ are odd, then $A_1 - A_2 = 1$ and $P_1 - P_2 = -1$ (so $I = 1 - (-1) = 2$ at the starting state, but we want $b$ pears followed by $a$ apples, giving $-1 - 1 = -2$). So this quickly shows that it's impossible if $a$ and $b$ are both odd.

s333neb wrote: Let $A_1$, $A_2$, $P_1$, $P_2$ be the numbers of apples and pears in odd and even bowls respectively. Then the quantity $(A_1 - A_2)-(P_1 - P_2)$ is invariant. I did the same

GameMaster402 wrote: paint the bowls such that odd = black; even # = white s_b = # of FRUITS in bowls 1 + 3 + .... + last odd s_w = # of FRUITS in bowls 2 + 4 + .... + last event each mod s_b-s_w changes by 4 mod 8 the whole thing lasts only a*b moves if a*b is odd, you get 0 = 4 mod 8 which is obviously not true otherwise it checks out will this get full creditr? You need to prove that it is always achievable when ab is even too.

oops i spent 2 hours on this maybe i'm just bad at combo We first show that if $ab$ is odd, the problem statement is impossible. Suppose that an odd move is a move in which $i$ and $j$ are odd. Assume that whenever multiple apples are in the same bowl, the one that was originally closer to bowl $a+b$ moves first, so that the apples remain in order; that is, the apple in bowl $k$ ends up in $b+k$. Similarly, assume that the pear in bowl $a+\ell$ ends up in $\ell$. If $k$ is odd, apple $k$ starts in bowl $k$ and ends up in bowl $b+k$. Thus, it encounters odd moves from bowls $k,k+2,\ldots,b+k-1$; or $\tfrac{b+1}2$ odd moves in total. If $k$ is even, apple $k$ encounters odd moves from bowls $k+1,k+3,\ldots,b+k-2$, but not $b+k$ since it ends up there, so it encounters $\tfrac{b-1}2$ odd moves in total. Then, the apples encounter $$\left(\frac{a+1}2\right)\left(\frac{b+1}2\right)+\left(\frac{a-1}2\right)\left(\frac{b-1}2\right)=\frac{ab+1}2$$odd moves. Similarly, if $\ell$ is odd, pear $\ell$ starts in bowl $a+\ell$ and ends up in bowl $\ell$. Thus, it encounters odd moves from bowls $a+\ell-1,a+\ell-3,\ldots,\ell+2$, but not $\ell$, since it ends up there, so it encounters $\tfrac{a-1}2$ odd moves. If $\ell$ is even, pear $\ell$ encounters odd moves from bowls $a+\ell,a+\ell-2,\ldots,\ell+1$, so it encounters $\tfrac{a+1}2$ odd moves. Then, the pears encounter $$\left(\frac{a-1}2\right)\left(\frac{b+1}2\right)+\left(\frac{a+1}2\right)\left(\frac{b-1}2\right)=\frac{ab-1}2$$odd moves. Since a move only occurs if $i-j$ is even, the numbers of odd moves apples and pears encounter must be equal; that is, $$\frac{ab+1}2=\frac{ab-1}2,$$which is impossible. $\blacksquare$ Now, assume that $ab$ is even. This implies that at least one of $a$ and $b$ is even. Assume WLOG $a$ is even. If $a$ is odd, we can take the mirror image of the problem, which is identical We use induction on $b$. The base case, $b=0$, is trivial, as we are done already. Now, assume that this problem is possible with $b-1$ pears. We will show that it is possible with $b$ pears. We take the pear in $a+1$, and make moves to move it down to $1$ without affecting the other pears. When the pear is in bowl $t$, move it with the apple that has position $a+2-t$ in the ordering of the apples. This way, each apple moves up exactly once, and since $$i-j\equiv (a+2-t)-t\equiv a+2-2t\equiv 0\pmod2,$$these moves are valid. Now, a pear is in bowl $1$, apple occupy bowls $2,3,\ldots,a+1$, and bowls $a+2,\ldots,a+b$ contain the remaining pears. Since $(i-1)-(j-1)=i-j$, we can ignore the pear in bowl $1$, and shift the remaining fruits down one bucket, so that the problem is the same as $b-1$ pears, which works by our inductive hypothesis. Hence, the problem is possible if and only if $ab$ is even, so we are done. $\square$

no_name wrote:

wait is this wrong i'm scared now

For $ab$ even, you can assume w.l.o.g. that $a$ is even (by symmetry; if only $b$ was even, then you can renumber the bowls in reverse, and swap apples/pears). Base case: $a=2$ and $b=1$. Then we can easily achieve it in two moves, by moving the apple in bowl #1 and the pear in bowl #3 so that everything is in bowl #2, then finishing the next move. Inductive step: suppose that for $a \ge 2$ (even) and $b \ge 1$, that with $a$ apples and $b$ pears that it is achievable. We will show two things: i) achievable with $a$ apples and $b+1$ pears, and ii) achievable with $a+2$ apples and $b$ pears. i) Apply the process on the $a$ apples and first $b$ pairs to get a configuration $bb\ldots ba\ldots ab$. Now we will "swap" the leftmost apple with the last pear by repeatedly applying the move on just these two fruits (as $a$ is even, the difference $i-j$ is even). This gives a solution for $a$ apples and $b+1$ pears. In particular, this gives a solution for $(a,b) = (2,b)$. ii) To show $a+2$ apples and $b$ pears is achievable, given that $a$ apples and $b$ pears is achievable, apply the process on the last $a$ apples and $b$ pears to get a configuration $aabbb\ldots baaa\ldots a$. Then, because we have shown that 2 apples and $b$ pears is achievable in i), we can now reverse the first two apples and $b$ pears. Combined with an argument that it is impossible for $ab$ odd, that should give a (mostly) complete solution. I think this should be correct (I did not take the USA(J)MO as I'm well beyond HS), but let me know of any errors.

I basically just said that an apple in bowl $i$ can be swapped with a pear in bowl $j$ by repeatedly applying the legal move, as long as $i-j$ is even. The configuration can be made by just swapping apples and pears, given that $ab$ is even. If both $a$ and $b$ are odd, then there will be an apple/pear that becomes an odd one out, which prevents the goal from being achieved. Hope that's right... i'd love to get a positive score for my first JMO lol

AMC_Kid wrote: Brendanb4321 wrote: I wrote down bananas instead of pears so many times... Same Good thing I proof-read. I had to write pears so much I started writing "pairs"

We will first show that the task is possible if $ab$ is even. First, note that if an apple is in bowl $i$ and a pear is in bowl $j$ initially, and $2|i - j$ and $j > i$, then we can always perform a sequence of moves to swap the positions of the apple and the pear; we will call this a swap of the apple in $i$ and the pear in $j$. We now consider two distinct cases: Case 1: $2|a, 2\nmid b$ or $2\nmid a, 2|b$. Then, letting $m = \min(a,b)$, perform swaps on the apple in $k$ and the pear in $a + b - k + 1$ for each positive integer $k\le m$. This gives the desired. Case 2: $2| a, 2|b$. Again, let $m = \min(a,b)$. This time, perform swaps on the apple in $k$ and the pear in $a + b + k - m$ for each positive integer $k\le m$. It is easy to see that this gives the desired. Now, suppose $a$ and $b$ are both odd. We will show that the task is impossible. Let $X$ and $Y$ be the number of apples and pairs, respectively, in odd-indexed bowls. It is easy to see that $X - Y$ is an invariant as any move either decreases both $X$ and $Y$ by $1$ or increases both by $1$. Initially, we have $X - Y = \tfrac{a+1}{2} - \tfrac{b-1}{2} = \tfrac{1}{2}(a-b) + 1$. However, if we were able to complete the task, then the value of $X - Y$ after the task is completed is $\tfrac{a - 1}{2} - \tfrac{b + 1}{2} = \tfrac{1}{2}(a-b) - 1$, which is not equal to the initial value of $X - Y$, contradicting the fact that $X - Y$ is invariant. We are done.

A year ago I looked at this problem and thought it was impossible, now I solve in 20 mins lol. We first show that if one of $a$ or $b$ is even, then it is possible. WLOG let $a$ be even. Let $A$ denote an apple and $P$ denote a pear. When $(a,b)=(2,1)$, we can turn $AAP$ into $PAA$ by operating on the first apple and pear, and then one of the middle apples and the pear. Now, for general $(a,b)$ with $a$ even, split the apples into consecutive pairs. We showed above that we can shift a pair right by one, so we can sequentially shift the pairs to the right, starting with the rightmost pair and working our way left. For example, when $(a,b)=(4,3)$, we do the following: \[ AAAAPPP \rightarrow AAPAAPP \rightarrow AAPPAAP \rightarrow AAPPPAA \]\[ \rightarrow PAAPPAA \rightarrow PPAAPAA \rightarrow PPPAAAA \] Now, we show that if both $a$ and $b$ are odd, it is impossible. Consider the number of apples in odd-indexed bowls minus the number of pears in odd-indexed bowls. This is invariant because each move takes out an apple and a pear from the odd-indexed bowls, or inserts an apple and a pear into the odd-indexed bowls. However, this difference decreases by $2$ over the moves, a contradiction. Therefore, it is impossible if both $a$ and $b$ are odd.

take cases if a+b is odd or even

I'm wondering, how many MOHS is this problem?

probably like 10M? pretty standard use of invariants

Original100_3.14 wrote: probably like 10M? pretty standard use of invariants more like 5M

I'd say like 3 M. This is too easy for the IMO, as generally J1's don't belong anywhere on the IMO. Side note, @DDCN_2011... You seem to have copied my solution from about 3 years ago imao.

ab456 wrote: I'd say like 3 M. This is too easy for the IMO, as generally J1's don't belong anywhere on the IMO. Side note, @DDCN_2011... You seem to have copied my solution from about 3 years ago imao. this is not imo this is jmo

its parity counting problem

First note that we can swap 2 fruits at bowls with the same parity. Next is just casework. If one of a,b is even, then a+b is odd and swapping fruits in the $i$ th and $a+b-i$ th bowl $\forall i<min(a,b)$ give the conclusion. If both a and b are even, we have a+b even, then swapping fruits between bowl $i$ and $k-i$ for odd i and between bowl $i$ and $k-i+2$ for even i will also give the conclusion. The last case is when both a and b are odd. Since the difference between the signed difference of the number of fruits in odd numbered bowls or even number bowls is always invariant, we can see that this value in the start is different from that in the end, so the process is impossible. Full proof here: https://infinityintegral.substack.com/p/usajmo-2019-contest-review

My own solution. Notation: I use AAA....BBB, where each A represent an apple, each B to represent a pear, to show the starting sequence. We say that there are a copies of the letter A, and b copies of the letter B. Part 1: We show that for ab even, it can be done. We assume that the number of A and number of B in the sequence are positive, since if there is either 0 copies of B or 0 copies of A, then it becomes absolutely trivial. Case 1: if a is even. Base case: AAB is easily achievable through the following swap sequence. (3->2 and 1->2), (2->1 and 3->1). Inductive step: We use strong induction. If we add 2 copies of A to the beginning sequence, when there are n previous copies of AA, we can cycle through the new AABs like the base case. If we add another B, when there are previously n Bs, we cycle through the iterations of AAB using the AAB operation again after finishing the n Bs off by inductive step. Case 2: If a is odd and b is even. Base case: abb works through the following swap sequence. (3->2 and 1->2), (2->1 and 3->1). Inductive step: same process as Case 1, except with the b in the place of the a. Part 2: Show that if a and b are both odd, then it doesn't work. From the given process it is obvious that a copie of A can only go to a place where there previously had been a B, or vice versa, if they are in positions along the numbered a+b length number line such that they have the same parity. Assume WLOG that there are at least as many copies of As than Bs (the other case is symmetric), so that a greater than or equal to b. In order to have the b copies of Bs as the leftmost b letters, there must be an equal number of As and Bs occurring in the same parity positions. However, that is false. So therefore the a, b both odd case doesn't work. So we have proved the statement and we are done.

My questions about my solution: Do I need to elaborate on the part about only moving to positions where they occupy the same parity position number? I am not sure if that is necessary since it is fairly obvious from the given rules. How can I make my induction more clear? I intended a 2-sided induction on both A and B, but I'm not sure how to phrase "what we assume to be true" in the inductive step.

We first show that if $ab$ is even then the goal is achievable, and proceed with induction. Base Cases: If $\min(a,b) = 0$, there is no work to be done. If $\min(a,b) = 1$, WLOG assume it's a singular apple, then we just swap the apple and the rightmost pear by only moving those two, which is always possible due to $b$ being even. Induction Steps: If $a,b$ are of opposite parity this means with a series of moves we can switch the apple at bowl $1$ with the pear at bowl $a+b$ by only moving those two (due to $a+b-1$ being even), this means we can effectively reduce the problem from $(a,b) \rightarrow (a-1,b-1)$ in this case, which is possible by induction as one of them must be even. If $a,b$ are both even this means with a series of moves we can switch the apple at bowl $1$ with the pear at bowl $a+b-1$ by only moving those two (due to $a+b-2$ being even), similarly we can also switch the apple at bowl $2$ with the pear at bowl $a+b$, reducing the problem from $(a,b) \rightarrow (a-2, b-2)$ in this case, which is again possible by induction. Now we show $ab$ cannot be odd. Notice that the difference of the number of apples in odd-numbered bowls and the number of pears in odd-numbered bowls does not change. But, (with $a,b$ both odd) we initially have $\frac{1}{2}(a+1)$ apples in odd-numbered bowls and $\frac{1}{2}(b-1)$ pears in odd-numbered bowls, while in the goal position we need to have $\frac{1}{2}(a-1)$ apples in odd-numbered bowls and $\frac{1}{2}(b+1)$ pears in odd-numbered bowls, so when $ab$ is odd the goal is not achievable. $\Box$