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
Yesterday at 11:16 PM
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
Yesterday at 11:16 PM
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
Euler's function
luutrongphuc   1
N 11 minutes ago by luutrongphuc
Find all real numbers \(\alpha\) such that for every positive real \(c\), there exists an integer \(n>1\) satisfying
\[
\frac{\varphi(n!)}{n^\alpha\,(n-1)!} \;>\; c.
\]
1 reply
+1 w
luutrongphuc
an hour ago
luutrongphuc
11 minutes ago
Square problem
Jackson0423   1
N 26 minutes ago by maromex
Construct a square such that the distances from an interior point to the vertices (in clockwise order) are
1,2,3,4, respectively.
1 reply
Jackson0423
42 minutes ago
maromex
26 minutes ago
Sequence with infinite primes which we see again and again and again
Assassino9931   4
N 29 minutes ago by SimplisticFormulas
Source: Balkan MO Shortlist 2024 N6
Let $c$ be a positive integer. Prove that there are infinitely many primes, each of which divides at least one term of the sequence $a_1 = c$, $a_{n+1} = a_n^3 + c$.
4 replies
+1 w
Assassino9931
Apr 27, 2025
SimplisticFormulas
29 minutes ago
Fermat points of Pentagon
Jackson0423   1
N 44 minutes ago by Jackson0423
It is known that, in general, a pentagon has three Fermat points. But I'm curious—if there are exactly two Fermat points inside the pentagon, under what conditions does the distance sum reach a minimum? Can you help me?
1 reply
Jackson0423
an hour ago
Jackson0423
44 minutes ago
Inequality , Exponent problem
biit   5
N an hour ago by Jackson0423
If $\ P=(\frac {6375}{6374})^ {6374} $ , $\ Q=(\frac {6375}{6374})^ {6375} $ then prove that $P^{Q}$ >$ Q^{P}$
5 replies
biit
an hour ago
Jackson0423
an hour ago
Ant walks
monishrules   0
an hour ago
Source: Homemade
3 Ants in a plane are placed on the vertices of a equilateral triangle of side length s, each ant moves s unit in a random direction with uniform probability. find the expected change in the area of the equilateral triangle.

some interesting extensions which I expect to only be solve-able via integration.
a) a right angled triangle with legs of side length A, and step length A?
b) a general n-gon?
c) a non uniform probability distribution? given by f(theta)
d) expected increase in volume/surface area of a cube?
0 replies
monishrules
an hour ago
0 replies
Inequality for 4 variables
Nguyenhuyen_AG   0
an hour ago
Let $a, \, b, \, c, \, d$ are non-negative real numbers. Prove that
\[( {a}^{2}-bc ) \sqrt {a+b+c}+ ( {b}^{2}-cd) \sqrt {b+c+d}+ ( {c}^{2}-da ) \sqrt {c+d+a}+ ( {d}^{2}-ab ) \sqrt {d+a+b} \geqslant 0.\]
0 replies
Nguyenhuyen_AG
an hour ago
0 replies
Two equal angles
jayme   1
N an hour ago by jayme
Dear Mathlinkers,

1. ABCD a square
2. I the midpoint of AB
3. 1 the circle center at A passing through B
4. Q the point of intersection of 1 with the segment IC
5. X the foot of the perpendicular to BC from Q
6. Y the point of intersection of 1 with the segment AX
7. M the point of intersection of CY and AB.

Prove : <ACI = <IYM.

Sincerely
Jean-Louis
1 reply
jayme
Today at 6:52 AM
jayme
an hour ago
Symetric inequality
Nguyenhuyen_AG   0
an hour ago
Let $a, \, b, \, c$ are non-negative real numbers and $k \geqslant 0.$
(i) Prove that
\[\frac{a(a^2-bc)}{\sqrt{ka+b+c}} + \frac{b(b^2-ca)}{\sqrt{kb+c+a}} + \frac{c(c^2-ab)}{\sqrt{kc+a+b}} \geqslant 0.\](ii) Prove that
\[(a^2-bc)\sqrt{ka+b+c}+(b^2-ca)\sqrt{kb+c+a}+(c^2-ab)\sqrt{kc+a+b} \geqslant 0.\]
0 replies
Nguyenhuyen_AG
an hour ago
0 replies
Lord Evan the Reflector
whatshisbucket   23
N an hour ago by bjump
Source: ELMO 2018 #3, 2018 ELMO SL G3
Let $A$ be a point in the plane, and $\ell$ a line not passing through $A$. Evan does not have a straightedge, but instead has a special compass which has the ability to draw a circle through three distinct noncollinear points. (The center of the circle is not marked in this process.) Additionally, Evan can mark the intersections between two objects drawn, and can mark an arbitrary point on a given object or on the plane.

(i) Can Evan construct* the reflection of $A$ over $\ell$?

(ii) Can Evan construct the foot of the altitude from $A$ to $\ell$?

*To construct a point, Evan must have an algorithm which marks the point in finitely many steps.

Proposed by Zack Chroman
23 replies
whatshisbucket
Jun 28, 2018
bjump
an hour ago
4 variables with quadrilateral sides 2
mihaig   6
N an hour ago by mihaig
Source: Own
Let $a,b,c,d\geq0$ satisfying
$$\frac1{a+1}+\frac1{b+1}+\frac1{c+1}+\frac1{d+1}=2.$$Prove
$$\left(a+b+c+d-2\right)^2+8\geq3\left(abc+abd+acd+bcd\right).$$
6 replies
mihaig
Apr 29, 2025
mihaig
an hour ago
Hard inequality
ys33   6
N an hour ago by mihaig
Let $a, b, c, d>0$. Prove that
$\sqrt[3]{ab}+ \sqrt[3]{cd} < \sqrt[3]{(a+b+c)(b+c+d)}$.
6 replies
ys33
Today at 9:36 AM
mihaig
an hour ago
Nice one
imnotgoodatmathsorry   2
N an hour ago by imnotgoodatmathsorry
Source: Own
With $x,y,z >0$.Prove that: $\frac{xy}{4y+4z+x} + \frac{yz}{4z+4x+y} +\frac{zx}{4x+4y+z} \le \frac{x+y+z}{9}$
2 replies
imnotgoodatmathsorry
3 hours ago
imnotgoodatmathsorry
an hour ago
Permutation with Matrices
SomeonecoolLovesMaths   0
an hour ago
Consider all $n \times n$ matrix such that $\forall$ $k \leq n$, $( a_{1k}, a_{2k}, \cdots, a_{nk} )$ is a permutation of $(1,2, \cdots, n)$, call such matrices $\textit{rowgood}$. Consider all $n \times n$ matrix such that $\forall$ $k \leq n$, $( a_{k1}, a_{k2}, \cdots, a_{kn} )$ is a permutation of $(1,2, \cdots, n)$, call such matrices $\textit{columngood}$. How many $n \times n$ matrices exist that are both $\textit{rowgood}$ and $\textit{columngood}$?
0 replies
SomeonecoolLovesMaths
an hour ago
0 replies
IMO ShortList 2003, combinatorics problem 4
darij grinberg   37
N Apr 30, 2025 by Maximilian113
Source: Problem 5 of the German pre-TST 2004, written in December 03
Let $x_1,\ldots, x_n$ and $y_1,\ldots, y_n$ be real numbers. Let $A = (a_{ij})_{1\leq i,j\leq n}$ be the matrix with entries \[a_{ij} = \begin{cases}1,&\text{if }x_i + y_j\geq 0;\\0,&\text{if }x_i + y_j < 0.\end{cases}\]Suppose that $B$ is an $n\times n$ matrix with entries $0$, $1$ such that the sum of the elements in each row and each column of $B$ is equal to the corresponding sum for the matrix $A$. Prove that $A=B$.
37 replies
darij grinberg
May 17, 2004
Maximilian113
Apr 30, 2025
IMO ShortList 2003, combinatorics problem 4
G H J
Source: Problem 5 of the German pre-TST 2004, written in December 03
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
darij grinberg
6555 posts
#1 • 6 Y
Y by anantmudgal09, Wizard_32, Adventure10, TFIRSTMGMEDALIST, Mango247, Deadline
Let $x_1,\ldots, x_n$ and $y_1,\ldots, y_n$ be real numbers. Let $A = (a_{ij})_{1\leq i,j\leq n}$ be the matrix with entries \[a_{ij} = \begin{cases}1,&\text{if }x_i + y_j\geq 0;\\0,&\text{if }x_i + y_j < 0.\end{cases}\]Suppose that $B$ is an $n\times n$ matrix with entries $0$, $1$ such that the sum of the elements in each row and each column of $B$ is equal to the corresponding sum for the matrix $A$. Prove that $A=B$.
Attachments:
This post has been edited 4 times. Last edited by MellowMelon, Nov 13, 2018, 7:56 PM
Reason: fix typo: x_n -> y_n
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
grobber
7849 posts
#2 • 3 Y
Y by Adventure10, Mango247, and 1 other user
Consider the matrix $A-B$. It has only $-1,0,1$ as elements, and we want to prove that it actually has only $0$. It also has the property that the sum of the elements on each line and each column is $0$. In $A$ we can't have $i\ne k,\ j\ne l$ s.t. $a_{ij},a_{kl}=1,\ a_{il},a_{kj}=0$ or vice-versa. Then in $A-B$ we can't have $i\ne k,\ j\ne l$ s.t. $a_{ij},a_{kl}=1,\ a_{il},a_{kj}\ne 1$ or vice-versa. [Moderator edit: Here and in the following, $a_{uv}$ doesn't necessarily denote the $\left(u,v\right)$-th entry of the matrix $A$, but rather the $\left(u,v\right)$-th entry of whatever matrix we are currently talking about.]

Consider the line in $A-B$ with the maximal number of $1$'s. If this number is non-zero, then there must be some $-1$'s as well on this line (call it line $i$). Assume $a_{ij}=-1$. In this case there is a $k$ s.t. $a_{kj}=1$ (because the sum of all numbers on column $j$ is $0$). If for all $m$ for which $a_{im}=1$ we also have $a_{km}=1$ then on the line $k$ we have more $1$'s than on the line $i$, and that's a contradiction, so there must exist an $l$ s.t. $a_{il}=1$ and $a_{kl}\ne 1$. But if we look at the four elements $a_{ij}=-1\ne 1,a_{kl}\ne 1,a_{il}=a_{kj}=1$ we see that they contradict what we said in the first paragraph.
This post has been edited 3 times. Last edited by darij grinberg, Aug 27, 2011, 11:15 AM
Reason: typo fixed; renamed a variable to avoid double use; added mod edit; however Wolfy's objection still seems correct
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Wolfy
12 posts
#3 • 3 Y
Y by Adventure10, Mango247, and 1 other user
grobber wrote:
Then in $A-B$ we can't have $i\ne k,\ j\ne l$ s.t. $a_{ij},a_{kl}=1,\ a_{il},a_{kj}\ne 1$ or vice-versa.
why?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Nukular
1963 posts
#4 • 3 Y
Y by Adventure10, Mango247, and 1 other user
[ Moderator edit: The following solution renames the matrices $A$ and $B$ as $M$ and $N$. ]

We can make this really easy by generalizing to n x m matrices, and forcing the x_i (1<=i <= n), y_j (1 <= j <= m) to be nondecreasing sequences (note row/column swapping does not affect the condition if we do likewise with N).

Let a_i,j be the position in M determined by x_i , y_j.

Then consider a_(n,1). If it is 0, the entire column a_(k,1) must be 0's and therefore M, N must match in this column. Deleting this column reduces m by one.

If it is 1, the entire row a_(n,k) must be 1's and therefore M,N must match in this row. Deleting this row reduces n by one.

Therefore, by inducting on m+n we see the result.
This post has been edited 1 time. Last edited by MellowMelon, May 20, 2016, 8:52 PM
Reason: fix formatting error
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dashmiz
124 posts
#5 • 2 Y
Y by Adventure10, Mango247
it is easy try to prove that we have always a column with all 1 or all zero or else
a row.
then use mathematical induction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IDMasterz
1412 posts
#6 • 7 Y
Y by Wizard_32, Pluto1708, brokendiamond, hakN, Adventure10, Mango247, and 1 other user
Consider $\sum_{i=1}^{n} \sum_{j=1}^n (x_i+y_j)(a_{ij} - b_{ij})$. This sum is $0$. Now, consider all $i, j$ s.t. $a_{ij} \neq b_{ij}$. We have that is $a_{ij}=1 \implies b_{ij} =0 \implies (a_{ij} - b_{ij})(x_i + y_j)$ is positive. Similarly, $a_{ij} = 0 \implies b_{ij} = 1, x_i + y_j < 0$ so that is still positive. Summing yields a contradiction, so $A=B$.
This post has been edited 1 time. Last edited by darij grinberg, Oct 26, 2017, 8:00 AM
Reason: "a_{ij} + b_{ij}" -> "a_{ij} - b_{ij}"
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pi37
2079 posts
#7 • 3 Y
Y by hakN, Adventure10, Mango247
We only consider the entries which change when $A$ switches to $B$. Let $e_{i,j}$ be $1$ if $b_{i,j}=1$ while $a_{i,j}=0$, and let $e_{i,j}$ be $-1$ if $b_{i,j}=0$ while $a_{i,j}=1$. Let $S\subseteq [n]^2$ be the subset of entries which changed. Note that for any fixed $j$,
\[
\sum_{(i,j)\in S} e_{i,j}=0
\]and similarly for fixed $i$, varying $j$. So if $i,j$ are allowed to vary over all possible choices,
\[
\sum_{(i,j) in S} e_{i,j}(x_i+y_j) = \left(\sum_{i} x_i\sum_{(i,j) \in S} e_{i,j}\right)+\left(\sum_{j} y_j \sum_{(i,j)\in S} e_{i,j}\right)=0
\]However for any $(i,j)\in S$, $e_{i,j}(x_i+y_j)\ge 0$, and for any $e_{i,j}=-1$, equality does not hold. Since there is at least one negative value of $e_{i,j}$, we get $0>0$, which is a contradiction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
anantmudgal09
1980 posts
#8 • 4 Y
Y by Wizard_32, Adventure10, Mango247, Deadline
IMO SL 2003 C4 wrote:
Given $n$ real numbers $x_1$, $x_2$, ..., $x_n$, and $n$ further real numbers $y_1$, $y_2$, ..., $y_n$. The entries $a_{ij}$ (with $1\leq i \leq n$ and $1 \leq j\leq n$) of an $n\times n$ matrix $A$ are defined as follows:

$a_{ij}=\left\{ \begin{array}{c} 1\text{\ \ \ \ \ \ if\ \ \ \ \ \ }x_{i}+y_{j}\geq 0; \\ 0\text{\ \ \ \ \ \ if\ \ \ \ \ \ }x_{i}+y_{j}<0. \end{array} \right.$

Further, let $B$ be an $n\times n$ matrix whose elements are numbers from the set $\left\{0;\  1\right\}$ satisfying the following condition: The sum of all elements of each row of $B$ equals the sum of all elements of the corresponding row of $A$; the sum of all elements of each column of $B$ equals the sum of all elements of the corresponding column of $A$. Show that in this case, $A = B$.

Firstly, shift the sequences $(x_1, \dots, x_n)$ and $(y_1, \dots, y_n)$ by a positive constant so that $x_i+y_j<0$ doesn't change for any pair $i, j$.

Note that if $A \ne B$ then the sum $$S \overset{\text{def}}{:=} \sum_{i, j} (a_{ij}-b_{ij})(x_i+y_j),$$is positive since each of the summands is positive (in general they would be non-negative). However, we see that $$S=\sum_{i} x_i \left(\sum_{j} (a_{ij}-b_{ij}) \right)+\sum_{j} y_j \left(\sum_{i} (a_{ij}-b_{ij}) \right)=0,$$yielding the desired contradiction. $\blacksquare$

EDIT: A few glaring errors with this proof. Thanks to Darij for providing a good fix in the post below :)
This post has been edited 2 times. Last edited by anantmudgal09, Oct 26, 2017, 10:32 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
darij grinberg
6555 posts
#9 • 3 Y
Y by anantmudgal09, Adventure10, Mango247
anantmudgal09 wrote:
Firstly, shift the sequences $(x_1, \dots, x_n)$ and $(y_1, \dots, y_n)$ by a positive constant so that $x_i+y_j<0$ doesn't change for any pair $i, j$.

What do you mean by "shift", and why are you doing that?
anantmudgal09 wrote:
Note that if $A \ne B$ then the sum $$S \overset{\text{def}}{:=} \sum_{i, j} (a_{ij}-b_{ij})(x_i+y_j),$$is positive since each of the summands is positive (in general they would be non-negative).

Uhm, they're not quite all positive. First of all, $x_i + y_j$ can be $0$, which causes the term $(a_{ij}-b_{ij})(x_i+y_j)$ to vanish. Second, $a_{ij}$ can equal $b_{ij}$, with the same consequence.

The argument you probably want to make is the following: Each of the terms $(a_{ij}-b_{ij})(x_i+y_j)$ is nonnegative; thus the whole sum $\sum_{i, j} (a_{ij}-b_{ij})(x_i+y_j)$ is nonnegative. Furthermore, we claim that this sum is positive. To prove this, it suffices to find at least one positive addend. Notice that the sum of all entries of $A$ equals the sum of all entries of $B$ (since the sum of all elements of each row of $B$ equals the sum of all elements of the corresponding row of $A$); therefore, at least one entry of $A$ must be smaller than the corresponding entry of $B$ (since $A \neq B$). In other words, $a_{ij} < b_{ij}$ for some $i$ and $j$. Fix such $i$ and $j$, and observe that $a_{ij}$ and $b_{ij}$ must be $0$ and $1$, respectively (since $a_{ij} < b_{ij}$). From $a_{ij} = 0$, we obtain $x_i + y_j < 0$. Thus, $\left(\underbrace{a_{ij}}_{=0}-\underbrace{b_{ij}}_{=1}\right)\left(x_i+y_j\right) = \left(0-1\right) \left(x_i+y_j\right) = - \left(x_i+y_j\right) > 0$ (since $x_i + y_j < 0$), and so we have found a positive term.

Nice argument -- just needs this little fix.
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
#10 • 4 Y
Y by Bandera, matinyousefi, Adventure10, Mango247
Did I do something wrong?

Permute the rows and columns of $A$ and $B$ simultaneously in the same way so that $x_1\ge x_2\ge\ldots x_m$ and $y_1\ge y_2\ge\ldots y_n$ (we generalize to $m\times n$). Now, note that our 1's form a Young diagram in $A$. A column past the 1's in the first row is all 0's so we may remove it and induct down. Otherwise, the entire first row consists of 1's, so we may remove it and induct down.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MathStudent2002
934 posts
#11 • 4 Y
Y by darij grinberg, kingofgeedorah, Adventure10, Mango247
What a funny problem!

For a binary matrix $A$, we define a stone move on its entries to be picking $i,j,k,\ell$ (where $i\neq j$, $k\neq \ell$) so that $a_{ik}+a_{j\ell} = 2$, $a_{i\ell}+a_{jk} = 0$, and swapping entries so that $a_{ik} = a_{j\ell} = 0$, $a_{i\ell}=a_{jk} = 1$. Now, we claim that if $A, B$ are rectangular binary matrices with the same size so that the row, column sums of $A$ and $B$ are the same, then $B$ can be reached from $A$ via a finite sequence of stone moves. Indeed, let $r_1,\ldots, r_m$ denote the row sums, and $c_1,\ldots, c_n$ denote the column sums. It suffices to show that we can reach some matrix $C$ from both $A$ and $B$ via a finite sequence of stone moves, since stone moves are undoable.

Indeed, we will demonstrate an algorithm that decreases $S = \sum\limits_{i=1}^n |a_{1i}-b_{1i}|$, which will eventually reach zero (this is essentially USAMO 2015/4). Indeed, suppose that $S \neq 0$. Then, there exist $i$ such that $a_{1i}\neq b_{1i}$, say $a_{1i} = 1, b_{1i} = 0$. There must also exist $j\neq i$ with $a_{1j} = 0$, $b_{1j} = 1$, since $\sum a_{1i}-b_{1i} = 0$. Now, we claim that there either exists $k$ so that $a_{ki} = 0$ and $a_{kj} = 1$, or there exists $k$ so that $b_{ki} = 1, b_{kj} = 0$. Indeed, suppose not, then $a_{ki}-a_{kj} \geq 0$ for $k\geq 2$, and $b_{ki}-b_{kj}\leq 0$ for $k\geq 2$, and \[
0 < \sum\limits_{k=1}^m a_{ki}-a_{kj}  = c_i - c_j = \sum\limits_{k=1}^m b_{ki}-b_{kj} < 0,
\]contradiction. So, if there exists $a_{ki} = 0$, $a_{kj} = 1$, we simply apply a stone move to $A$; else apply a stone move to $B$, and $a_{1i} = b_{1i}$, $a_{1j} = b_{1j}$, so we have decreased $S$. Eventually this forces $S = 0$, so we may discard the first row and repeat on the $m-1\times n$ matrices $A', B'$. So, by applying stone moves to $A$, $B$ we can reach a common $C$, and this means we can apply stone moves $A\to C\to B$.

However, note that if $a_{ik}+a_{j\ell} = 2$, $a_{i\ell} = a_{jk} = 0$, then we get $x_i+y_k > 0$, $x_j+y_\ell > 0$ which implies $x_i+x_j+y_k+y_\ell> 0$, but $x_i + y_\ell \leq 0$, $x_j+y_k \leq 0$, which yields $x_i+x_j +y_k+y_\ell \leq 0$, contradiction. So, we cannot apply any stone moves to $A$; since $B$ is reachable by stone move, $A=B$.
This post has been edited 2 times. Last edited by darij grinberg, Sep 9, 2018, 4:48 PM
Reason: typos: added a "such that"; replaced "so that $a_{ki} = 0$ or $a_{kj} = 1$" by "so that $a_{ki} = 0$ and $a_{kj} = 1$"; replace "stone move to $a$" by "stone move to $A$".
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
darij grinberg
6555 posts
#12 • 2 Y
Y by Adventure10, Mango247
@MathStudent2002: I think you use two different definitions of "stone move", one of which has a determined direction (perhaps $i < j$ and $k < \ell$?) whereas the other doesn't.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MathStudent2002
934 posts
#13 • 2 Y
Y by Adventure10, Mango247
Hm? I'm pretty sure the definition is always taking a rectangle with two opposite corners 1 and the other two 0 and swapping the 1s with the 0s?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
darij grinberg
6555 posts
#14 • 1 Y
Y by Adventure10
Oops, I've misunderstood your last paragraph, sorry. Nice proof! (I've fixed a few typos.)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
TheDarkPrince
3042 posts
#15 • 1 Y
Y by Adventure10
Notice that we can change $y_i$ to $-y_i$ and rephrase the problem:
rephrased problem wrote:
Let $x_1,\ldots, x_n$ and $y_1,\ldots, y_n$ be real numbers. Let $A = (a_{ij})_{1\leq i,j\leq n}$ be the matrix with entries \[a_{ij} = \begin{cases}1,&\text{if }x_i \geq y_j;\\0,&\text{if }x_i < y_j.\end{cases}\]Suppose we are given sum of each row and sum of each column, then show that we can find all values of $A$.

Solution. Arrange $n$ numbers in increasing order (not equal). Now sum of each row say the $i^{th}$, means the number of $y_j$'s greater than $x_i$. Now place the $x_i$'s according the $n$ numbers assuming the $n$ numbers were $y_j$'s in increasing order. Now sum of each column say the $j^{th}$ mean the number of $x_i$'s greater than $y_j$, so label the $n$ numbers now.

Therefore we can define the entire set $A$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
darij grinberg
6555 posts
#16 • 2 Y
Y by Adventure10, Mango247
What $n$ numbers are you arranging, @TheDarkPrince?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
TheDarkPrince
3042 posts
#17 • 1 Y
Y by Adventure10
darij grinberg wrote:
What $n$ numbers are you arranging, @TheDarkPrince?

Some $n$ numbers. Notice that $y_i$'s are reals and only their relative position matter, so we choose any $n$ numbers and accordingly fix $x_i$ and $y_i$.
This post has been edited 1 time. Last edited by TheDarkPrince, Nov 14, 2018, 6:39 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
darij grinberg
6555 posts
#18 • 2 Y
Y by Adventure10, Mango247
??? Sorry, I really don't follow.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
TheDarkPrince
3042 posts
#19 • 2 Y
Y by Adventure10, Mango247
darij grinberg wrote:
Sorry, I really don't follow.

Sorry, I'm not able to express it too well :(

We need to find the values of matrix $A$. We have defined the elements of $A$ in such a way that $x_i$'s and $y_i$'s value doesn't matter only their relative value matters, i.e which is greater.

Sum of each row means number of values of $y_i$'s greater than that particular $x_j$.
We'll take an example:

Suppose $n = 3$, sum of row$_1 = 2$, sum of row$_2 = 3$, sum of row$_3 = 3$, sum of column$_1 = 3$, sum of column$_2 = 3$, sum of column$_3= 2$.

We'll try to find the values of matrix $A$ with this information.

[asy]
 /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki, go to User:Azjps/geogebra */
import graph; size(4cm); 
real labelscalefactor = 0.5; /* changes label-to-point distance */
pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ 
pen dotstyle = black; /* point style */ 
real xmin = -5.664651162790702, xmax = 17.033023255813966, ymin = -6.063255813953488, ymax = 6.141395348837212;  /* image dimensions */

 /* draw figures */
 /* dots and labels */
dot((0.,0.),linewidth(4.pt) + dotstyle); 
dot((3.,0.),dotstyle); 
dot((5.,0.),dotstyle); 
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); 
 /* end of picture */
[/asy]

Sum of row$_1 = 2$ means $x_1$ is less than one ($3-2 = 1$) $y_i$.

[asy]
import graph; size(4cm); 
real labelscalefactor = 0.5; /* changes label-to-point distance */
pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ 
pen dotstyle = black; /* point style */ 
real xmin = -5.664651162790702, xmax = 17.033023255813966, ymin = -6.063255813953488, ymax = 6.141395348837212;  /* image dimensions */

pair A = (0.,0.), B = (3.,0.), C = (5.,0.), x_1 = (3.7493023255813975,0.); 
 /* draw figures */
 /* dots and labels */
dot(A,linewidth(4.pt) + dotstyle); 
dot(B,dotstyle); 
dot(C,dotstyle); 
dot(x_1,dotstyle); 
label("$x_1$", (3.8237209302325605,0.1879069767441865), NE * labelscalefactor); 
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); 
 /* end of picture */
[/asy]

Sum of row$_2 = 3$ means $x_2$ is less than zero ($3-3 = 0$) $y_i$.

[asy]
 /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki, go to User:Azjps/geogebra */
import graph; size(4cm); 
real labelscalefactor = 0.5; /* changes label-to-point distance */
pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ 
pen dotstyle = black; /* point style */ 
real xmin = -5.664651162790702, xmax = 17.033023255813966, ymin = -6.063255813953488, ymax = 6.141395348837212;  /* image dimensions */

pair A = (0.,0.), B = (3.,0.), C = (5.,0.), x_1 = (3.7493023255813975,0.), x_2 = (5.795813953488376,0.); 
 /* draw figures */
 /* dots and labels */
dot(A,linewidth(4.pt) + dotstyle); 
dot(B,dotstyle); 
dot(C,dotstyle); 
dot(x_1,dotstyle); 
label("$x_1$", (3.8237209302325605,0.1879069767441865), NE * labelscalefactor); 
dot(x_2,dotstyle); 
label("$x_2$", (5.870232558139539,0.1879069767441865), NE * labelscalefactor); 
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); 
 /* end of picture */
[/asy]

Repeating this for columns gives:

[asy]
 /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki, go to User:Azjps/geogebra */
import graph; size(4cm); 
real labelscalefactor = 0.5; /* changes label-to-point distance */
pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ 
pen dotstyle = black; /* point style */ 
real xmin = -5.664651162790702, xmax = 17.033023255813966, ymin = -6.063255813953488, ymax = 6.141395348837212;  /* image dimensions */

pair y_1 = (0.,0.), y_2 = (3.,0.), y_3 = (5.,0.), x_1 = (3.7493023255813975,0.), x_2 = (5.795813953488376,0.), x_3 = (6.744651162790702,0.); 
 /* draw figures */
 /* dots and labels */
dot(y_1,linewidth(4.pt) + dotstyle); 
label("$y_1$", (0.06558139534883684,0.1506976744186051), NE * labelscalefactor); 
dot(y_2,dotstyle); 
label("$y_2$", (3.079534883720932,0.1879069767441865), NE * labelscalefactor); 
dot(y_3,dotstyle); 
label("$y_3$", (5.070232558139538,0.1879069767441865), NE * labelscalefactor); 
dot(x_1,dotstyle); 
label("$x_1$", (3.8237209302325605,0.1879069767441865), NE * labelscalefactor); 
dot(x_2,dotstyle); 
label("$x_2$", (5.870232558139539,0.1879069767441865), NE * labelscalefactor); 
dot(x_3,dotstyle); 
label("$x_3$", (6.819069767441865,0.1879069767441865), NE * labelscalefactor); 
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); 
 /* end of picture */
[/asy]

This gives the matrix \[\begin{bmatrix}
1 & 1 & 0\\
1 & 1 & 1\\
1& 1 &  1
\end{bmatrix}\]
Was this kinda clear?
This post has been edited 1 time. Last edited by TheDarkPrince, Nov 15, 2018, 7:05 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
darij grinberg
6555 posts
#20 • 3 Y
Y by HolyMath, Adventure10, Mango247
No, I still don't follow. You're saying nothing about $B$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pad
1671 posts
#21 • 3 Y
Y by lahmacun, Adventure10, Mango247
We will prove the result in general for an $m\times n$ matrix. Strong induct on $m+n$, the base case of $m+n=2$ being trvial.

We first apply the permutation $\pi_1$ to $\{x_i\}$ and $\pi_2$ to $\{y_i\}$ to sort them into decreasing order, and also permute $A$ and $B$ into $A'$ and $B'$ by applying $\pi_1$ to the rows and $\pi_2$ to the columns. To retrieve $A$ and $B$, we apply $\pi_1^{-1}$ to the rows and $\pi_2^{-1}$ to the columns. So if we can show $A'=B'$, we are done.

Since $x$ and $y$ are sorted, $A$ will form a Young Tableux. (This is where each row has a number of 1's, and then 0's, with the constraint that the number of 1's in the rows is non-increasing.) If there are any rows of 0's at the bottom of $A$, $B$ must also have these rows of 0's, since the row sum is 0. Then we can delete these rows, and since $m+n$ decreased, we finish by induction. Similarly for columns of 0's at the right. If there are no rows or columns of 0's, there must be a row of 1's in $A$. Then $B$ must have this same row of 1's, since the row sum is maximum. So we can delete it and finish by induction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
william122
1576 posts
#23 • 1 Y
Y by Adventure10
WLOG $\{x_i\}$ and $\{y_i\}$ are both sorted. Then, the $1$s in $A$ form a Young's Tableau. If we consider the first column of $B$, the amount of $1$s it has is equal to the number of rows with at least one $1$, so it is fixed. In a similar manner, the second column is now fixed, as its sum is equal to the number of rows which still have another $1$, and so forth. So, $B$ is fixed, and thus must be $A$, as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
BOBTHEGR8
272 posts
#24 • 3 Y
Y by hakN, Adventure10, Mango247
We will prove the general result for $m \times n$
Induction on $m+n$
The case $m+n=3$ is trivial. Assume for $m+n=k-1$
Now let $m+n=k$ ,
Consider the row in $A$ with maximum number of $1's$
Case 1- This row contains only $1's$ , then the corresponding row in $B$ must also contain all ones, hence we may delete this row and complete the problem by induction hypothesis.
Case 2 - This row contains a $0$, now we claim that the column of this $0$ ,say $i$, contains only $0's$ and then complete the proof as before.
If possible let this column $i$ contain a $1$ . We show that the row of this $1$ ,say $l$, contains more $1's$ than our chosen row, say $k$,m contradicting maximality of chosen row. Let there be a $1$ in $j'th$ column of row $k$. We show that there must be a $1$ in $j'th$ column of row $l$.Whereas we already have an extra $1$ in row $l$, hence proof will be complete.
If possible let $a_{k,j}=1$ but $a_{l,j}=0$, we already know $a_{k,i}=0$ and $a_{l,i}=1$ .
Hence $x_l+x_j<0, x_k+x_i<0 \implies x_i+x_j+x_l+x_k<0$
And $x_k+x_j\geq0 x_l+x_i\geq0 \implies  x_i+x_j+x_l+x_k\geq0$
Contradiction.
Hence proved.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math_pi_rate
1218 posts
#25 • 1 Y
Y by amar_04
Nice problem! Here's my solution: Rearrange the rows of $A$ so that number of ones in a row is a non-increasing sequence as we go down. Do the same row transformations with $B$. Note that this doesn't affect the problem, since only the order of the rows is affected. This change is equivalent to ordering the $x_i$'s as $x_1 \geq x_2 \geq \dots \geq x_n$. Then, for a fixed $j \in [n]$, we have $$x_1+y_j \geq x_2+y_j \geq \dots \geq x_n+y_j$$In particular, this means that if we have a $1$ in some cell, then all cells above in the same column must also contain $1$. Do an analogous transformation of the columns, which corresponds to arranging the $y_i$'s as $y_1 \geq y_2 \geq \dots \geq y_n$. This gives that if there is a $1$ in some cell, then all cells to its left (in the same row) must also have $1$'s. Let $a_i$ denote the number of $1$'s in the $i^{\text{th}}$ row (in this new matrix). Then the above transformation forces $a_1 \geq a_2 \geq \dots \geq a_n$. If $a_n \neq 0$, then the first $a_n$ columns must contain all $1$'s. So the first $a_n$ columns of $B$ must also contain $1$'s. But, since the last row of $B$ also has $a_n$ $1$'s, which are already filled in the first $a_n$ columns, so the remaining elements of the last row of $B$ must be zero (i.e. same as $A$). In that case, a simple induction on $n \geq 1$ finishes the argument. Else, if $a_n=0$, then the last row of $A$ has only zeros. So the last row of $B$ must also be zero. In that case, consider the largest $i$ such that $a_i \neq 0$. Then all rows of $A$ below the $i^{\text{th}}$ row consists of only $0$'s, so the same must be true for $B$. But, the first column contains exactly $i$ $1$'s in both $A$ and $B$, and there are already $(n-i)$ $0$'s in the first column of $B$, so the first column's initial $i$ cells must all have $1$. So in this situation again the inductive step suffices. Hence, done. $\blacksquare$

REMARKS: Tbh I didn't like my writeup much, coz there are just too many words :P, but I guess the basic idea is pretty simple. The resulting matrix after the row/column transformations is what I had used in my solution to the first problem here.
This post has been edited 3 times. Last edited by math_pi_rate, Apr 13, 2020, 11:58 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
rcorreaa
238 posts
#26
Y by
We gerenalize the problem for an $m \times n$ board. Suppose WLOG that $x_1 \leq x_2 \leq ... \leq x_m$ and $y_1 \leq y_2 \leq ... \leq y_n$.

Now, we induct on $m+n$ (the base cases are easy).

If the first row of $A$ has all its entries $0$, we can erase it and induct, since the correspondent row in $B$ must have all its entries $0$ as well. Otherwise, there exists a $k \leq n$ such that $x_1+y_k \geq 0$. Thus, since $$x_1+y_n \geq x_1+y_{n-1} \geq ... \geq x_1+y_k \geq 0$$the cell $(1,n)$ is equal to $1$.

Furthermore, $$x_m+y_n \geq x_{m-1}+y_n \geq ... \geq x_1+y_n \geq 0$$$\implies$ all cells above $(1,n)$ are equal to $1$. Then, we can erase this column and induct, since the correspondent column in $B$ must contain only $1$'s in it.

Hence, we are done.
$\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathaddiction
308 posts
#27 • 1 Y
Y by Mango247
We consider the general $m\times n$ case, we begin by induction. The case when $m=1$ is easy to check. Now we consider the case $(m,n)$ with the assumption that all cases $(m',n')$ with $m'\leq m$,$n'\leq n$ and $(m',n')\neq (m,n)$ holds. Now WLOG assume $|x_1|=\max\{|x_1|,|x_2|,...,|x_n|,|y_1|,...,|y_n|\}$. Therefore, the sum of the column corresponding to $x_1$ must have entries either all equal to $1$ or $0$. Therefore the entries of $B$ must also be the same, now we an apply the inductive hypothesis to the remaining matrix 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.
VicKmath7
1389 posts
#28
Y by
Nice problem!
Generalize for $x_1> x_2> \cdots> x_n; y_1>y_2> \cdots >y_m$ (WLOG the numbers are sorted, otherwise interchange some and rows and columns) and we will induct. Obviously the original matrix $A$ is an Young Tableux now (i.e. the rows and columns have decreasing number of 1's from left to right and from uppermost edge to the lowermost edge). If there is an all-zero row or column in $A$, we are done (this row or column will appear also in $B$, so we can remove it and induct down). Otherwise there is an all-one row (the uppermost one), so this row must be also in $B$, so we can remove it and induct down.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cj13609517288
1900 posts
#29 • 2 Y
Y by Mango247, Mango247
Catloe walk is OP!

Assume FTSOC that the two matrices are not equal. Consider where the two matrices differ. If $A$ has a $1$ in some spot that $B$ has a $0$ in, call it a Ritwino cell. If it is the other way around, call it a Jatloeo cell.

Now, pick any Ritwino cell in the grid and let Catloe be on it. Note that if a row or column has one changed cell, it must have at least two changed cells. So, select Jatloeo cell in the row, and let Catloe walk to it in a straight line. Now, select another Ritwino cell in the column Catloe is in, and let Catloe walk there. This repeats until Catloe reaches a cell he was already in. Catloe has completed a loop that only turns on Ritwino and Jatloeo cells. By parity, the turns are also alternating Ritwino and Jatloeo.

Now, consider the Ritwino and Jatloeo turns. Clearly, if we focus on any row or column, it has the same number of Ritwino and Jatloeo turns. Then the sum of $x_i+y_j$(all nonnegative) on the Ritwino turns is equal to the sum of $x_i+y_j$(all negative) on the Jatloeo turns(from matrix $A$), contradiction.
This post has been edited 1 time. Last edited by cj13609517288, Dec 19, 2022, 5:01 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awesomeming327.
1711 posts
#30 • 1 Y
Y by Om245
Consider
\[S=\sum_{i=1}^{n}{\sum_{j=1}^{n}{(x_i+y_j)(a_{ij}-b_{ij})}}=\sum_{i=1}^{n}{\left(x_i\sum_{j=1}^{n}{y_j(a_{ij}-b_{ij})}\right)}+\sum_{j=1}^{n}{\left(y_j\sum_{j=1}^{n}{x_i(a_{ij}-b_{ij})}\right)}=0\]If $x_i+y_i\ge 0$ then $a_{ij}-b_{ij}=1-b_{ij}\ge 0$ and if $x_i+y_i<0$ then $a_{ij}-b_{ij}=-b_{ij}\le 0$. Either way, $(x_i+y_i)(a_{ij}-b_{ij})\ge 0$ so $S\ge 0$. Equality holds if and only if $x_i+y_i=0$ or $a_{ij}=b_{ij}$ for each $i,j$. In both cases, $a_{ij}\ge b_{ij}$ so if the sum of row and column equality were to hold, $a_{ij}=b_{ij}$ as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
sman96
136 posts
#31
Y by
WLOG, let $x_1 \leq x_2 \leq \dots \leq x_n$ and same for $y$.
Then, $a_{i1} \leq \dots \leq a_{in}$. And same for the columns.
Now, FTSOC, let there exist $B\neq A$ with those property.
Now we create $C = A-B$ then the entries of $C$ will be $-1,0,1$. And notice that if $c_{ip} = -1$ and $c_{iq} = 1$ then, $a_{ip} =0, a_{iq} =1 \implies p < q$. And same for entries in the same column. $\qquad(1)$

Now, we can have a sequence of $2k$ cells $z_1, \dots z_{2k}$ of $C$ s.t. $z_{2i}, z_{2i+1}$ are in the same row and $z_{2i-1}, z_{2i}$ are on the same column. And $z_{2i} =1, z_{2i+1}=-1$.
But this cycle contradicts because of $(1)$ so we are done. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
huashiliao2020
1292 posts
#32
Y by
Used with hint on OTIS 20\%

We can generalize to mxn by induction on a fixed n with varying m, and vice versa, since the process is the same, with the key being that we can remove a row/column if it has only 1s or only 0s since B MUST match up there. The base case m=n=1 is obvious. Now, assume there is a row (resp. column) with at least 1 1, we will take this with indices 1n, where we order indices s.t. $x_1\le x_2\le ...\le x_m,y_1\le y_2\le ...\le y_n$. Then since $x_m+y_n\ge x_{m-1}+y_n\ge\dots\ge x_1+y_n$, this entire row has 1s; in particular, we can remove it and it is reduced to inductive hypothesis. (If 1n was 0 then the entire row with indice x=1 is all 0s, and remove that).
This post has been edited 1 time. Last edited by huashiliao2020, Sep 12, 2023, 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.
john0512
4185 posts
#33
Y by
We generalize to all $n$ by $m$ rectangular matrices. The problem is essentially saying that there is only one possible matrix given the row and column sums.

Call a row or column boring if it consists of only 0s or only 1s.

The main claim of the problem is the following:

\begin{claim}
There exists a boring row or column.
\end{claim}

\begin{proof}
Suppose not. Then, arrange $x_1\dots x_n$ and $y_1\dots y_m$ in nondecreasing order in both ways (this only rearranges the rows and columns so it does not affect the claim). Note that each row and column is nondecreasing. Therefore, if there are no boring rows, each row must end with 1. Similarly, if there are no boring columns, each column must start with 0. However, this is a contradiction as the top right corner is both 0 and 1.
\end{proof}

We want to show that we can uniquely reconstruct the original matrix given the row and column sums. We will use induction. This is clearly true if either $n=1$ or $m=1$. We induct on $m+n$.

We know that there is a boring row or column. Thus, we can select a boring row or column (we can do this as one exists and we are given the row and column sums so we can pinpoint which one it is and we also know whether it consists of all 0s or all 1s) and consider the matrix excluding that boring row or column. We know the row and column sums of this remaining matrix (by taking the original row and column sums and subtracting away the boring row or column), and since this is a smaller value of $m+n$, by induction we are able to uniquely reconstruct this remaining matrix. Since we also know the contents of the boring row or column, we can reconstruct the entire matrix, hence done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shendrew7
794 posts
#34
Y by
Note that in any such $m \times n$ matrix, there must be at least one row or column with only 0's or 1's, as the number with highest absolute value surpresses the other entries. Thus this row or column is fixed, so we can simply remove it.

The resulting matrix has the same property, so we conclude by downwards induction. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Cusofay
85 posts
#35
Y by
Storage:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8857 posts
#36
Y by
Pretty straightforward but satisfying.

We let $p_i$ denote the sum of the $i$th row and $q_j$ denote the sum of the $j$th column; we will induct on $n$. It suffices to show that given the values of the $p_i$ and $q_j$ we can construct $A$ uniquely.

Claim. If $p_i = p_j$, then the rows $i$ and $j$ of $A$ are identical.

Proof. If otherwise, there is a $k$ such that $a_{ik} = 0$ and $a_{jk} = 1$ and $\ell$ with $a_{i\ell} = 1$ and $a_{j \ell} = 0$. It follows that $a_i < a_j$ from the first equation and $a_i > a_j$ from the second equation, contradiction. $\blacksquare$

By a similar argument as above, it follows that if $p_i > p_j$, then $a_i > a_j$ by looking at a $k$ with $a_{ik} = 1$ and $a_{jk} = 0$.

In particular, let $p_i$ be the (not necessarily unique) among the $p_j$. If some element $a_{ik} = 0$, then every element in column $k$ is zero as $x_i + y_k$ is the maximum among the $x_j + y_k$'s. In this case, $a_{ik} = 0$ precisely if $q_k = 0$, so the elements of row $i$ are fixed. Similarly, the elements of some column $k$ are fixed, so we can delete this row and column and induct down.

If no element $a_{ik} = 0$, it follows that $p_i = n$. Repeating this argument for the maximal column (assuming there is no zero row, otherwise we would be done as above), there is a column $q_j = n$. So row $i$ and column $j$ consist of solely $1$'s and are thus fixed; again, we can delete them and induct down, as needed.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
PEKKA
1848 posts
#37
Y by
First solve on a ISL 4! (With 20% hint)
First, WLOG assume $x_i \le x_j$ if $i \le j$ and a similar statement for $y.$
Next, we induct on a $p\times q$ matrix.
Base cases:
The $1\times 1,$ $n\times 1$ and $1 \times n$ matrices are easy to verify.
The $1 \times 1$ matrix is trivial. The $1\times n$ matrix is also easy to verify, as the column sums are just indicators for what number goes into the cell of a matrix, and the $n\times 1$ matrix is as easy to verify. (Assuming we write the number of rows before the number of columns)
Inductive step: We will use strong induction and assume that a matrix with $<p$ rows and $<q$ columns or $p$ rows and $<q$ columns or $<p$ rows and $q$ columns satisfy the desired statement. (All matrices that can be fit inside the $p\times q$ matrix)
Now consider the following on a $p\times q$ matrix:
If $x_1+y_p \ge 0,$ then the numbers $x_2+y_n, x_3+y_n \dots x_n+y_n$ are nonnegative too. This implies the bottommost row (row p) consists of all $1$'s in the cells.
If $x_1+y_p<0,$ then the numbers $x_1+y_{p-1}, x_1+y_{p-2}, \dots x_1+y_1$ are all negative. Therefore, the leftmost column (column $1$) consists of all $0$'s in the cells.
Once we have a row/column with all cells the same in $A,$ we get that the matrix $B$ must match that row/column. What is left is a matrix that fits inside the $p\times q$ matrix and by our inductive hypothesis we are done.
Therefore, our induction is complete and the desired statement holds.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
joshualiu315
2533 posts
#38
Y by
It suffices to show that the matrix can be uniquely determined by its row and column sums. We will prove this by induction on an $m \times n$ matrix. Denote a row or column as $\textit{repetitive}$ if it only contains $0$'s or only contains $1$'s.

The base cases where either $m$ or $n$ equals $1$ is clearly vacuous, so we move on to our inductive step.


Claim: Every matrix has at least one repetitive row or column.

Proof: WLOG let $x_1 \ge x_2 \ge \dots \ge x_n$ and $y_1 \ge y_2 \ge \dots \ge y_n$, which is allowed because it only rearranges rows and columns.

If $x_n+y_1 \ge 0$, then obviously $x_i+y_1 \ge 0$, for all $i$. Thus, the first row contains only $1$'s. Otherwise, since $x_n+y_1<0$, we must have $x_n + y_j<0$ for all $j$; this implies that the $n$th column contains only $0$'s. In either case, there must be at one repetitive row or column. $\square$


We can simply delete the repetitive row or column from the matrix. The row and column sums of the remaining matrix can easily be determined, completing the inductive step. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Maximilian113
574 posts
#39
Y by
We proceed by induction on an $m \times n$ matrix. The base cases $1 \times 1, m \times 1, 1 \times n$ are trivial as each row/column will be determined already (since either the row/column has exactly one number).

Now suppose that the proposition holds for an $m \times (n-1)$ grid and an $(m-1) \times n$ grid. For an $m \times n$ grid, WLOG order the $x_i$ so that they increase from left to right, and the $y_i$ so that the increase from top to bottom. If the bottom left is $1,$ then the entire bottom row is $1,$ so the entire bottom row of $B$ would be determined. If it is instead $-1,$ the entire left column is $-1$ so the entire bottom left column of $B$ is determined. In each case the determined part would match the corresponding part for $A,$ so now applying the inductive hypothesis, the proposition holds for an $m \times n$ grid, so we are done. QED
Z K Y
N Quick Reply
G
H
=
a