Apple sharing in Iran

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Apple sharing in Iran

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Iran 2025 second round p6

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

103 posts

#1 h Apr 20, 2025, 4:17 AM • 1 Y

Y by sami1618

Ali is hosting a large party. Together with his $n-1$ friends, $n$ people are seated around a circular table in a fixed order. Ali places $n$ apples for serving directly in front of himself and wants to distribute them among everyone. Since Ali and his friends dislike eating alone and won't start unless everyone receives an apple at the same time, in each step, each person who has at least one apple passes one apple to the first person to their right who doesn't have an apple (in the clockwise direction).

Find all values of $n$ such that after some number of steps, the situation reaches a point where each person has exactly one apple.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1541 posts

#2 h Apr 20, 2025, 5:07 AM • 2 Y

Y by sami1618, jannatiar

Very nice problem. Sketch I will clean up later:

$n$ which are powers of $2$ work inductively as it goes from $2^k$ to two copies $2^{k-1}$ which are apart, this decays into all ones.

$n$ which are equal to $2^k + r$ turn into a $2^k$ and $r$ component with $2^k - 1$ and $r - 1$ zeros before them. The $2^k$ acts like an inch worm which jumps every $2^k$ so it can't ever hit the $r$ from one direction. The $r = 2^a + s$ decays the same way so we can finish inductively to get that it never is all ones. Thus this ends up becoming $2^i$ inch worms in different states which never have the same all $1$ time which gives the result.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

908 posts

#3 h Apr 20, 2025, 8:03 PM • 1 Y

Y by jannatiar

Answer: $n=2^k$ for all non-negative integers $k$ .

Solution: We will show that if $n$ is a power of $2$ then eventually each person will have exactly one apple, and if $n$ is not a power of $2$ this will not happen.

Assume that $n=2^k$ . We claim that after $2^k-1$ steps, everyone will have exactly one apple. We proceed by induction on $k$ . The base case $k=0$ is trivial. For the induction step, assume that the result holds for $k$ and we will show it holds for $k+1$ . Notice that for each of the first $n-1$ steps the range of people that have an apple will expand by one in the clockwise direction. Thus no apple will make its way around the circle in the first $n-1$ moves, so we can imagine "cutting" the circle to the left of Ali and only considering the passing in straight line. By the inductive hypothesis, after $2^k-1$ moves, Ali will be left with $2^k+1$ apples, the $2^k-1$ friends to the right of Ali will have exactly $1$ apple, and no one else has apples yet. After $1$ more step, Ali will be left with $2^k$ apples, the friend $2^k$ spots to the right of Ali will also have $2^k$ apples, and no one else will have apples. Thus by the inductive step, after another $2^k-1$ steps all $2^{k+1}$ people will have exactly $1$ apple. This completes this part of the solution.

Now we prove two claims.

Claim 1. All such $n\neq 1$ are even.
Proof. Assume $n\neq 1$ works. Consider the situation one step before everyone gets an apple. Everybody having at least one apple must have exactly $2$ apples in order to end up with just $1$ apple after the step. Then $2|n$ , as claimed.

Claim 2. If $n=2k$ works, then $n=k$ also works.
Proof. Consider the party with $n=2k$ people. Let $A$ denote the set of $k$ people which are an even number of seats away from Ali and let $B$ denote the set of the other $k$ people. We claim that after every two steps, only the people in $A$ will have apples, and each of them will have an even number of them. Additionally, the people in $A$ function as a party of $k$ people where every two steps it is as if they pass with $2$ apples instead of $1$ . Notice that this is true from the beginning. Now consider a person in $A$ that has no apples and is adjacent (to the left) to a block of friends in $A$ with apples. After the first step all the people in $B$ in front of a person from the block will receive $1$ apple. The person to the left of the block still does not have an apple so after the second move all the apples received by people in $B$ plus one additional apple from each person from the block of friends in $A$ will go to the person in consideration. Thus effectively, after two steps, the people in $B$ just helped "passing" the apples and returned to having no apples, while the people in $A$ functioned as a sub-party with $k$ people and twice as many apples. This only stops when everyone in $A$ has exactly $2$ apples, in which case we can not consider a person in $A$ that has no apples and thus after one more step, everyone will have an apple. But by examining our sub-party, this means that $n=k$ must also work, as claimed.

Now if $n$ is not a power of $2$ , then express $n$ as $2^k\cdot m$ for a non-negative integer $k$ and an odd integer $m\geq 3$ . By Claim 2, if $n$ works then $m$ must also work. But by Claim 1, this is a contradiction, as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

13 posts

#4 h Apr 23, 2025, 4:53 AM

Y by

Here you can find some solutions
https://t.me/matholampiad123

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a