Stay ahead of learning milestones! Enroll in a class over the summer!

G
Topic
First Poster
Last Poster
k a May Highlights and 2025 AoPS Online Class Information
jlacosta   0
May 1, 2025
May is an exciting month! National MATHCOUNTS is the second week of May in Washington D.C. and our Founder, Richard Rusczyk will be presenting a seminar, Preparing Strong Math Students for College and Careers, on May 11th.

Are you interested in working towards MATHCOUNTS and don’t know where to start? We have you covered! If you have taken Prealgebra, then you are ready for MATHCOUNTS/AMC 8 Basics. Already aiming for State or National MATHCOUNTS and harder AMC 8 problems? Then our MATHCOUNTS/AMC 8 Advanced course is for you.

Summer camps are starting next month at the Virtual Campus in math and language arts that are 2 - to 4 - weeks in duration. Spaces are still available - don’t miss your chance to have an enriching summer experience. There are middle and high school competition math camps as well as Math Beasts camps that review key topics coupled with fun explorations covering areas such as graph theory (Math Beasts Camp 6), cryptography (Math Beasts Camp 7-8), and topology (Math Beasts Camp 8-9)!

Be sure to mark your calendars for the following upcoming events:
[list][*]May 9th, 4:30pm PT/7:30pm ET, Casework 2: Overwhelming Evidence — A Text Adventure, a game where participants will work together to navigate the map, solve puzzles, and win! All are welcome.
[*]May 19th, 4:30pm PT/7:30pm ET, What's Next After Beast Academy?, designed for students finishing Beast Academy and ready for Prealgebra 1.
[*]May 20th, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 1 Math Jam, Problems 1 to 4, join the Canada/USA Mathcamp staff for this exciting Math Jam, where they discuss solutions to Problems 1 to 4 of the 2025 Mathcamp Qualifying Quiz!
[*]May 21st, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 2 Math Jam, Problems 5 and 6, Canada/USA Mathcamp staff will discuss solutions to Problems 5 and 6 of the 2025 Mathcamp Qualifying Quiz![/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

Calculus
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

AIME Problem Series A
Thursday, May 22 - Jul 31

AIME Problem Series B
Sunday, Jun 22 - Sep 21

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
May 1, 2025
0 replies
k i Adding contests to the Contest Collections
dcouchman   1
N Apr 5, 2023 by v_Enhance
Want to help AoPS remain a valuable Olympiad resource? Help us add contests to AoPS's Contest Collections.

Find instructions and a list of contests to add here: https://artofproblemsolving.com/community/c40244h1064480_contests_to_add
1 reply
dcouchman
Sep 9, 2019
v_Enhance
Apr 5, 2023
k i Zero tolerance
ZetaX   49
N May 4, 2019 by NoDealsHere
Source: Use your common sense! (enough is enough)
Some users don't want to learn, some other simply ignore advises.
But please follow the following guideline:


To make it short: ALWAYS USE YOUR COMMON SENSE IF POSTING!
If you don't have common sense, don't post.


More specifically:

For new threads:


a) Good, meaningful title:
The title has to say what the problem is about in best way possible.
If that title occured already, it's definitely bad. And contest names aren't good either.
That's in fact a requirement for being able to search old problems.

Examples:
Bad titles:
- "Hard"/"Medium"/"Easy" (if you find it so cool how hard/easy it is, tell it in the post and use a title that tells us the problem)
- "Number Theory" (hey guy, guess why this forum's named that way¿ and is it the only such problem on earth¿)
- "Fibonacci" (there are millions of Fibonacci problems out there, all posted and named the same...)
- "Chinese TST 2003" (does this say anything about the problem¿)
Good titles:
- "On divisors of a³+2b³+4c³-6abc"
- "Number of solutions to x²+y²=6z²"
- "Fibonacci numbers are never squares"


b) Use search function:
Before posting a "new" problem spend at least two, better five, minutes to look if this problem was posted before. If it was, don't repost it. If you have anything important to say on topic, post it in one of the older threads.
If the thread is locked cause of this, use search function.

Update (by Amir Hossein). The best way to search for two keywords in AoPS is to input
[code]+"first keyword" +"second keyword"[/code]
so that any post containing both strings "first word" and "second form".


c) Good problem statement:
Some recent really bad post was:
[quote]$lim_{n\to 1}^{+\infty}\frac{1}{n}-lnn$[/quote]
It contains no question and no answer.
If you do this, too, you are on the best way to get your thread deleted. Write everything clearly, define where your variables come from (and define the "natural" numbers if used). Additionally read your post at least twice before submitting. After you sent it, read it again and use the Edit-Button if necessary to correct errors.


For answers to already existing threads:


d) Of any interest and with content:
Don't post things that are more trivial than completely obvious. For example, if the question is to solve $x^{3}+y^{3}=z^{3}$, do not answer with "$x=y=z=0$ is a solution" only. Either you post any kind of proof or at least something unexpected (like "$x=1337, y=481, z=42$ is the smallest solution). Someone that does not see that $x=y=z=0$ is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
Similar, posting "I have solved this problem" but not posting anything else is not welcome; it even looks that you just want to show off what a genius you are.

e) Well written and checked answers:
Like c) for new threads, check your solutions at least twice for mistakes. And after sending, read it again and use the Edit-Button if necessary to correct errors.



To repeat it: ALWAYS USE YOUR COMMON SENSE IF POSTING!


Everything definitely out of range of common sense will be locked or deleted (exept for new users having less than about 42 posts, they are newbies and need/get some time to learn).

The above rules will be applied from next monday (5. march of 2007).
Feel free to discuss on this here.
49 replies
ZetaX
Feb 27, 2007
NoDealsHere
May 4, 2019
Disjoint Pairs
MithsApprentice   42
N a minute ago by endless_abyss
Source: USAMO 1998
Suppose that the set $\{1,2,\cdots, 1998\}$ has been partitioned into disjoint pairs $\{a_i,b_i\}$ ($1\leq i\leq 999$) so that for all $i$, $|a_i-b_i|$ equals $1$ or $6$. Prove that the sum \[ |a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}|  \] ends in the digit $9$.
42 replies
MithsApprentice
Oct 9, 2005
endless_abyss
a minute ago
FE with gcd
a_507_bc   8
N 3 minutes ago by Tkn
Source: Nordic MC 2023 P2
Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that $$\gcd(f(x),y)f(xy)=f(x)f(y)$$for all positive integers $x, y$.
8 replies
a_507_bc
Apr 21, 2023
Tkn
3 minutes ago
2014 JBMO Shortlist G1
parmenides51   19
N 13 minutes ago by tilya_TASh
Source: 2014 JBMO Shortlist G1
Let ${ABC}$ be a triangle with $m\left( \angle B \right)=m\left( \angle C \right)={{40}^{{}^\circ }}$ Line bisector of ${\angle{B}}$ intersects ${AC}$ at point ${D}$. Prove that $BD+DA=BC$.
19 replies
parmenides51
Oct 8, 2017
tilya_TASh
13 minutes ago
Stars and bars i think
RenheMiResembleRice   1
N 36 minutes ago by NicoN9
Source: Diao Luo
Solve the following attached with steps
1 reply
RenheMiResembleRice
44 minutes ago
NicoN9
36 minutes ago
Sequence
Titibuuu   1
N 40 minutes ago by Titibuuu
Let \( a_1 = a \), and for all \( n \geq 1 \), define the sequence \( \{a_n\} \) by the recurrence
\[
a_{n+1} = a_n^2 + 1
\]Prove that there is no natural number \( n \) such that
\[
\prod_{k=1}^{n} \left( a_k^2 + a_k + 1 \right)
\]is a perfect square.
1 reply
Titibuuu
6 hours ago
Titibuuu
40 minutes ago
Show that three lines concur
benjaminchew13   2
N an hour ago by benjaminchew13
Source: Revenge JOM 2025 P2
t $A B C$ be a triangle. $M$ is the midpoint of segment $B C$, and points $E$, $F$ are selected on sides $A B$, $A C$ respectively such that $E$, $F$, $M$ are collinear. The circumcircles $(A B C)$ and $(A E F)$ intersect at a point $P != A$. The circumcircle $(A P M)$ intersects line $B C$ again at a point $D != M$. Show that the lines $A D$, $E F$ and the tangent to $(A E F)$ at point $P$ concur.
2 replies
benjaminchew13
an hour ago
benjaminchew13
an hour ago
slightly easy NT fe
benjaminchew13   2
N an hour ago by benjaminchew13
Source: Revenge JOM 2025 P1
Find all functions $f:\mathbb{N}\rightarrow\mathbb{N}$ such that $$f(a) + f(b) + f(c) | a^2 + af(b) + cf(a)$$for all $a, b, c\in\mathbb{N}$
2 replies
benjaminchew13
an hour ago
benjaminchew13
an hour ago
Cheesy's math casino
benjaminchew13   1
N an hour ago by benjaminchew13
Source: Revenge JOM 2025 P4
There are $p$ people playing a game at Cheesy's math casino, where $p$ is an odd prime number. Let $n$ be a positive integer. A subset of length $s$ from the set of integers from $1$ to $n$ inclusive is randomly chosen, with an equal probability ($s <= n$ and is fixed). The winner of Cheesy's game is person $i$, if the sum of the chosen numbers are congruent to $i mod p$ for $0 <= i <= p - 1$.

For each $n$, find all values of $s$ such that no one will sue Cheesy for creating unfair games (i.e. all the winning outcomes are equally likely).
1 reply
benjaminchew13
an hour ago
benjaminchew13
an hour ago
2013 Japan MO Finals
parkjungmin   0
an hour ago
help me

we cad do it
0 replies
parkjungmin
an hour ago
0 replies
inequality
benjaminchew13   1
N an hour ago by benjaminchew13
Source: Revenge JOM 2025 P3
Let $n \ge 2$ be a positive integer and let $a_1$, $a_2$, ..., $a_n$ be a sequence of non-negative real numbers. Find the maximum value of $$3(a_1  + a_2 + \cdots + a_n) - (a_1^2 + a_2^2 + \cdots + a_n^2) - (a_1a_2\cdots a_n)$$in terms of $n$.
1 reply
benjaminchew13
an hour ago
benjaminchew13
an hour ago
IMO ShortList 1999, algebra problem 2
orl   11
N an hour ago by ezpotd
Source: IMO ShortList 1999, algebra problem 2
The numbers from 1 to $n^2$ are randomly arranged in the cells of a $n \times n$ square ($n \geq 2$). For any pair of numbers situated on the same row or on the same column the ratio of the greater number to the smaller number is calculated. Let us call the characteristic of the arrangement the smallest of these $n^2\left(n-1\right)$ fractions. What is the highest possible value of the characteristic ?
11 replies
orl
Nov 14, 2004
ezpotd
an hour ago
Coolabra
Titibuuu   2
N an hour ago by no_room_for_error
Let \( a, b, c \) be distinct real numbers such that
\[
a + b + c + \frac{1}{abc} = \frac{19}{2}
\]Find the maximum possible value of \( a \).
2 replies
Titibuuu
6 hours ago
no_room_for_error
an hour ago
Hard centroid geo
lucas3617   0
an hour ago
Source: Revenge JOM 2025 P5
A triangle $A B C$ has centroid $G$. A line parallel to $B C$ passing through $G$ intersects the circumcircle of $A B C$ at $D$. Let lines $A D$ and $B C$ intersect at $E$. Suppose a point $P$ is chosen on $B C$ such that the tangent of the circumcircle of $D E P$ at $D$, the tangent of the circumcircle of $A B C$ at $A$ and $B C$ concur. Prove that $G P = P D$.
0 replies
lucas3617
an hour ago
0 replies
Cute construction problem
Eeightqx   5
N an hour ago by HHGB
Source: 2024 GPO P1
Given a triangle's intouch triangle, incenter, incircle. Try to figure out the circumcenter of the triangle with a ruler only.
5 replies
Eeightqx
Feb 14, 2024
HHGB
an hour ago
Operations on Pebbles
MarkBcc168   24
N Apr 26, 2025 by EeEeRUT
Source: ISL 2022 C6
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.
24 replies
MarkBcc168
Jul 9, 2023
EeEeRUT
Apr 26, 2025
Operations on Pebbles
G H J
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.
MarkBcc168
1595 posts
#1
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.
MarkBcc168
1595 posts
#2 • 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.
IAmTheHazard
5001 posts
#3 • 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.
TheUltimate123
1740 posts
#4 • 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.
MarkBcc168
1595 posts
#5 • 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:).

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.
IAmTheHazard
5001 posts
#6 • 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:).

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.
yofro
3151 posts
#8 • 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.
megarnie
5606 posts
#9 • 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.
GrantStar
821 posts
#10 • 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.
JAnatolGT_00
559 posts
#11
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.
1717 posts
#12
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
44 posts
#13
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
44 posts
#14
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.
Inconsistent
1455 posts
#15 • 1 Y
Y by TheHimMan
This problem is peak combo comedy :D 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.
cj13609517288
1915 posts
#16
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.
asdf334
7585 posts
#17 • 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.
Toll
23 posts
#18
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.
awesomehuman
499 posts
#19
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.
neon_paradox
27 posts
#20
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.
sami1618
907 posts
#21
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.
ihatemath123
3446 posts
#22
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.
MathLuis
1524 posts
#23
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:.
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.
Blast_S1
358 posts
#24
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.
quantam13
113 posts
#25
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.
EeEeRUT
70 posts
#26
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
=
a