Plan ahead for the next school year. Schedule your class today!

G
Topic
First Poster
Last Poster
k a July Highlights and 2025 AoPS Online Class Information
jwelsh   0
Jul 1, 2025
We are halfway through summer, so be sure to carve out some time to keep your skills sharp and explore challenging topics at AoPS Online and our AoPS Academies (including the Virtual Campus)!

[list][*]Over 60 summer classes are starting at the Virtual Campus on July 7th - check out the math and language arts options for middle through high school levels.
[*]At AoPS Online, we have accelerated sections where you can complete a course in half the time by meeting twice/week instead of once/week, starting on July 8th:
[list][*]MATHCOUNTS/AMC 8 Basics
[*]MATHCOUNTS/AMC 8 Advanced
[*]AMC Problem Series[/list]
[*]Plus, AoPS Online has a special seminar July 14 - 17 that is outside the standard fare: Paradoxes and Infinity
[*]We are expanding our in-person AoPS Academy locations - are you looking for a strong community of problem solvers, exemplary instruction, and math and language arts options? Look to see if we have a location near you and enroll in summer camps or academic year classes today! New locations include campuses in California, Georgia, New York, Illinois, and Oregon and more coming soon![/list]

MOP (Math Olympiad Summer Program) just ended and the IMO (International Mathematical Olympiad) is right around the corner! This year’s IMO will be held in Australia, July 10th - 20th. Congratulations to all the MOP students for reaching this incredible level and best of luck to all selected to represent their countries at this year’s IMO! Did you know that, in the last 10 years, 59 USA International Math Olympiad team members have medaled and have taken over 360 AoPS Online courses. Take advantage of our Worldwide Online Olympiad Training (WOOT) courses
and train with the best! Please note that early bird pricing ends August 19th!
Are you tired of the heat and thinking about Fall? You can plan your Fall schedule now with classes at either AoPS Online, AoPS Academy Virtual Campus, or one of our AoPS Academies around the US.

Our full course list for upcoming classes is below:
All classes start 7:30pm ET/4:30pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Wednesday, Jul 16 - Oct 29
Sunday, Aug 17 - Dec 14
Tuesday, Aug 26 - Dec 16
Friday, Sep 5 - Jan 16
Monday, Sep 8 - Jan 12
Tuesday, Sep 16 - Jan 20 (4:30 - 5:45 pm ET/1:30 - 2:45 pm PT)
Sunday, Sep 21 - Jan 25
Thursday, Sep 25 - Jan 29
Wednesday, Oct 22 - Feb 25
Tuesday, Nov 4 - Mar 10
Friday, Dec 12 - Apr 10

Prealgebra 2 Self-Paced

Prealgebra 2
Friday, Jul 25 - Nov 21
Sunday, Aug 17 - Dec 14
Tuesday, Sep 9 - Jan 13
Thursday, Sep 25 - Jan 29
Sunday, Oct 19 - Feb 22
Monday, Oct 27 - Mar 2
Wednesday, Nov 12 - Mar 18

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Tuesday, Jul 15 - Oct 28
Sunday, Aug 17 - Dec 14
Wednesday, Aug 27 - Dec 17
Friday, Sep 5 - Jan 16
Thursday, Sep 11 - Jan 15
Sunday, Sep 28 - Feb 1
Monday, Oct 6 - Feb 9
Tuesday, Oct 21 - Feb 24
Sunday, Nov 9 - Mar 15
Friday, Dec 5 - Apr 3

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Wednesday, Jul 2 - Sep 17
Sunday, Jul 27 - Oct 19
Monday, Aug 11 - Nov 3
Wednesday, Sep 3 - Nov 19
Sunday, Sep 21 - Dec 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Friday, Oct 3 - Jan 16
Sunday, Oct 19 - Jan 25
Tuesday, Nov 4 - Feb 10
Sunday, Dec 7 - Mar 8

Introduction to Number Theory
Tuesday, Jul 15 - Sep 30
Wednesday, Aug 13 - Oct 29
Friday, Sep 12 - Dec 12
Sunday, Oct 26 - Feb 1
Monday, Dec 1 - Mar 2

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Friday, Jul 18 - Nov 14
Thursday, Aug 7 - Nov 20
Monday, Aug 18 - Dec 15
Sunday, Sep 7 - Jan 11
Thursday, Sep 11 - Jan 15
Wednesday, Sep 24 - Jan 28
Sunday, Oct 26 - Mar 1
Tuesday, Nov 4 - Mar 10
Monday, Dec 1 - Mar 30

Introduction to Geometry
Monday, Jul 14 - Jan 19
Wednesday, Aug 13 - Feb 11
Tuesday, Aug 26 - Feb 24
Sunday, Sep 7 - Mar 8
Thursday, Sep 11 - Mar 12
Wednesday, Sep 24 - Mar 25
Sunday, Oct 26 - Apr 26
Monday, Nov 3 - May 4
Friday, Dec 5 - May 29

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)
Sat & Sun, Sep 13 - Sep 14 (1:00 - 4:00 PM PT/4:00 - 7:00 PM ET)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22
Friday, Aug 8 - Feb 20
Tuesday, Aug 26 - Feb 24
Sunday, Sep 28 - Mar 29
Wednesday, Oct 8 - Mar 8
Sunday, Nov 16 - May 17
Thursday, Dec 11 - Jun 4

Intermediate Counting & Probability
Sunday, Sep 28 - Feb 15
Tuesday, Nov 4 - Mar 24

Intermediate Number Theory
Wednesday, Sep 24 - Dec 17

Precalculus
Wednesday, Aug 6 - Jan 21
Tuesday, Sep 9 - Feb 24
Sunday, Sep 21 - Mar 8
Monday, Oct 20 - Apr 6
Sunday, Dec 14 - May 31

Advanced: Grades 9-12

Calculus
Sunday, Sep 7 - Mar 15
Wednesday, Sep 24 - Apr 1
Friday, Nov 14 - May 22

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)
Sunday, Aug 17 - Nov 9
Wednesday, Sep 3 - Nov 19
Tuesday, Sep 16 - Dec 9
Sunday, Sep 21 - Dec 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Oct 6 - Jan 12
Thursday, Oct 16 - Jan 22
Tues, Thurs & Sun, Dec 9 - Jan 18 (meets three times a week!)

MATHCOUNTS/AMC 8 Advanced
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)
Sunday, Aug 17 - Nov 9
Tuesday, Aug 26 - Nov 11
Thursday, Sep 4 - Nov 20
Friday, Sep 12 - Dec 12
Monday, Sep 15 - Dec 8
Sunday, Oct 5 - Jan 11
Tues, Thurs & Sun, Dec 2 - Jan 11 (meets three times a week!)
Mon, Wed & Fri, Dec 8 - Jan 16 (meets three times a week!)

AMC 10 Problem Series
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)
Sunday, Aug 10 - Nov 2
Thursday, Aug 14 - Oct 30
Tuesday, Aug 19 - Nov 4
Mon & Wed, Sep 15 - Oct 22 (meets twice a week!)
Mon, Wed & Fri, Oct 6 - Nov 3 (meets three times a week!)
Tue, Thurs & Sun, Oct 7 - Nov 2 (meets three times a week!)

AMC 10 Final Fives
Friday, Aug 15 - Sep 12
Sunday, Sep 7 - Sep 28
Tuesday, Sep 9 - Sep 30
Monday, Sep 22 - Oct 13
Sunday, Sep 28 - Oct 19 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, Oct 8 - Oct 29
Thursday, Oct 9 - Oct 30

AMC 12 Problem Series
Wednesday, Aug 6 - Oct 22
Sunday, Aug 10 - Nov 2
Monday, Aug 18 - Nov 10
Mon & Wed, Sep 15 - Oct 22 (meets twice a week!)
Tues, Thurs & Sun, Oct 7 - Nov 2 (meets three times a week!)

AMC 12 Final Fives
Thursday, Sep 4 - Sep 25
Sunday, Sep 28 - Oct 19
Tuesday, Oct 7 - Oct 28

AIME Problem Series A
Thursday, Oct 23 - Jan 29

AIME Problem Series B
Tuesday, Sep 2 - Nov 18

F=ma Problem Series
Tuesday, Sep 16 - Dec 9
Friday, Oct 17 - Jan 30

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, Aug 14 - Oct 30
Sunday, Sep 7 - Nov 23
Tuesday, Dec 2 - Mar 3

Intermediate Programming with Python
Friday, Oct 3 - Jan 16

USACO Bronze Problem Series
Wednesday, Sep 3 - Dec 3
Thursday, Oct 30 - Feb 5
Tuesday, Dec 2 - Mar 3

Physics

Introduction to Physics
Tuesday, Sep 2 - Nov 18
Sunday, Oct 5 - Jan 11
Wednesday, Dec 10 - Mar 11

Physics 1: Mechanics
Sunday, Sep 21 - Mar 22
Sunday, Oct 26 - Apr 26
0 replies
jwelsh
Jul 1, 2025
0 replies
2020 EGMO P3: Symmetric concurrence of angle bisectors in hexagon
alifenix-   38
N 4 minutes ago by asbodke
Source: 2020 EGMO P3
Let $ABCDEF$ be a convex hexagon such that $\angle A = \angle C = \angle E$ and $\angle B = \angle D = \angle F$ and the (interior) angle bisectors of $\angle A, ~\angle C,$ and $\angle E$ are concurrent.

Prove that the (interior) angle bisectors of $\angle B, ~\angle D, $ and $\angle F$ must also be concurrent.

Note that $\angle A = \angle FAB$. The other interior angles of the hexagon are similarly described.
38 replies
alifenix-
Apr 18, 2020
asbodke
4 minutes ago
Unit Digit
P162008   1
N 5 minutes ago by pooh123
If $f(x) = \left\lfloor\frac{x^{2x^4}}{x^{x^2} + 3} \right \rfloor$ then find the unit digit of $f(10).$
1 reply
P162008
Yesterday at 1:43 PM
pooh123
5 minutes ago
IMO 2009, Problem 5
orl   96
N 20 minutes ago by Miniapple268
Source: IMO 2009, Problem 5
Determine all functions $ f$ from the set of positive integers to the set of positive integers such that, for all positive integers $ a$ and $ b$, there exists a non-degenerate triangle with sides of lengths
\[ a, f(b) \text{ and } f(b + f(a) - 1).\]
(A triangle is non-degenerate if its vertices are not collinear.)

Proposed by Bruno Le Floch, France
96 replies
orl
Jul 16, 2009
Miniapple268
20 minutes ago
AOPS MO Introduce
MathMaxGreat   54
N 27 minutes ago by KevinYang2.71
$AOPS MO$

Problems: post it as a private message to me or @jerryZYang, please post it in $LATEX$ and have answers

6 Problems for two rounds, easier than $IMO$

If you want to do the problems or be interested, reply ’+1’
Want to post a problem reply’+2’ and message me
Want to be in the problem selection committee, reply’+3’
54 replies
MathMaxGreat
Yesterday at 1:04 AM
KevinYang2.71
27 minutes ago
No more topics!
IMO ShortList 2003, combinatorics problem 4
darij grinberg   39
N Jun 2, 2025 by ThatApollo777
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$.
39 replies
darij grinberg
May 17, 2004
ThatApollo777
Jun 2, 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
1392 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
1939 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.
1780 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
4192 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
816 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
8902 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
1854 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
2535 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
587 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
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AshAuktober
1043 posts
#40
Y by
Hmm, same as @above.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ThatApollo777
93 posts
#41 • 1 Y
Y by AshAuktober
Consider a bipartite graph whose vertices are rows on one side and columns on the other. Draw a red edge between 2 vertices if the corresponding cell has 0 in matrix A and 1 in matrix B, and blue edge if its 1 in matrix A and 0 in matrix B. Since row/column sums are same then every vertex must have blue degree = red degree. FTSOC assume A \neq B then there is atleast one edge, start at that edge and take a path that alternates colours, due to red deg = blue deg we never hit a dead end so there must be a cycle. Consider the cells corresponding to the edges of the cycle and add up the inequalities( the x_i, y_i ones) for the red edges and also for blue edges, these contradict each other so gg.
Z K Y
N Quick Reply
G
H
=
a