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
IMO Shortlist 2012, Geometry 8
lyukhson   33
N 7 minutes ago by awesomeming327.
Source: IMO Shortlist 2012, Geometry 8
Let $ABC$ be a triangle with circumcircle $\omega$ and $\ell$ a line without common points with $\omega$. Denote by $P$ the foot of the perpendicular from the center of $\omega$ to $\ell$. The side-lines $BC,CA,AB$ intersect $\ell$ at the points $X,Y,Z$ different from $P$. Prove that the circumcircles of the triangles $AXP$, $BYP$ and $CZP$ have a common point different from $P$ or are mutually tangent at $P$.

Proposed by Cosmin Pohoata, Romania
33 replies
lyukhson
Jul 29, 2013
awesomeming327.
7 minutes ago
Consecutive squares are floors
ICE_CNME_4   11
N 34 minutes ago by ICE_CNME_4

Determine how many positive integers \( n \) have the property that both
\[
\left\lfloor \sqrt{2n - 1} \right\rfloor \quad \text{and} \quad \left\lfloor \sqrt{3n + 2} \right\rfloor
\]are consecutive perfect squares.
11 replies
ICE_CNME_4
Yesterday at 1:50 PM
ICE_CNME_4
34 minutes ago
Finding all possible $n$ on a strange division condition!!
MathLuis   10
N an hour ago by justaguy_69
Source: Bolivian Cono Sur Pre-TST 2021 P1
Find the sum of all positive integers $n$ such that
$$\frac{n+11}{\sqrt{n-1}}$$is an integer.
10 replies
MathLuis
Nov 12, 2021
justaguy_69
an hour ago
IMO 2012 P5
mathmdmb   123
N an hour ago by SimplisticFormulas
Source: IMO 2012 P5
Let $ABC$ be a triangle with $\angle BCA=90^{\circ}$, and let $D$ be the foot of the altitude from $C$. Let $X$ be a point in the interior of the segment $CD$. Let $K$ be the point on the segment $AX$ such that $BK=BC$. Similarly, let $L$ be the point on the segment $BX$ such that $AL=AC$. Let $M$ be the point of intersection of $AL$ and $BK$.

Show that $MK=ML$.

Proposed by Josef Tkadlec, Czech Republic
123 replies
1 viewing
mathmdmb
Jul 11, 2012
SimplisticFormulas
an hour ago
Fixed line
TheUltimate123   14
N an hour ago by amirhsz
Source: ELMO Shortlist 2023 G4
Let \(D\) be a point on segment \(PQ\). Let \(\omega\) be a fixed circle passing through \(D\), and let \(A\) be a variable point on \(\omega\). Let \(X\) be the intersection of the tangent to the circumcircle of \(\triangle ADP\) at \(P\) and the tangent to the circumcircle of \(\triangle ADQ\) at \(Q\). Show that as \(A\) varies, \(X\) lies on a fixed line.

Proposed by Elliott Liu and Anthony Wang
14 replies
TheUltimate123
Jun 29, 2023
amirhsz
an hour ago
Computing functions
BBNoDollar   7
N an hour ago by ICE_CNME_4
Let $f : [0, \infty) \to [0, \infty)$, $f(x) = \dfrac{ax + b}{cx + d}$, with $a, d \in (0, \infty)$, $b, c \in [0, \infty)$. Prove that there exists $n \in \mathbb{N}^*$ such that for every $x \geq 0$
\[
f_n(x) = \frac{x}{1 + nx}, \quad \text{if and only if } f(x) = \frac{x}{1 + x}, \quad \forall x \geq 0.
\](For $n \in \mathbb{N}^*$ and $x \geq 0$, the notation $f_n(x)$ represents $\underbrace{(f \circ f \circ \dots \circ f)}_{n \text{ times}}(x)$. )
7 replies
BBNoDollar
May 18, 2025
ICE_CNME_4
an hour ago
RMO 2024 Q2
SomeonecoolLovesMaths   14
N an hour ago by Adywastaken
Source: RMO 2024 Q2
For a positive integer $n$, let $R(n)$ be the sum of the remainders when $n$ is divided by $1,2, \cdots , n$. For example, $R(4) = 0 + 0 + 1 + 0 = 1,$ $R(7) = 0 + 1 + 1 + 3 + 2 + 1 + 0 = 8$. Find all positive integers such that $R(n) = n-1$.
14 replies
SomeonecoolLovesMaths
Nov 3, 2024
Adywastaken
an hour ago
Decimal functions in binary
Pranav1056   3
N 2 hours ago by ihategeo_1969
Source: India TST 2023 Day 3 P1
Let $\mathbb{N}$ be the set of all positive integers. Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that $f(x) + y$ and $f(y) + x$ have the same number of $1$'s in their binary representations, for any $x,y \in \mathbb{N}$.
3 replies
Pranav1056
Jul 9, 2023
ihategeo_1969
2 hours ago
Beautiful numbers in base b
v_Enhance   21
N 2 hours ago by Martin2001
Source: USEMO 2023, problem 1
A positive integer $n$ is called beautiful if, for every integer $4 \le b \le 10000$, the base-$b$ representation of $n$ contains the consecutive digits $2$, $0$, $2$, $3$ (in this order, from left to right). Determine whether the set of all beautiful integers is finite.

Oleg Kryzhanovsky
21 replies
v_Enhance
Oct 21, 2023
Martin2001
2 hours ago
Polynomial method of moving points
MathHorse   6
N 2 hours ago by Potyka17
Two Hungarian math olympians achieved significant breakthroughs in the field of polynomial moving points. Their main results are summarised in the attached pdf. Check it out!
6 replies
MathHorse
Jun 30, 2023
Potyka17
2 hours ago
Intertwined numbers
miiirz30   2
N 2 hours ago by Gausikaci
Source: 2025 Euler Olympiad, Round 2
Let a pair of positive integers $(n, m)$ that are relatively prime be called intertwined if among any two divisors of $n$ greater than $1$, there exists a divisor of $m$ and among any two divisors of $m$ greater than $1$, there exists a divisor of $n$. For example, pair $(63, 64)$ is intertwined.

a) Find the largest integer $k$ for which there exists an intertwined pair $(n, m)$ such that the product $nm$ is equal to the product of the first $k$ prime numbers.
b) Prove that there does not exist an intertwined pair $(n, m)$ such that the product $nm$ is the product of $2025$ distinct prime numbers.
c) Prove that there exists an intertwined pair $(n, m)$ such that the number of divisors of $n$ is greater than $2025$.

Proposed by Stijn Cambie, Belgium
2 replies
miiirz30
Yesterday at 10:12 AM
Gausikaci
2 hours ago
Geometry
shactal   0
2 hours ago
Two intersecting circles $C_1$ and $C_2$ have a common tangent that meets $C_1$ in $P$ and $C_2$ in $Q$. The two circles intersect at $M$ and $N$ where $N$ is closer to $PQ$ than $M$ . Line $PN$ meets circle $C_2$ a second time in $R$. Prove that $MQ$ bisects angle $\widehat{PMR}$.
0 replies
shactal
2 hours ago
0 replies
Inspired by 2025 KMO
sqing   1
N 2 hours ago by sqing
Source: Own
Let $ a,b,c,d  $ be real numbers satisfying $ a+b+c+d=0 $ and $ a^2+b^2+c^2+d^2= 6 .$ Prove that $$ -\frac{3}{4} \leq abcd\leq\frac{9}{4}$$Let $ a,b,c,d  $ be real numbers satisfying $ a+b+c+d=6 $ and $ a^2+b^2+c^2+d^2= 18 .$ Prove that $$ -\frac{9(2\sqrt{3}+3)}{4} \leq abcd\leq\frac{9(2\sqrt{3}-3)}{4}$$
1 reply
sqing
3 hours ago
sqing
2 hours ago
RMO 2024 Q1
SomeonecoolLovesMaths   25
N 3 hours ago by Adywastaken
Source: RMO 2024 Q1
Let $n>1$ be a positive integer. Call a rearrangement $a_1,a_2, \cdots , a_n$ of $1,2, \cdots , n$ nice if for every $k = 2,3, \cdots , n$, we have that $a_1 + a_2 + \cdots + a_k$ is not divisible by $k$.
(a) If $n>1$ is odd, prove that there is no nice arrangement of $1,2, \cdots , n$.
(b) If $n$ is even, find a nice arrangement of $1,2, \cdots , n$.
25 replies
SomeonecoolLovesMaths
Nov 3, 2024
Adywastaken
3 hours ago
number theory and combinatoric sets of integers relations
trying_to_solve_br   40
N May 16, 2025 by MathLuis
Source: IMO 2021 P6
Let $m\ge 2$ be an integer, $A$ a finite set of integers (not necessarily positive) and $B_1,B_2,...,B_m$ subsets of $A$. Suppose that, for every $k=1,2,...,m$, the sum of the elements of $B_k$ is $m^k$. Prove that $A$ contains at least $\dfrac{m}{2}$ elements.
40 replies
trying_to_solve_br
Jul 20, 2021
MathLuis
May 16, 2025
number theory and combinatoric sets of integers relations
G H J
Source: IMO 2021 P6
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
trying_to_solve_br
191 posts
#1 • 8 Y
Y by centslordm, fattypiggy123, megarnie, jhu08, quirtt, PHSH, kiyoras_2001, PikaPika999
Let $m\ge 2$ be an integer, $A$ a finite set of integers (not necessarily positive) and $B_1,B_2,...,B_m$ subsets of $A$. Suppose that, for every $k=1,2,...,m$, the sum of the elements of $B_k$ is $m^k$. Prove that $A$ contains at least $\dfrac{m}{2}$ elements.
This post has been edited 1 time. Last edited by trying_to_solve_br, Jul 20, 2021, 8:49 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ABCDE
1963 posts
#2 • 10 Y
Y by centslordm, trumpeter, TheStrayCat, Mindstormer, USJL, p_square, jhu08, PRMOisTheHardestExam, awesomeming327., PikaPika999
Seems like Jumpy snuck onto the PSC and applied a move to Problem 1 :maybe:

See Theorem 1 here.

I went to a talk the author of the paper above gave about some of his work and thought this result was cute, so I put this problem on a mock IMO I made for the 2020 USA IMO team. I also sent this mock IMO to the 2021 team, so let's see how they do...
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
kvanta
113 posts
#3 • 4 Y
Y by centslordm, pavel kozlov, jhu08, PRMOisTheHardestExam
Seems like I posted on the wrong P6 thread, so I'm copying this over here.

First of all, here is the key idea for the solution of this problem: You need to have some experience with linear algebra (and have some intuition about it). More precisely: Suppose $|A|=k$. Let's view the $B_i$ as vectors $v_i$ in $\{ 0, 1 \} ^k$. If $k$ would be small, then we would be able to find a linear combination of $v_i$ with small integer coefficients. But then we would get a contradiction with the fact that there is a linear combination of numbers $m, m^2, ..., m^m$ with small integer coefficients.

Now, the solution: Lemma: Suppose that $v_1, ..., v_m$ are vectors in $\{ 0, 1 \}^k$ where $k<m/2$. Then there exist integer $a_1, ..., a_m$, not all zero, such that $a_1v_1 + ... + a_m v_m = 0$ and all $|a_i| < m$.

Proof of the lemma: For a vector $v$ denote $v_1, v_2, ..., v_k$ its coordinates. Then for each $(c_1, ..., c_m)$ consider the ugly sum $(c_1 v_{11} + ... c_m v_{m1}) + (c_1 v_{11} + ... c_m v_{m1})m^2 + ... + (c_1 v_{11} + ... c_m v_{m1}) m^{2k-2}$. It is not that ugly actually! Anyway, each such sum is at least $0$ and less or equal to $m(m-1)(1+m^2...+m^{2k-2}) = m(m-1) \cdot \frac{m^{2k}-1}{m^2-1} < m^m$ and we have $m^m$ different ways to pick $(c_1, ..., c_m)$. Then for some two of those ways, say $(c_1, ...., c_m)$ and $(c_1',...,c_m')$ the ugly-sum will be the same. Let $a_i = c_i - c_i'$. Then we will be done, cause if the ugly-sum is equal to zero then each of the things in parentheses must be zero (cause each thing in parentheses is between $-m^2$ and $m^2$ and we have a linear combination of powers of $m^2$ that is zero). Sorry for not writing down all the algebra, but I hope it is clear.

Now, let's use the lemma to solve the problem. Suppose $|A| =k$ and let $v_i$ be the vector in $\{ 0, 1 \}^k$ such that $v_{ij} = 1$ if the $j-th$ biggest element of $A$ is in $B_i$, and $v_{ij} = 0$ otherwise. Suppose that $k < m/2$. Apply the lemma above to $v_i$ and find the corresponding $a_i$. But then if we multiply elements of $B_1$ by $a_1$, elements of $B_2$ by $a_2$ ... and add the numbers we will get that $a_1 m + a_2 m^2 + ... a_m m^m = 0$ where $a_i$ are not all zero and $-m < a_i < m$. This is impossible. Contradiction. So done.
This post has been edited 2 times. Last edited by kvanta, Jul 20, 2021, 9:58 PM
Reason: small editing
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
zschess
92 posts
#4 • 22 Y
Y by kukuriku, khina, pavel kozlov, arvind_r, wateringanddrowned, gvole, microsoft_office_word, jhu08, WallyWalrus, Illuzion, hakN, rcorreaa, Master_of_Aops, Wizard0001, electrovector, Realgauss1, PRMOisTheHardestExam, SHZhang, Assassino9931, math_comb01, mathleticguyyy, kiyoras_2001
My solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
USJL
540 posts
#5 • 5 Y
Y by steppewolf, Hamel, jhu08, PRMOisTheHardestExam, snap7822
I happened to get the main idea at the very first moment because I've seen something related to the lemma. I will first write up my solution and then lay out the detailed motivation behind it.

Also this is the only problem I enjoy in Day 2... :(
plus is this problem misclassified again? Feel like this is classified to N but it should've been C.

Solution

Motivation
This post has been edited 1 time. Last edited by USJL, Jul 22, 2021, 3:58 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
hyx
192 posts
#6 • 2 Y
Y by jhu08, PRMOisTheHardestExam
This technic is really common in China,so I think it is not difficult for Chinese team to solve it.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Hachiri_Tomoko
22 posts
#7 • 2 Y
Y by jhu08, PRMOisTheHardestExam
Looks a bit easy for IMO 6. I guess the $m/2$ can be improved to $m/2+cm/\log m$. It would be interesting to see whether this can be improved further...
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
kukuriku
6 posts
#8 • 1 Y
Y by jhu08
Is there a solution that is not based on linear algebra?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Loppukilpailija
155 posts
#10 • 3 Y
Y by pavel kozlov, jhu08, PRMOisTheHardestExam
kvanta wrote:
Lemma: Suppose that $v_1, ..., v_m$ are vectors in $\{ 0, 1 \}^k$ where $k<m/2$. Then there exist integer $a_1, ..., a_m$, not all zero, such that $a_1v_1 + ... + a_m v_m = 0$ and all $|a_i| < m$.

This is how I solved it as well. The result follows directly by applying Siegel's lemma, a somewhat well-known techinque in transcendetal number theory (but the proof is just an application of the pigeonhole principle). In the Nordic 2019 IMO camp there was a lecture where Siegel's lemma was discussed.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ABCDE
1963 posts
#11 • 16 Y
Y by test20, Hachiri_Tomoko, holahello, USJL, tree_3, pipitchaya.s4869, turmax2005, trumpeter, Aliaksei, jhu08, megarnie, centslordm, PRMOisTheHardestExam, mathleticguyyy, khina, sabkx
We in fact have $|A|\ge\left(\frac23-o(1)\right)m$. Assume that $m$ is sufficiently large. As in the solutions above, let $|A|=n$ and consider the indicator vectors $v_1,\ldots,v_n\in\{0,1\}^m$. Previously, we argued that all nonnegative multiples of $m$ less than $m^{m+1}$ can be expressed as $v=c_1v_1+\cdots+c_nv_n$ for nonnegative integers $c_1,\ldots,c_n$ less than $m$, where each coordinate of $v$ is a nonnegative integer less than $m^2$. The key idea in this better bound is that most nonnegative multiples of $m$ less than $m^{m+1}$ can be expressed as $v=c_1v_1+\cdots+c_nv_n$ for nonnegative integers $c_1,\ldots,c_n$ less than $m$, where each coordinate of $v$ lies in some interval of length $O(m^{3/2})$ by applying concentration inequalities.

Let $C_1,\ldots,C_n$ be i.i.d. random variables distributed as $C$, a uniform random element of $\{0,1,\ldots,m-1\}$. Note that the $i$th coordinate of $V=C_1v_1+\cdots+C_nv_n$ is the sum of $k$ i.i.d. copies of $C$, where $k\le m$ is the number of sets among $B_1,\ldots,B_m$ that $i$ lies in. Since the range of $C$ is bounded by $m$, we have by the Azuma-Hoeffding inequality that the probability that the $i$th coordinate of $V$ deviates from its expectation by more than $m^{3/2}\log m\ge\lambda=2\sqrt{km^2\log m}$ is at most $2\exp\left(-\frac{\lambda^2}{2km^2}\right)=\frac2{m^2}$. Union bounding over all coordinates, the probability that any coordinate of $V$ deviates from its expectation by more than $m^{3/2}\log m$ is at most $\frac2m$.

It follows that at least $m^m-2m^{m-1}$ nonnegative multiples of $m$ less than $m^{m+1}$ can be expressed as $v=c_1v_1+\cdots+c_nv_n$ for nonnegative integers $c_1,\ldots,c_n$ less than $m$, where each coordinate of $v$ is an integer constrained to be in some interval of length $2m^{3/2}\log m$ centered at the expectation of the corresponding coordinate of $V$. Thus, we have that $(2m^{3/2}\log m+1)^n\ge m^m-2m^{m-1}$, from which it easily follows that $n\ge\left(\frac23-o(1)\right)m$, as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Hachiri_Tomoko
22 posts
#12 • 1 Y
Y by jhu08
Awesome! Probabilistic methods always come in handy.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
VicKmath7
1390 posts
#13 • 1 Y
Y by jhu08
Is the solution in #4 correct? Because it's the simplest one here I think.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
square_root_of_3
78 posts
#14 • 1 Y
Y by jhu08
Let $k$ denote the number of elements of $A$. Suppose $2k<m$.

Lemma. If $2k<m$ and $v_1, v_2, \ldots, v_m$ are vectors in $\{0,1\}^k$, then there exist integers $a_1, \ldots, a_m$ not all equal to zero such that $|a_i|\leq 2k$ and $$\sum_{i=1}^m a_iv_i=0.$$Proof
Now, let $x_1, \ldots, x_k$ be the elements of $A$, and let $v_j$ be the vector adjoined to the subset $B_j$ for each $j\leq m$. Finally, let $(a_1, \ldots, a_m)$ be the integer $m$-tuple satisfying the lemma applied to $v_1,\ldots, v_k$. Note that the dot product of $(x_1, \ldots, x_k)$ and $v_j$ equals $m^j$. Then the dot product of $(x_1,\ldots, x_k)$ and $0=\sum a_j v_j$ equals $\sum a_jm^j$ which cannot be zero due to the bounds on $|a_j|$ (take the largest $j$ such that $a_j$ is nonzero, and then the remaining nonzero $a_i$ are too small to reach zero). Hence, we've reached a contradiction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pavel kozlov
617 posts
#15 • 2 Y
Y by Loppukilpailija, jhu08
Loppukilpailija wrote:
kvanta wrote:
Lemma: Suppose that $v_1, ..., v_m$ are vectors in $\{ 0, 1 \}^k$ where $k<m/2$. Then there exist integer $a_1, ..., a_m$, not all zero, such that $a_1v_1 + ... + a_m v_m = 0$ and all $|a_i| < m$.

This is how I solved it as well. The result follows directly by applying Siegel's lemma, a somewhat well-known techinque in transcendetal number theory (but the proof is just an application of the pigeonhole principle). In the Nordic 2019 IMO camp there was a lecture where Siegel's lemma was discussed.

Nice observation. Also by refinement of Siegel's lemma made by Bombieri and Vaaler in 1983 (theorem 1.3 here: https://arxiv.org/pdf/1707.05941.pdf) one can prove that $|a_i|\leq k^{k/(2(m-k)}$. That helps to prove that $k>2m/3$ unconditionally.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Justanaccount
196 posts
#16 • 1 Y
Y by jhu08
I wonder if this problem is classified as A or NT in the shortlist.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pavel kozlov
617 posts
#17 • 2 Y
Y by jhu08, test20
Justanaccount wrote:
I wonder if this problem is classified as A or NT in the shortlist.

What exactly makes you wonder?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Eyed
1065 posts
#18 • 5 Y
Y by smartmonkey999, jhu08, shivprateek, Elainedelia, signifance
Solved with Michael Gao and Kevin Wu

Let the elements of $A$ be $a_{1}, a_{2}, \ldots a_{n}$. Observe that for some number $0 \leq T \leq m^{m+1} - m$, where $m | T$, we can take integers $c_{1}, c_{2}, \ldots c_{m}$ such that $0 \leq c_{i} < m$, and
\[T = c_{1}m + c_{2}m^{2} + \ldots + c_{m}m^{m}\]This is true by dividing both sides by $m$, then expressing $T$ in base $m$.

Now, we can express $T$ as the sum of elements in $A$, where duplicates are allowed. Observe that for each element $a_{i}\in A$, $a_{i}$ will be included at most $m(m-1)$ times (for each $c_{j}$, $a_{i}$ will be included at most $c_{j}$ times, and $c_{j} \leq m-1$ for $m$ values of $j$0. Now, observe that there are $m(m-1) + 1$ ways to choose the total number of duplicates of element $a_{i}$, so the total number of distinct sums is at least
\[(m(m-1) + 1)^{|A|}\]However, there are $m^{m}$ values of $T$, so we get
\[(m^{2})^{|A|} \geq (m(m-1) + 1)^{|A|} \geq m^{m} \Rightarrow m^{2|A|} \geq m^{m} \Rightarrow |A|\geq \frac{m}{2}\]
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JingheZhang
179 posts
#19 • 1 Y
Y by jhu08
hyx wrote:
This technic is really common in China,so I think it is not difficult for Chinese team to solve it.

Someone told me that all six Chinese team member solved question 1,4,5,6.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AwesomeYRY
579 posts
#20 • 1 Y
Y by jhu08
Solved with Elliott Liu. Also got 3 very cryptic hints from Jeffrey Chen (stuff like "linear algebra" and "base m")

We double count the number of ways to express numbers as repeat-sums of $B_k$ and repeat-sums of $a_k$

Note that we can express all multiples of $m$ in the range $[0,m^{m+1}-m]$ as pseudosums of $B_k$. Basically if,
\[S_{B}(m-1) = \{\sum_{k=1}^{m} e_k B_k:  \forall k, e_k\in [0,m-1]\}\]Then, we have $S_{B}(m-1)$ exactly covers all multiples of $m$ in $[0,m^{m+1}-m]$, of which there are $m^m$.

However, this set of pseudosums can all be written as sums of elements of $A$ with repeats of at most $m^2-m$.
\[S_A(m^2-m) = \{\sum_{k=1}^{|A|}d_k a_k: \forall k, d_k\in [0,m^2-m]\}\]
This gives us
\[(m^2-m+1)^{|A|} \geq S_{A}(m^2) \geq S_{B}(m-1) =m^m\]Thus, $|A|\geq \frac{m}{2}$ and 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.
Aliaksei
3 posts
#21 • 1 Y
Y by jhu08
pavel kozlov wrote:
Nice observation. Also by refinement of Siegel's lemma made by Bombieri and Vaaler in 1983 (theorem 1.3 here: arxiv/pdf/1707.05941.pdf) one can prove that |a_i| > k^{k/(2(m-k)}. That helps to prove that k>2m/3 unconditionally.

Could you please elaborate on how to apply Siegel's lemma to solve this problem? I currently cannot see, how to use it, since the RHS to our system of equations is the vector (m, m^2, ..., m^m), not (0, 0, ..., 0), as required by Siegel's lemma.
I tried to add a "fictive" variable a_{k+1} = 1 to a_1, ..., a_k, so that we have equalities ...a_1 + ... + ...a_k - m^i a_{k+1} = 0 for each i, but the determinant of MM^{T} does not seem to be well-bounded, where M is a matrix of ones and zeros with the last column equal to (m, m^2, ...).

(no latex, because it is my first post here, and the website does not allow to insert "images" and links).
This post has been edited 1 time. Last edited by Aliaksei, Jul 26, 2021, 12:57 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pavel kozlov
617 posts
#22 • 1 Y
Y by jhu08
Aliaksei wrote:

Could you please elaborate on how to apply Siegel's lemma to solve this problem?

Please read solution of kvanta in post #3
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Aliaksei
3 posts
#23 • 1 Y
Y by jhu08
pavel kozlov wrote:
Aliaksei wrote:

Could you please elaborate on how to apply Siegel's lemma to solve this problem?

Please read solution of kvanta in post #3

Somehow overlooked it. Thank you!

However, I fail to repeat the way you obtain the bound k > 2m/3.

As far as I understand, the refinement of Siegel's lemma suggests us to consider a matrix M of dimension k х m, consisting of 0's and 1's. We want to find a = (a_1, a_2, ..., a_m) such that Ma = (0, ..., 0). Then we consider a matrix M M^{T}, which has dimension k x k, and where each entry is bounded by m.

I only see how to estimate det (MM^T) by (m\sqrt{k})^k, which gives bound max |a_i| <= (m\sqrt{k})^{k/2(m-k)}, from where I can only deduce the inequality k > (4/7 - o(1))m, which is a weaker bound.

Could you please elaborate on how to obtain the bound k > 2m/3 with Siegel's?

(Still, no latex, since new users cannot post images)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
PRMOisTheHardestExam
409 posts
#25 • 2 Y
Y by pavel kozlov, jhu08
thinker123 wrote:
BTW, to be honest this was wayyy too easy for IMO P6. Does anyone else feel this way?
Ah yes, problems really feel easy after reading the solutions ;)
Click to reveal hidden text
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pavel kozlov
617 posts
#26 • 1 Y
Y by jhu08
Aliaksei wrote:

However, I fail to repeat the way you obtain the bound k > 2m/3.

just look at square matrix $M$ of size $k$ formed by vectors $v_i$. Here $det(M\cdot M^T)\leq k^{k/2}$ and so on...
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Aliaksei
3 posts
#27 • 1 Y
Y by jhu08
pavel kozlov wrote:
Aliaksei wrote:

However, I fail to repeat the way you obtain the bound k > 2m/3.

just look at square matrix M of size k formed by vectors v_i. Here det MM^T <= k^{k/2} and so on...

Siegel's lemma is not applicable to square matrices.

Based on your bound k^{k/2(m-k)}, it seems to me that you apply Siegel's lemma to the matrix M of dimension k х m. But I see no way to estimate det MM^T better than (mk^{1/2})^k for such M.
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
#28 • 2 Y
Y by jhu08, sabkx
If \(A=\{a_1,\ldots,a_n\}\) has \(n\) elements then we are given each \(m^k\) may be expressed in the form \[m^k=\varepsilon_{k1}a_1+\varepsilon_{k2}a_2+\cdots+\varepsilon_{kn}a_n\quad\text{where}\quad0\le\varepsilon_i\le1.\]
Consider the \(m^m\) nonnegative multiples of \(m\) less than \(m^{m+1}\). Each \(mj<m^{m+1}\) may be represented in base \(m\) as \[mj=d_m\cdot m^m+d_{m-1}\cdot m^{m-1}+\cdots+d_1\cdot m\quad\text{where}\quad0\le d_i\le m-1.\]
Now consider \[w_j:=\sum_{i=1}^md_i\varepsilon_{ij}\le m(m-1),\]defined so that \[mj=w_1a_1+w_2a_2+\cdots+w_na_n\quad\text{where}\quad0\le w_i\le m(m-1).\]
Expressions of the above form may describe at most \((m^2-m+1)^n\) distinct numbers, so we have the inequality \[m^m\le(m^2-m+1)^n<m^{2n}.\]from which it is clear \(n\ge m/2\).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
vlj
1 post
#29 • 1 Y
Y by jhu08
Solution (this should be quite short and simple):
For A consisting of p elements, where p is prime, consider the characteristic vectors of subsets as 0-1 vectors in the vector space F_p^p (each coordinate of the length-p vector is modulo p) and we can see that all p-ary linear combinations of the characteristic vectors of the subsets are different as they have different (weighted) sums. Therefore p^(number of subets) <= p^p and thus number of subsets is at most p. In other words, for m prime, A contains at least m elements. To complete the proof, take p as the largest prime that is at most m (there is one at least m/2, small cases can be covered separately), and note monotonicity since we might as well increase the number of subsets from p to m, and we might as well have coefficients for subsets in {0,1,...,m-1} instead of its subset {0,1,...,p-1}.

Or actually why not look at the module Z_m^m, coefficients modulo m, think of the set {0,1,...,m-1} and we have a similar proof that m^(number of subsets) <= m^m and thus number of subsets at most m. So size of A is at least m (looking at vectors of length |A| with entries modulo |A|). Am I missing something here? Is there a counterexample?
This post has been edited 4 times. Last edited by vlj, Aug 3, 2021, 3:23 PM
Reason: more specific
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dgrozev
2464 posts
#31 • 1 Y
Y by khina
A better estimate can be proven. The set $A$ contains at least $ \displaystyle \frac{2m}{3}$ elements. Or even slightly sharper: It contains at least $ \displaystyle \left(\frac{2}{3}+\frac{c}{\log m} \right)m$ elements, where $c>0$ is some absolute constant.

The problem boils down to prove the following pure linear algebra claim.
Claim. Let $ v_1,v_2,\dots,v_m$ be $ n$ dimensional binary vectors (their coordinates are only $0$'s and $1$'s ) and $ n<\frac{2}{3}m$. Then, for some $k, 2\le k\le m$ the vector $ v_k$ can be represented as
$$ \displaystyle v_k=\sum_{i=1}^{k-1} \alpha_i v_i\,;\, |\alpha_i|<m,i=1,2,\dots,k-1 \qquad(1)$$The proof of this claim and more detailed discussion can be found in my blog. Here, in order to sketch the main idea, I'll provide a proof for the particular case when the first $n$ vectors $v_1,v_2,\dots,v_n$ are linearly independent and thus are basis vectors in $\mathbb{R}^n$. We denote by $\det(v_1,v_2,\dots,v_n)$ the determinant which columns are the vectors $v_1,\dots,v_n$ in this order. Obviously $\left|\det(v_1,v_2,\dots,v_n)\right|\ge 1$ since it is a non-zero integer. We can write
$$v_{n+1}=\sum_{i=1}^n \alpha_i v_i, \alpha_i\in \mathbb{R} $$If $|\alpha_i|<m,i=1,\dots,n$ we are done, so suppose $|\alpha_k|\ge m$ for some $k,1\le k\le n.$ Cramer's rule yields
$$|\alpha_k|=\frac{\left|\det(v_1,v_2,\dots,v_{k-1},v_{n+1},v_{k+1},\dots,v_n) \right|}{\left|\det(v_1,v_2,\dots,v_n) \right| } \ge m$$hence
$${\left|\det(v_1,v_2,\dots,v_{k-1},v_{n+1},v_{k+1},\dots,v_n) \right|}\ge m.$$Note that the vectors
$$v_1,v_2,\dots,v_{k-1},v_{n+1},v_{k+1},\dots,v_n$$are also linearly independent, so $v_{n+2}$ can be written as some linear combination of them. If some of those coefficients has absolute value at least $m$ we again apply the same trick and get some permutation of those vectors with determinant in absolute value at least $m^2.$ So, proceeding in this way for $v_{n+1},v_{n+2},\dots,v_m$ either we get a representation as in $(1)$ or we find a permutation of binary vectors with determinant in absolute value at least $m^{(m-n)}$. The latter case is impossible if $n<2m/3.$ Indeed, the determinant of any $n\times n$ matrix that consists only of $0$'s and $1$'s can have an absolute value at most $n^{n/2}.$ (see here) It yields
$$n^{n/2}\ge m^{(m-n)}\ge n^{(m-n)}$$hence $n\ge 2m/3$ which contradicts the imposed constraint of our claim.
This post has been edited 1 time. Last edited by dgrozev, Sep 19, 2021, 6:02 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
TheKagas
141 posts
#32
Y by
Could someone explain to me why immediately they see this they think of it as a linear algebra problem? is it because of Siegel's motto? Maybe knowing him my question answers itself but I don't know him
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
squareman
966 posts
#33 • 4 Y
Y by centslordm, rama1728, Catsaway, ike.chen
Solved with rama1728.

Say $|A| = N$ and $A = \{a_1,a_2, \dots , a_n\}.$ Let $S$ be the set of (at most) $(m^2-m+1)^N$ integers that can be written as
$$c_1a_1 + c_2a_2 + \dots + c_{N}a_N$$Where $c_1,c_2, \dots c_N$ are integers between $0$ and $m^2-m$ inclusive.

We claim all nonnegative multiples of $m$ less than $m^{m+1}$ are in $S.$ Each such integer has sum of its digits in base $m$ at most $m(m-1),$ and its units digits is $0.$ So it equals the sum of the sums of the elements of at most $m(m-1)$ (not necessarily distinct) subsets taken from $\{B_1,B_2, \dots B_m\},$ each of which encompasses distinct elements in $S,$ so the desired linear combination exists.

There are $m^m$ of these multiples, so $(m^2-m+1)^N \ge m^{m} \implies N \ge \frac{m}{2}.$ $\square$
This post has been edited 5 times. Last edited by squareman, Jan 10, 2022, 12:41 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
megarnie
5610 posts
#34 • 2 Y
Y by Sross314, math31415926535
2000th post!

Let $|A|=n$, and treat the $B_i$ as vectors $v_i$ in $\{0,1\}^n$, where $v_{ij}=1$ if the $j$th element of set $A$ is in $B_i$ and $v_{ij}=0$ otherwise. Henceforth suppose FTSOC that $n<\frac{m}{2}$.

Claim: There exist integers $a_1, a_2\ldots, a_m$ so that $a_1v_1+a_2v_2+\ldots+a_mv_m=0$ and $|a_i|<m$ for any $i$.
Proof: We have a sequence $b_i$, where $1\le i\le m$, and all the elements (non necessarily distinct) are integers from $0$ to $m-1$, inclusive. Consider the sum\[(b_1 v_{11}+b_2 v_{21}+\ldots+b_m v_{m1})+(b_1 v_{12}+b_2 v_{22}+\ldots+b_m v_{m2})m^2+\ldots+(b_1 v_{1n}+b_2 v_{2n}+\ldots +b_m v_{mn})m^{2n-2}\]This sum is less than or equal to $m(m-1)\left(\frac{m^{2n}-1}{m^2-1}\right)=m\frac{m^{2n}-1}{m+1}< m^{2n}-1<m^m$.
This sum is also greater than or equal to $0$.

Since there are $m^m$ ways to make sequence $b_i$, for some such distinct sequences $b_i$ and $b'_i$, the sum will be equal for both of them. We can see that\[b_1v_{11}+b_2v_{21}+\ldots+b_mv_{m1}=b'_1v_{11}+b'_2v_{21}+\ldots+b'_mv_{m1},\]and so on (because they are less than or equal to $m(m-1)<m^2$).

So a valid sequence $a_i$ is just $b_i-b'_i$. In fact the minimum value is $0-(m-1)=-m+1$ and the maximum value is $m-1$. This implies $-m<a_i<m$. $\blacksquare$

Multiply each element in $B_i$ by $a_i$ and we get $a_1 m+a_2m^2+\ldots+a_m m^m=0$. This is a contradiction as it implies $m\mid a_1\implies |a_1|\ge m$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
XaXuser
6 posts
#35 • 1 Y
Y by Mango247
let A={a_{1},....,a_{n}} where n=|A|
denote by t(Z) the transposite of Z=(z_{1},...,z_{m})
X=(a_{1},....,a_{n}) and Y_{k} for 0<=k<=m such that X.t(Y_{k})=m^k
let M=(t(Y_{1}),....,t(Y_{m})) and Y=(m,.....,m^m)
then we have X.M=Y
S={Z=(z_{1},.....,z_{m})/ 0<=max{z_{i} / 1<=i<=m} <=m-1}
D={Σx_{i}.m^i / for all i in[|1,m|] 0<=x_{i}<=m-1}
C={M.Z / Z in S}
define φ(t(Z))=Y.t(Z)=X.M.t(Z) from S to D
then φ is injective ( uniqueness of the writing in base of m)
thus m^m<=|Im(φ)|<=|C|
but :
M.Z as a vector it has for every coordinate m(m-1)+1 choice ( z_{i} 's range in [|0,m-1|] and M contains 0 or 1 as a coordinate so the range of any coordinate of M.Z is
[|0,m(m-1)|] which is m(m-1)+1choice)
so m^m<=(m(m-1)+1)^n<=m^(2n)
therefore n>=m/2 qed
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
#36
Y by
Assume by opposite that $A=\left \{ a_1,a_2,...,a_n\right \}$ for $n<\frac m2$. Let $s_i=m^i$ denotes sum of elements of $B_i$. Note that all $m^m$ numbers of type $\sum_{k=1}^m  s_k \alpha_k$ (for $\alpha_i \in \left \{ 0,1,...,m-1\right \}$) are different, because there is unique representation of number in $m-\text{base}$ system. On the other hand, all this numbers can be represented as $\sum_{k=1}^n a_k\beta_k$ for $\beta_k\in \left \{ 0,1,...,m(m-1)\right \}$, so there are at most $(m^2-m+1)^n<m^{2n}<m^m$ distinct numbers between them, contradiction.
This post has been edited 2 times. Last edited by JAnatolGT_00, Sep 21, 2022, 4:21 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
YaoAOPS
1541 posts
#37
Y by
Let $n = |A|$. Represent $B_i$ as vectors in ${\mathbb Z}^n$.

Claim: If we have $m \ge 2c$ vectors $a_1, \dots, a_m$ in ${\mathbb Z}^c$, then some nontrivial linear combination of $a_i$ with coefficients of absolute magnitude less than $m$ sums to $0$.
Proof. Note that for each $i = 1, \dots, m - c$ it follows that $a_i, a_{m-c+1}, \dots a_m$ has a nontrivial solution in ${\mathbb F}_2^m$, which by scaling gives $m$ nontrivial solutions.
As such, we get at least $m^(m-c)$ nontrivial solutions in ${\mathbb F}_m^n$ over all vectors.
However, the multiset $\mathcal L = \{\sum e_ia_i \mid 0 \le e_i < m \}$ has at most $m^c$ elements that get mapped to $0$ through embedding in ${\mathbb F}_m^n$.
Since, $m^(m-c) \ge m^c$, it follows that either the zero vector is in $\mathcal L$, in which case we are done, or that two elements in $\mathcal L$ are equal, in which case subtracting them gives the desired result. $\blacksquare$
Now, for any $-m < e_i < m$, we have that $\sum e_ia_i$ has a sum of $\sum e_i m^i$, which is only $0$ if each $e_i$ is $0$.
By the lemma, this can only hold if $n \ge \frac{m}{2}$.
This post has been edited 2 times. Last edited by YaoAOPS, Nov 29, 2023, 2:57 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
#38 • 1 Y
Y by Aryan_Agarwal
Let $S=\{s_1,s_2,\dots,s_l\}$ have $l$ elements, and let the vector $S=[s_1,\dots,s_l]$. Let the vector $b_i=[a_{i,1},a_{i,2},\dots,a_{i,l}$ with $a_{i,j}=1$ if $_j$ is used in the sum for $b_i$ to be $m^i$ and $0$ if it is not used in that sum.
Now, consider $\sum_{i=1}^m a_i(S\cdot b_i)$ where $0\leq a_i\leq m-1$ for all $i$. Note that this simply is a base $m$ representation, and all $m^m$ multiples of $m$ between $0$ and $m^{m+1}-m$ can be expressed this way. However, looking at it from each $s_i$ individually, we get that each $s_i$ appears anywhere between $0$ and $m(m-1)$ times. Thus, this sum takes at most $(m(m-1)+1)^l$ distinct values. Then, combine this with above to get $m^{2l}>(m^2-m+1)^l\geq m^m$ which finishes.

Remark: Is this alg, combo, or nt lmao
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awesomeming327.
1730 posts
#39
Y by
Let $A$ be $\{a_1,a_2,\dots,a_n\}$. For each $1\le i\le m$, let $m^i=a_1\varepsilon_{i1}+a_2\varepsilon_{i2}+\dots+a_n\varepsilon_{in}$ where $\varepsilon_{ij}\in \{0,1\}$ for all $(i,j)\in \{1,2,\dots,m\}\times \{1,2,\dots,n\}$. We can represent all integers from $0\le k\le m^m-1$ as
\[k=\frac{1}{m}\left(b_1m+b_2m^2+\dots+b_mm^m\right)\]Where $0\le b_i\le m-1$. If we substitute in the representation of $m^i$ as a sum of elements in $A$ then we are left with
\[k=\frac{1}{m}\sum_{i=1}^{n}{a_i(b_1\varepsilon_{1i}+b_2\varepsilon_{2i}+\dots+b_m\varepsilon_{mi})}\]Note that $k$ takes $m^m$ different values, so there must be $m^m$ different values representable by the right hand side through different choices of the coefficient $b_1\varepsilon_{1i}+b_2\varepsilon_{2i}+\dots+b_m\varepsilon_{mi}$. Note that this coefficient is between $0$ and $m(m-1)$ therefore there are at most $m^2-m+1<m^2$ ways to represent each coefficient. There are $n$ coefficients, so the number of different numbers the RHS can produce is less than $m^{2n}$ so $n>\tfrac{m}{2}$ as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Pyramix
419 posts
#40
Y by
Let $|A|=n$ and the elements be $A=\{a_1, a_2, \ldots, a_n\}$.

Claim: Every non-negative integer multiple $mt$ of $m$ less than $m^{m+1}$ can be written as:
\[mt=t_1a_1+t_2a_2+\cdots+t_na_n\]where $0\leq t_j\leq m^2-m$ for each $1\leq j\leq n$.
Proof. (Constructive) Note that since $mt\leq m^{m+1}$, we have $mt=(b_mb_{m-1}\ldots b_10)_m$ in base $m$ where each $0\leq b_i\leq m-1$ for $1\leq i\leq m$.
So, we may write
\[mt = b_mm^m + b_{m-1}m^{m-1}+\cdots+b_1m+0 \]\[= b_m(\text{sum of elements of }B_m)+b_{m-1}(\text{sum of elements of }B_{m-1})+\cdots+b_1(\text{sum of elements of }B_1)\]Expanding out, we get that we can write $mt=t_1a_1+t_2a_2+\cdots+t_na_n$. The fact that $t_j\leq m^2-m$ follows from the fact that any element of $A$ can appear in at most $m$ sets from $B_1, B_2, \ldots, B_m$, and the coefficients $b_1, b_2, \ldots, b_m$ are at most $m-1$, which means the final coefficient of that element is at most $m(m-1)$. The claim is therefore true. $\blacksquare$

Note that $(t_1, t_2, \ldots, t_n)\in\{0,1,\ldots,m^2-m\}^n$, which means there are at most $(m^2-m+1)^n$ distinct sums possible which can be written as
\[\text{sum}=t_1a_1+t_2a_2+\cdots+t_na_n\]However, we have given a construction that there are at least $m^m$ distinct sums possible as there are $m^m$ non-negative integer multiples of $m$ less than $m^{m+1}$.
This means $(m^2-m+1)^n \geq m^m$ and hence $n\geq \frac m2$. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
thdnder
198 posts
#41
Y by
Let $A = \{a_1 < a_2 < \dots a_k\}$. Our problem condition implies that for all $1 \le i \le m$, there exist $\varepsilon_{(i, 1)}, \varepsilon_{(i, 2)}, \dots, \varepsilon_{(i, k)} \in \{0, 1\}$ such that $a_1\varepsilon_{(i, 1)} + a_2\varepsilon_{(i, 2)} + \dots + a_k\varepsilon_{(i, k)} = m^i$. Take any nonnegative integer $M$ between $0, m^{m+1} - 1$ that is divisible by $m$. We can write $M = b_sm^s + b_{s-1}m^{s-1} + \dots + b_1m^1$ for some positive integer $s$ and some nonnegative integers $b_1, b_2, \dots, b_s \le m-1$. Thus, we get $M = \sum_{i=1}^{k} a_i(b_s\varepsilon_{(s, i)} + b_{s-1}\varepsilon_{(s-1, i)} + \dots + b_1\varepsilon_{(1, i)})$ and note that $b_s\varepsilon_{(s, i)} + b_{s-1}\varepsilon_{(s-1, i)} + \dots + b_1\varepsilon_{(1, i)} \le (m-1)s \le (m-1)m$, so we can write any nonnegative integer $M$ that is divisible by $m$ into a form $a_1x_1 + a_2x_2 + \dots + a_kx_k$ where $x_i$ are nonnegative integers that are not exceed $m(m-1)$. There are exactly $m^m$ nonnegative integers that are divisible by $m$ between $0$ and $m^{m+1}-1$, and $x_i$ can take at most $m(m-1) + 1$ values, we derive $m^m \le (m(m-1) + 1)^k < m^{2k}$, thus $\frac{m}{2} \le k$, as wanted. $\blacksquare$
This post has been edited 1 time. Last edited by thdnder, Apr 24, 2024, 9:18 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pi271828
3371 posts
#43 • 1 Y
Y by peace09
Let $A = \{ a_1, a_2, \dots, a_k \}$ and define

\[
\epsilon_{i, j} =
\begin{cases*}
1 & $a_j \in B_i$ \\
0 & $a_j \not\in B_i$
\end{cases*}
\]We can therefore model \begin{align*} S_i = \sum_{x \in B_i} x = \epsilon_{i, 1} a_1 + \epsilon_{i, 2} a_2 + \cdots + \epsilon_{i, k} a_k = m^i \end{align*}By using base $m$, one can choose a unique tuple $\{ C_1, C_2, \dots, C_m \}$ and $0 \le C_i \le m-1$ such that $\sum S_iC_i$ can generate any number from $m$ to $m^{m+1} - 1$. We let \begin{align*} C'_j = \sum_{i} C_i\epsilon_{i, j} \end{align*}such that \begin{align*} C'_1a_1 + C'_2a_2 \cdots + C'_ka_k \end{align*}can generate any value between $m$ and $m^{m+1}-1$. Therefore the number of tuples of $(C'_1, C'_2, \dots, C'_k)$ must be at least $m^{m+1} - m$. There are $m^2-m$ possibilities for each value of $C'_i$ so we have $m^{2k} > (m^2 - m)^k \ge m^{m+1} - m \ge m^m$ so $k > \tfrac{m}{2}$ 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.
HamstPan38825
8868 posts
#44
Y by
what the heck is this

Set $|A| = k$, and let $\mathbf B_i = [b_{1i}, b_{2i}, \dots, b_{ki}]$ be a vector for each $i$ such that $b_{ji} =1$ if $B_i$ contains the element $j$ and $1$ otherwise. We define the norm $|\mathbf B_i| = b_{1i}a_1 + b_{2i} a_2 + \cdots + b_{ki} a_k$ where $a_1, \dots, a_k$ are the elements of $A$ in that order. Then, the condition implies that for each positive integer $1 \leq n < m^{m+1}$, there exist digits $d_1, d_2, \dots, d_m \in \{0, 1, \dots, m-1\}$ such that \[n = |d_1 \mathbf B_1 + d_2 \mathbf B_2 + \cdots + d_m \mathbf B_m| = |r_1 \mathbf e_1 + r_2 \mathbf e_2 + \cdots + r_k \mathbf e_k|\]for digits $r_1, r_2, \dots, r_k \in \{0, 1, \dots, m^2 - 1\}$, where $\mathbf e_1, \dots, \mathbf e_k$ are the standard basis vectors. We have the upper bound on the $r-i$ because the entries of $\mathbf B_i$ are at most $1$. These vectors may span a space of size at most $(m^2)^k$, hence $(m^2)^k \geq m^m$, i.e. $k \geq \frac m2$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MathLuis
1550 posts
#45
Y by
Let $|A|=\ell$, now recall that for an integer $m \mid N$ and $0 \le N \le m^{m+1}-m$ we have that $N=ma_1+m^2a_2+\cdots+m^ma_m$ for some $0 \le a_i \le m-1$ for all such indexes $i$, and this holds true because of base $m$ representation after multiplying by $m$, now if $A$ had elements not in any of the $B_i$'s then its free real state by solving it for the other case as it just adds more so suppose the union of all $B_i$'s make $A$, then consider the sum of (could be repeated) elements of $A$ from all of the $B_i$'s, the idea is that we can make any such $N$ from sums of sums of elements from each $B_i$ and now in these sums, an element $a \in A$ shows up at most $m(m-1)$ repeated times because each coefficient $c_i$ is bounded between $0$ and $m-1$ and we have $m$ subsets chosen, notice that counting on the probabilities of the coefficients gives at most $(m^2-m+1)^\ell$ distinct possible sums but we have seen we can cover $m^m$ multiples of $m$ among the possible sums which means that $m^{2\ell}>(m^2-m+1)^{\ell} \ge m^m$ giving $\ell>\frac{m}{2}$ as desired thus we are done :cool:.
Z K Y
N Quick Reply
G
H
=
a