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.

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 ). 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.

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 ). 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

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.

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$

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.

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$

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.

This is a bit too easy for C6 imho

This problem was proposed by Adrian Beker, Croatia

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.

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$

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.

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

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.

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.

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.

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$.