Operations on Pebbles

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

Operations on Pebbles

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: ISL 2022 C6

The post below has been deleted. Click to close.

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

1595 posts

#1 h Jul 9, 2023, 4:39 AM

Y by

Let $n$ be a positive integer. We start with $n$ piles of pebbles, each initially containing a single pebble. One can perform moves of the following form: choose two piles, take an equal number of pebbles from each pile and form a new pile out of these pebbles. Find (in terms of $n$ ) the smallest number of nonempty piles that one can obtain by performing a finite sequence of moves of this form.

Z K Y

The post below has been deleted. Click to close.

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

1595 posts

#2 h Jul 9, 2023, 4:39 AM • 2 Y

Y by Stuffybear, bhan2025

Solution

Z K Y

The post below has been deleted. Click to close.

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

5005 posts

#3 h Jul 9, 2023, 4:52 AM • 1 Y

Y by centslordm

I can’t read

This post has been edited 1 time. Last edited by IAmTheHazard, Aug 5, 2023, 1:24 AM

Z K Y

The post below has been deleted. Click to close.

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

1740 posts

#4 h Jul 9, 2023, 2:54 PM • 2 Y

Y by math90, sabkx

Replace piles of stones with classrooms of students and replace the main character with Po.

Let $n$ be the total number of students and let $t$ be the greatest odd divisor of $n$ . The answer is 1 if $t$ divides the number of students in each class and 2 otherwise.

Remark: The intended solution goes along the lines of splitting the classes into groups of size powers of two, and then combining them. However, the below solution still works and is stronger.

We cite the following problem:

Lemma: [ISL 1994 C3] Peter has three accounts in a bank, each with an integral number of dollars. He is only allowed to transfer money from one account to another so that the amount of money in the latter is doubled. Prove that Peter can always transfer all his money into two accounts.

Proof. Without loss of generality the accounts contain $a<b<c$ dollars. I will show we can perform some moves to obtain an account with strictly fewer than $a$ dollars.

Write $b=ab'+r_1$ and $c=ac'+r_2$ , with $0\le r_1,r_2<a$ . Let $b'=(\overline{1b_{k-1}b_{k-2}\ldots b_0})_2$ in binary. Iterating over $i=0,1,\ldots,k-1$ , perform the following:

If $b_i=1$ then transfer money from the second account to the first account, doubling $a$ and removing the $b_i$ bit from $b'$ .
If $b_i=0$ then transfer money from the third account to the first account, doubling $a$ .

At the end the first account contains $2^ka$ dollars and the second account contains $2^ka+r_1$ dollars, so transferring money from the second account to the first account leaves the second account with $r_1<a$ liters. $\blacksquare$

While there are at least three classrooms, Po can take any three of them and rearrange them into two classrooms. Thus Po can arrange all the students into two classrooms. It suffices to show that arranging the students into one classroom is possible if and only if $t$ divides all the class sizes.

Proof of necessity: If initially there is a class whose size is not divisible by $t$ , then there will always be a class whose size is not divisible by $t$ . Thus we cannot ever have a single class of size $n$ .

Proof of sufficiency: Divide all sizes by $t$ , so we may assume $n=2^k$ is a power of 2. As above, arrange the students into two classes. Then if the classes have positive size $a$ and $b$ , we must have $\nu_2(a)=\nu_2(b)$ .

Then the operation $(a,b)\mapsto(2a,b-a)$ increments $\nu_2(a)=\nu_2(b)$ until it no longer less than $k$ , at which point $(a,b)=(0,2^k)$ and we are done.

Z K Y

The post below has been deleted. Click to close.

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

1595 posts

#5 h Jul 10, 2023, 2:21 PM • 1 Y

Y by GeoKing

I was told by the team leader that this above post is the problem statement from the shortlist without any changes. However, the only way I can confirm this is to wait until they upload the shortlist (which hasn't been done yet :play_ball:

:play_ball:

).

Also @TheUltimate123, I think your solution is solving a generalization of this problem that one does not have to start with one pile. Most likely, I think it is because they edited the problem for the MOP tests.

Z K Y

The post below has been deleted. Click to close.

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

5005 posts

#6 h Jul 10, 2023, 2:45 PM • 1 Y

Y by centslordm

MarkBcc168 wrote:

I was told by the team leader that this above post is the problem statement from the shortlist without any changes. However, the only way I can confirm this is to wait until they upload the shortlist (which hasn't been done yet :play_ball:

:play_ball:

).

Also @TheUltimate123, I think your solution is solving a generalization of this problem that one does not have to start with one pile. Most likely, I think it is because they edited the problem for the MOP tests.

Never mind, I can’t read. The original version was indeed the one posted. The version black/blue received allowed the piles to start with any number of pebbles

Z K Y

The post below has been deleted. Click to close.

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

3151 posts

yofro

#8 h Jul 11, 2023, 1:37 AM • 2 Y

Y by Stuffybear, sabkx

Same solution as post #2 but with a different construction for non-powers of $2$ :

Let $n=2^{a_1}+2^{a_2}+\cdots+2^{a_k}$ be the binary representation of $n$ , with $a_1>a_2>\cdots>a_k$ . Separate the $n$ piles into groups of size $2^{a_i}$ for each $i$ . Collapse these groups so that we have $k$ groups with the $i$ th group having $2^{a_i}$ pebbles. Now take $2^{a_k}$ pebbles from the $1$ st group and the $k$ th group to form a group of $2^{a_k+1}$ pebbles. If $a_k+1=a_{k-1}$ condense the two piles into $1$ , else take $2^{a_k+1}$ pebbles from the $1$ st group and the new group to form another group with $2^{a_k+2}$ pebbles. Continuing this process we eventually have $k-1$ piles. Running the same process eventually leads to $2$ piles. Because $2^{a_1}>2^{a_2}+2^{a_3}+\cdots+2^{a_k}$ we never run into a negative amount of pebbles in the first group.

Z K Y

The post below has been deleted. Click to close.

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

5611 posts

#9 h Jul 12, 2023, 3:27 PM • 2 Y

Y by OronSH, Inconsistent

Solved with OronSH, Spectator, pi271828.

Let $f(n)$ denote this number. We claim that $\begin{cases} f(n) = 1 & \text{if } n \text{ is a power of } 2 \\ f(n) = 2 & \text{otherwise } \\ \end{cases}$
Construction for powers of $2$ :
We show that we can turn $n = 2^k$ into one pile for any nonnegative integer $k$ . We induct on $k$ with base case $k = 0$ . If it was true for $k-1$ , then we can split $2^k$ piles of one pebble into two piles with size $2^{k-1}$ by the inductive hypothesis, and then combine them for a single pile with size $2^k$ .

Construction for non powers of $2$ :
Let the binary representation of $n$ be equal to $2^{a_k} + 2^{a_{k-1} } + \cdots + 2^{a_1}$ , where $a_k > a_{k-1} > \cdots > a_1$ . Then using our power of $2$ construction, we can make $k$ piles, where the $i$ th pile has $2^{a_{k - i + 1}}$ pebbles. Now, we can take away $2^{a_1}$ pebbles from the first and last piles, and our last pile now becomes $2^{a_1 + 1}$ . If this is equal to $2^{a_2}$ , we can combine them. If not, we can repeat the process until the last pile has $2^{a_2}$ pebbles, and then combine. After this, we repeat the process until we have only $2$ piles left. This will always be fine because $2^{a_k} >2^{a_k - 1} + 2^{a_k - 2} + \cdots + 2^0$ , so the first pile won't run out of pebbles.

Proof that you can't get $1$ with non powers of $2$ :
Claim: For any odd prime $p$ , there always exists some pile with size not divisible by $p$ .
Proof: Suppose not and we at some point had all piles with size divisible by $p$ . Let the last arrangement of piles before the first time this happens be $(a_1, a_2, \ldots, a_t)$ . Since $(1,1,\ldots,1)$ has no multiples of $p$ , there exist some $a_i$ that are not divisible by $p$ . Now WLOG the arrangement of the piles becomes $(a_1 - k, a_2 - k, a_3, a_4, \ldots, a_t, 2k)$ . Then $a_1 - k, a_2 - k, 2k, a_3, a_4, \ldots, a_t$ are all divisible by $p$ . This implies that $2k\equiv 0\pmod p$ , so $p\mid k$ . Thus, $p$ divides $a_1$ and $a_2$ . Then $p$ divides everything in $(a_1, a_2, \ldots, a_t)$ , which is a contradiction. $\square$

This post has been edited 2 times. Last edited by megarnie, Feb 14, 2024, 9:38 PM

Z K Y

The post below has been deleted. Click to close.

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

821 posts

#10 h Jul 12, 2023, 7:48 PM • 1 Y

Y by megarnie

The answer is $1$ if $n$ is a power of $2$ and it's $2$ otherwise. Notice that we can easily get to $1$ pile when $n$ is a power of two simply by merging piles together going down the line and repeating until $1$ pile remains

Claim 1: If $n$ is not a power of two, then we can get down to $2$ piles.
Proof: Again, like above, merge piles together keeping each pile to have a number of stones equal to a power of $2$ . Notice that we can do this until the piles are the binary representation of $n$ (an example is for $1434$ merge until we have piles of $1024,256,128,16,8,2$ ) by simply designating certain starting piles to be merged into powers of two (again as an example for $1434,$ designate the first $1024$ to be merged into the $1024$ pile and so on). Then, once we have these piles, let there be $k$ of them and say the largest has size $2^l$ . What we do is go down in a line from the second pile to the last and perform a moves on pile $i$ pile $1$ (taking all pebbles from pile $i$ ) and putting the end result, twice the number of pebbles in pile $i$ as we started with, back in the spot $i$ . Them, repeat this on pile $i$ until it has $2^{l-i+1}$ pebbles or in the case of the last pile, $2^{l-k+2}$ . This will leave us with piles of size $n-2^l,2^{l-1},2^{l-2},\dots,2^{l-k+2},2^{l-k+2}$ and then merge from the left to the right to get $n-2^l, 2^l$ as the pile sizes as desired.

Claim 2: If $n$ is not a power of $2$ , we can't get down to only $1$ pile.
Proof: If $n$ is not a power of $2,$ it has an odd divisor $>1,$ call it $d$ . Looking at the process backwards, the final outcome is divisible by $d$ , and I claim that every pile size ever must also be divisible by $d$ (obviously yielding a contradiction as $d$ doesn't divide $1$ ). To see why this is true, notice that a move sends $(x,y)$ to $(x-k,y-k,2k)$ . As $d$ is odd and $d\mid 2k$ , we see $d\mid k$ and similarly $d \mid x,y$ and the claim is proven.

Putting these two claims together implies the result.

This post has been edited 1 time. Last edited by GrantStar, Jul 12, 2023, 7:49 PM

Z K Y

The post below has been deleted. Click to close.

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

559 posts

#11 h Jul 21, 2023, 7:57 PM

Y by

We claim the answer $1$ if $n$ is a power of $2,$ and answer $2$ otherwise.

Firstly, it's trivial that for $n=2^k$ we can unite all pebbles in one pile (for $i=k-1,\ldots ,1,0$ we consequently form $2^i$ piles with $2^{k-i}$ pebbles in each). Assume next $n=2^m+r$ for $m,r\in \mathbb Z^+,$ $r<2^m.$

Construction of two piles. For the beginning unite $2^m$ pebbles in one pile (without moving other pebbles) - call this pile major. Next take $1$ pebble from major pile and $1$ from one of the other $r\geq 1$ piles to form a new pile of $2$ pebbles. Now, until major pile has more than $r$ pebbles, form a new pile of $2$ pebbles with $1$ pebble from major pile and $1$ pebble from pile with size $2.$ At the end major pile will have $r$ pebbles, some pile will have $2$ pebbles, and others will have $1$ pebble - obviously all piles, except for the major, can be united in one. Thus we are done $\Box$

Bound for two piles. It suffices to prove, that at any moment there exist a pile, whose size isn't divisible by a fixed odd divisor $t>1$ of $n;$ this is clearly true for the initial configuration. FTSOC there exist a first operation $(a,b)\to (a-c,b-c,2c),$ after which this property fails. Then $t\mid 2c \implies t\mid c,$ and so $t\mid a,b.$ This clearly contradicts with definition of taken operation $\Box$

This post has been edited 1 time. Last edited by JAnatolGT_00, Jul 21, 2023, 7:58 PM

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1737 posts

awesomeming327.

#12 h Aug 5, 2023, 12:07 AM

Y by

We claim that the answer is $1$ if $n$ is a power of $2$ . Clearly, from two piles of size $2^{n-1}$ we can form a single pile of size $2^n$ , so by induction this is true.

We claim that the answer is $2$ otherwise. First, we'll show that we can't make it into a single pile if $n$ is not a power of $2$ . Let $p$ be an odd prime divisor of $n$ . Clearly, if there is one pile left then there are zero piles whose pebble count is divisible by $p$ . Thus, at some point we have gotten rid of the last pile with such a pebble count. Suppose this move was $(a,b)\to (a-c,b-c,2c)$ where $a-c,b-c,2c$ are all divisible by $p$ but either $a$ or $b$ isn't. This is clearly impossible.

We claim that it is always possible to form two piles for odd $n$ . Now, we prove the stronger claim that for $n$ odd. We in fact claim that we can obtain piles with pebble counts of $1$ and $n-1$ . Soft induct on $n$ , with trivial base cases. Suppose it is true for $n-2$ then we can make the configuration $(1,1,1,n-3)\to (1,1,n-4,2)\to (n-4,4)$ . If we are given $(a,b)$ , we can let it become $(a-b,2b)$ or $(b-a,2a)$ whichever is the one that has both as nonnegative. Consider $\pmod n$ , both piles are doubled, so eventually we will reach $(n-1,1)$ as desired.

Now, we can extend to the even $n$ by seeing that with a power of two number of piles, with each pile having $n$ , we can do the same thing as we did with powers of two in the beginning, so we're done.

Z K Y

The post below has been deleted. Click to close.

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

Fibonacci_11235

45 posts

Fibonacci_11235

#13 h Aug 10, 2023, 10:18 PM

Y by

This is a bit too easy for C6 imho

Z K Y

The post below has been deleted. Click to close.

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

Fibonacci_11235

45 posts

Fibonacci_11235

#14 h Aug 15, 2023, 3:18 PM

Y by

This problem was proposed by Adrian Beker, Croatia

Z K Y

The post below has been deleted. Click to close.

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

1455 posts

#15 h Aug 18, 2023, 6:16 AM • 1 Y

Y by TheHimMan

This problem is peak combo comedy

brilliant!

Answer is $1$ if power of two and $2$ else.

First we construct all odd numbers via induction. I claim for each odd number $n$ we can construct piles of $2, n - 2$ . $n = 3$ is trivial. Now to go from $n$ to $n+2$ , simply construct $1, 1, 2, n - 2$ , then merge the leftmost piles to get $4, n - 2$ . Now notice that if you have two piles and merge all of the smaller pile, you get a new pair of an even and an odd pile. In fact, you can determine which pair of two piles you came from if you restrict to performing this operation, as the even pile tells you how many stones were merged. Thus this operation forms a permutation on the space of two piles. Since $2, n$ goes to $4, n - 2$ in this space for $n \geq 3$ , it follows that one can eventually obtain $2, n$ from $4, n - 2$ , finishing the induction.

Now for all non-powers of two which are $n = 2^ak$ where $k\geq 3$ is odd, just merge into $k$ piles of $2^a$ and finish construction by reduction. For powers of two the construction is obvious.

Now we prove the upper bound. The power of two case is trivial, so it suffices to show non-powers of two do not have a construction for one pile. Assume there is such a construction, then imagine the state right before the final state for $n = 2^ak$ for odd $k \geq 3$ . Notice that every pile must be a multiple of $k$ , since the even pile created in the next step (if there is any), must be a multiple of $k$ . Thus this property is preserved going backwards, but the initial state is $n$ copies of $1$ , none of which are multiples of $k$ , giving 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.

1924 posts

#16 h Nov 24, 2023, 7:25 PM

Y by

For the rest of this proof, include $1$ as a power of $2$ .

The answer is
$\boxed{ \begin{cases} 1 & \text{if }n\text{ is a power of }2 \\ 2 & \text{otherwise} \end{cases} }.$
Rephrase the problem so that we have numbers on a blackboard(representing the sizes of the piles).

Construction. We will first prove that a specific move is possible.

The Doubling Move. If there are two numbers $a$ and $b$ such that $a\ge b$ , then we can make them $a-b$ and $2b$ , respectively. In particular, if $a=b$ , then the $a-b$ also disappears and we are left with $2b$ .
Proof. This is just subtracting $b$ from both numbers and forming the number $2b$ as the new pile.

Call the doubling move when $a=b$ the merging move.

Now we will provide an algorithm to reach our answer.

- Greedily merge pairs of numbers until it is impossible to do so; this will leave us with a binary representation of $n$ . If $n$ is a power of $2$ , the algorithm has already finished.
- Now apply doubling moves with the largest number. Repeatedly double the smallest number until it is equal to the second smallest number, then merge those, etc, until we have two numbers left.

Example:
n = 53 -> 32 16 4 1 -> 31 16 4 2 -> 29 16 4 4 -> 29 16 8 -> 21 16 16 -> 21 32

In particular, note that the largest number is larger than the sum of the rest, so this process must work.

Now we will prove that it is impossible to have one number left on the board after finitely many moves if $n$ is not a power of $2$ .

Let $k$ be the largest odd divisor of $n$ . Since $n$ is not a power of $2$ , $k\ge 3$ . For a set of numbers on the board, call its coolness the number of numbers on the board that are not divisible by $k$ . Clearly one move can reduce the coolness of the board by at most $2$ . Since the coolness of the final board is $0$ , there must be some last position with a coolness of either $1$ or $2$ . Clearly the coolness cannot be $1$ (take mod $k$ ), so a move took a position with a coolness of $2$ to a coolness of $0$ . Say that the move acted on $a$ and $b$ and made the piles $a-c$ , $b-c$ , and $2c$ . Then $k\mid 2c$ , so $k\mid c$ . Also, $k\mid a-c$ , so $k\mid a$ , which violates the original coolness of $2$ , contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

7585 posts

#17 h Dec 20, 2023, 6:55 PM • 1 Y

Y by Inconsistent

thank

Pile $p$ refers to the pile itself and $p$ simultaneously refers to the size of the pile.

Let's show that $2$ or less piles is always possible. Write $n=2^a+b$ and $1\le b<2^a$ (if $b=0$ we're clearly done).

Lemma: Given an arbitrary configuration of piles with total $2^a$ pebbles, we can reduce to a single pile with $2^a$ pebbles.
Proof: Pretty algorithmic. Note $a\ge 1$ . Just take any two piles $p,q\ne 2$ and remove $1$ pebble from each pile until one pile is gone or one pile is equal to $2$ . This decreases the number of piles not equal to $2$ . If there is a single pile not equal to $2$ , it must have $p\equiv 0\pmod 2$ . Hence take
$(p,2)\to (p-1,1,2)\to (p-2,2,2)$ and so clearly we can reduce to all piles being equal to $2$ . Now just take the obvious combination approach:
$(2,2,2,2)\to (4,4)\to (8)$ is easily generalizable.

Now we show that $2$ piles is possible. As long as there is a pile of size $b$ , then the rest of the pebbles can be merged into a pile of size $2^a$ . Hence merge into
$(1,\dots,1)\to (2^a,1,\dots,1)$ and let the first pile be $p$ . Now since another pile $q$ must exist just take
$(p,q)\to (p-1,q-1,2)$ and we continue applying this until $p=b$ . Hence done.

Now we show that if $n=2^a\cdot b$ and $b>1$ then we can't form a single pile. Suppose otherwise and work backwards. We induct to show that all piles are always divisible by $b$ , a contradiction. At any point, we essentially take a pile $p$ from the current configuration, delete it, then add $p/2$ to some (possibly nonexistent) two distinct piles. Since $b\mid p/2$ we're fine.

So the answer is $1$ when $n=2^a$ and $2$ otherwise.

Z K Y

The post below has been deleted. Click to close.

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

23 posts

Toll

#18 h Jan 15, 2024, 6:14 PM

Y by

We claim that the smallest number of piles that can be achieved is $1$ if n is a power of $2$ , and 2 otherwise.

$\textit{Lemma 1:}$ it is always possible to reach a single pile if the initial configuration is a power of 2
$\textit{proof:}$ let $n=2^k$ for some $k$ . Group all initial piles in pairs of 2, and then combine those pairs into a single pile. We are now left with $2^{k-1}$ piles of size 2. Do that pairing and combining again, and we will eventually have $1$ pile left

$\textit{Lemma 2:}$ We are always able to construct two piles if $n$ is not a power of $2$
$\textit{proof:}$ The idea is to consider the binary representation of $n$ . let $t_1 < t_2 < \dots < t_k$ all be powers of 2 whose sum is $n$ . We therefore know that $t_1 > \sum_{i=2}^k t_i$ . First, we partition $n$ into sets of those sizes and put those together into singular piles that all have sizes of powers of $2$ . Call the pile of size $t_1 = A$ .
Now we simply can do the following algorithm: If there are two piles of the same size, then combine those into a single pile. If there aren't two piles of the same size, then choose the pile with the smallest size and pile $A$ , and apply the move with the value of the size of the smallest pile. It is clear that this process will result in $2$ piles left ( $1$ if $n$ is a power of $2$ )

Now all it remains to show is that it is impossible to reach a single pile if $n$ is not a power of $2$ . For this, let $p$ be some prime that is not $2$ such that $p\mid n$
If we would be able to reach a single pile, that would mean that $p$ divides the sizes of all the piles.
Now assume at any point, $p$ divides the size of every pile. That would mean that $p$ divides the size of the most recently created pile, say it has size $2m$ . by that, $p\mid m$ . Since $p$ divides all the sizes of the piles and $p \mid m$ , it also means it divided the size of the two piles that we took pebbles from the previous round, which means that it also divided the size of all the piles in the previous round. But since initially, $p$ didn't divide all the sizes of the piles, that can't happen and we can't reach a single pile

Z K Y

The post below has been deleted. Click to close.

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

499 posts

#19 h Mar 22, 2024, 11:40 PM

Y by

Case 1: $n$ is a power of $2$
We can just combine all the pebbles to make 1 pile.
Case 2: $n$ is not a power of $2$
We claim the answer is $2$ . Let $m$ be the highest integer such that $2^m<n$ . Then, create a pile with $2^m$ pebbles. Assume there are $a$ lone pebbles remaining. Let $a\le 2^k < 2a$ . Then, $2^k-a$ times, take a lone pebble and combine it with a pebble from the $2^m$ pile to create a pair of pebbles. Then, there are $2^k$ pebbles that are not in the big pile, and each one is in a pile of $1$ or $2$ . So, we can combine them to make a pile of size $2^k$ .

Now we will show it's impossible for there to be $1$ pile.

Claim: it is impossible for the number of pebbles in each pile to have a common prime factor $p\neq 2$ .
Proof: Assume towards a contradiction that this condition is true at some point. Then, consider the move that changes the condition from being false to being true. Say two piles $a$ and $b$ each have $k$ taken from them to form a new pile of size $2k$ . So, $p\mid k$ , $p\mid a-k$ , and $p\mid b-k$ . So, $p\mid a, b$ , so the condition was already true, a contradiction.

If there is $1$ pile, then all the piles have $n$ as a factor. However, $n$ has an odd prime factor, a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

27 posts

#20 h Apr 18, 2024, 1:56 AM

Y by

The answer is $1$ if $n$ is a power of $2$ and $2$ otherwise.
First we prove the result when $n$ is a power of $2$ : this is not hard by inductively constructing $2$ piles of size $\frac{n}{2}$ and then merging them together with a single move

We prove the upper bound for $n$ that is not power of $2$ .

Consider the decomposition of $n$ into distinct powers of $2$ (which can be obtained by writing $n$ in binary)
Say we have
$n=2^{v_1}+2^{v_2}+…2^{v_m}$ where
$v_1>v_2>\dots>v_m$ We perform moves as follows: first start with the smallest power of $2$ , say $2^k$ .
Then use the $2^{v_1}$ pile, removing $2^k$ from both piles in order to double its value.
Repeat until it is as large as another power of $2$ , say $v_c$ . Then we combine the two piles to obtain $2^{v_c+1}$ .
In this case, we would eventually combine all of $2^{v_2}, \dots 2^{v_m}$ into $2^{v_2+1}$ .

It remains to show that the $2^{v_1}$ pile does not run out of pebbles.
But this is true since we only removed distinct powers of 2 whose values are at most $2^{v_2} \leq 2^{v_1-1}$ ,
implying their sum is less than $2^{v_1}$ .
Hence at the end of the process we are left with 2 piles, one of which has size $2^{v_2+1}$ .

We now prove the lower bound.
Since $n$ is not a power of $2$ , it has an odd prime divisor $p$ .
Note if it is possible to only obtain 1 pile, then the final pile is clearly a multiple of $p$ .
Consider a move, which has the form
$(a,b) \rightarrow (a-x, b-x, 2x)$ If all terms at the end are multiples of $p$ , then $x$ and hence $a,b$ are multiples of $p$ .
In other words if before a move all piles are multiples of $p$ then the same can be said before that move was made.
Hence working backwards we obtain that at the start all the piles, which are of size $1$ , are multiples of $p$ , a contradiction.

Hence the result follows.

Z K Y

The post below has been deleted. Click to close.

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

917 posts

#21 h May 13, 2024, 12:26 AM

Y by

Nice Combo!

The answer is $1$ if $n$ is a power of $2$ and $2$ otherwise.

Construction:
If $n$ is a power of $2$ the construction is pretty obvious. Otherwise let $2^k< n< 2^{k+1}$ and let $n=2^k+l$ . Then create a stack of size $2^k$ . Notice their must be some $m$ in between $l$ and $2l$ that is a power of $2$ . Create $m-l$ piles of size $2$ using the reaming $1$ 's and the stack of size $2^k$ . Once you are done then you can create a stack of size $m$ giving two stacks in total.

Bound:
Let $a$ be an odd divisor of $n$ larger than $2$ . Considering the process in reverse we start with a pile of $n$ and if we ever have a pile of even size we can split it in half and put each half anywhere. We will never get to all $1$ 's as all the piles clearly contain a multiple of $a$ stones.

Z K Y

The post below has been deleted. Click to close.

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

3449 posts

#22 h Aug 6, 2024, 5:24 PM

Y by

The answer is $2$ for a non-power of two and $1$ for a power of $2$ . The powers of $2$ case is obvious, so we consider when $n$ is not a power of $2$ .

To obtain two piles: first, merge piles until the sizes of the piles are powers of $2$ that form the binary representation of $n$ – call the largest pile the "supplier" pile. If there are two piles of stones with $a$ and $b$ stones such that $a \geq b$ , we can take $b$ stones from both piles, leaving us with piles of size $2a$ and $b-a$ , letting us double piles.

We will repeatedly use this operation on the supplier pile and the smallest pile, merging the smallest pile with the second smallest pile whenever possible. Once we are done, there will be just two piles. It is clear that we will never run out of pebbles in the supplier pile (although it may not be the largest pile after the last operation).

To prove we can't get one pile: consider the operation mod $p$ , where $p$ is an odd prime. Suppose there are two piles with $a$ and $b$ pebbles and we take $c$ pebbles out of each. Assuming at least one of $a$ or $b$ is not a multiple of $p$ , it follows that at least one of $a-c, b-c$ and $2c$ is also not a multiple of $p$ , so for any odd prime $p$ , there is at least one pile which is not a multiple of $p$ .

This post has been edited 1 time. Last edited by ihatemath123, Aug 6, 2024, 5:25 PM

Z K Y

The post below has been deleted. Click to close.

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

1556 posts

#23 h Jan 27, 2025, 1:23 AM

Y by

We prove that the answer is $1$ if $n$ is a power of two and $2$ otherwise.
Clearly if $n=2^k$ it is trivial as you can just get pilars of $2$ and then all of $4$ and so on until one of $2^k$ .
Else if you consider $n$ in binary, that if $n=\sum_{i=1}^{k} 2^{a_i}$ where $a_1>a_2> \cdots a_k$ , notice $2^{a_i}>2^{a_i-1}+\cdots+1$ due to notable quotient formula which means that, if we make piles containing $2^{a_i}$ pebbles of each, then take $2^{a_k}$ pebbles from the piles with $2^{a_1}$ and $2^{a_k}$ , to make a new pile with $2^{a_k+1}$ pebbles then whenever we do this we get two piles of the same number of pebbles, we merge them and then continue until it's no longer possible, however since $2^{a_1}$ is the biggest of all, it will never run out of pebbles to make new piles with, which means that the process can be stopped when there is only $2$ piles remaining. in which case the one who had the biggest number of pebbles now has $a$ pebbles where $\nu_2(a)=a_k$ , which means that it won't be able to get merged with the remaining pile that has a non-zero amount of pebbles, so you can get two non-empty piles this way.
Finally to prove we can't have exactly one pile ever, consider $p$ an odd prime divisor of $n$ then when you have like $(x,y)$ for $x>y$ then the process makes it go $(x-z,y-z,2z)$ for some $y \ge z$ , and if all piles here also shared the common odd prime divisors $p$ then clearly $p \mid x,y,z$ as well which means that, if at any point we had that all piles have multiple of $p$ rocks, considering the previous arrangement to that, it happens that it should also have all multiple of $p$ works, but then clearly $p \mid 1$ cannot happen, therefore $1$ pile cannot be attained and thus we are done :cool:

:cool:

.

This post has been edited 1 time. Last edited by MathLuis, Jan 27, 2025, 1:23 AM

Z K Y

The post below has been deleted. Click to close.

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

363 posts

#24 h Feb 24, 2025, 2:03 AM

Y by

This feels... really easy for its placement?

For the algorithm, I found the same one as the post above. It's pretty easy to motivate by experimenting with random pile size distributions, like $4, 5, 6$ .

For the optimality of $2$ piles when $n$ isn't a power of $2$ , assign weights to stones based on the piles they're in. Initially, let $n-1$ of the stones have weight $0$ and the remaining stone have weight $1$ . Now, every time we create a new pile with stones of weights $i$ and $j$ , reassign all their weights to $\tfrac{i + j}{2}$ . We have two invariants: the sum of weights over all the stones is $1$ and the denominator of the weight of each stone is a power of $2$ . If all the stones get assigned to a single pile, then the number of stones in the pile is a power of $2$ .

This post has been edited 5 times. Last edited by Blast_S1, Feb 24, 2025, 3:08 AM

Z K Y

The post below has been deleted. Click to close.

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

115 posts

#25 h Apr 25, 2025, 8:36 AM

Y by

Super scam problem lmao. The answer is
$\boxed{ \begin{cases} 1 & \text{if }n\text{ is a power of }2 \\ 2 & \text{otherwise} \end{cases} }.$ When $n$ is a power of two, its trivial to get all stone to one pile. When $n$ is not a power of two, it would have some odd prime factor $p$ and its easy to see that at the end of every turn, there will be some pile that doesnt have a multiple of $p$ stones, implying that all $n$ stones cant be in the same pile since $p\mid n$ by assumption.

For the construction, we forcefully reduce the number of piles one by one till we reach two. This can be done by taking three piles and then reducing them to two within themselves(how to do so is not trivial but I wont go over the details)

Z K Y

The post below has been deleted. Click to close.

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

84 posts

#26 h Apr 26, 2025, 5:09 AM

Y by

This is cool. The answer is $1$ if $n$ is a power of $2$ and $2$ if $n$ is not a power of $2$ .
Construction
Suppose $n$ is power of $2$ , the construction is to turn $2^s$ piles of size $2^d$ to $2^{s-1}$ piles of size $2^{d+1}$ .
Now, suppose $n$ is not power of $2$ . We claimed that constructing piles of $2^{\lfloor log_2n \rfloor}, n- 2^{\lfloor log_2n\rfloor}$ is always possible.
First, we construct the piles of the size $2^{\lfloor log_2n \rfloor}$ the same way we do for $n = 2^k$ . We call this pile $S$ . Now, we select $2$ piles $a,b$ of size $1$ . Note that we can take out a pebble from $S$ , by taking $1$ pebbles from both $S$ and $a$ or $b$ to form a new size $2$ piles $a_1, b_1$ . Then we take $1$ pebbles from both $a_1, b_1$ to revert it back to $2$ piles of $1$ pebbles. Now, we repeat this until $S$ has $n- 2^{\lfloor log_2n\rfloor}$ pebbles. After that, we construct a piles of the size $2^{\lfloor log_2n\rfloor}$ with all the pebbles that doesnt belong to $S$ in the same manner as the case $n = 2^k$ .

Bound
Here, we need to show that if we can reach a single pile state in finite number of moves, then $n$ is power of $2$ .
Note that there are $n$ pebbles, thus there should be no more than $n$ piles of pebble formed.
We denote the number of pebbles in those piles as a nonnegative integers $a_1, a_2, a_3, \dots, a_n$ .
Claim : $\gcd(a_1, a_2, \dots, a_n)$ is always a power of $2$ .
Proof: Denote $\gcd(a_1, a_2, \dots, a_n) = d$
Note that initially $d=1$ , which is power of $2$ . For any positive integer $d$ , let $f(d)$ denotes its largest odd divisor.
Note that its suffice to show that, regardless of the moves, we always have $f(d) =1$ .
Suppose that we choose $2$ piles $(x,y)$ to form $(x-k, y-k, 2k)$ .
Consider the identity $f( \gcd(x-k, y-k, 2k) ) = f( \gcd(x, y, k) ) \mid f(\gcd(x,y))$ That is after the move the term $\gcd(a_1, a_2, \dots, a_n)$ changes from $d$ to $d’$ , it follows that $f(d’) \mid f(d) =1$ Thus, $f(d’) = 1$ . So, regardless of the move the term $f(d)$ is always $1$ . In other words, $d$ is always a power of $2$ . $\blacksquare$

Note that the term $\gcd(a_1, a_2, \dots, a_n)$ in the single pile state is equal to $n$ , hence by the claim, $n$ is a power of $2$ , as desired.

This post has been edited 1 time. Last edited by EeEeRUT, Apr 26, 2025, 5:10 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a