IMO ShortList 2003, combinatorics problem 4

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

IMO ShortList 2003, combinatorics problem 4

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

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.

6555 posts

#1 h May 17, 2004, 4:19 PM • 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.

7849 posts

#2 h Jun 1, 2004, 10:09 AM • 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.

12 posts

Wolfy

#3 h Feb 14, 2005, 7:53 PM • 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.

1963 posts

#4 h Mar 7, 2005, 8:50 PM • 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.

124 posts

#5 h Apr 28, 2005, 5:13 AM • 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.

1412 posts

#6 h Dec 26, 2013, 2:45 AM • 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.

2079 posts

pi37

#7 h May 20, 2016, 8:51 PM • 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.

1980 posts

#8 h Jul 3, 2017, 8:54 AM • 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.

6555 posts

#9 h Oct 26, 2017, 8:07 AM • 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.

1963 posts

ABCDE

#10 h Mar 28, 2018, 4:53 AM • 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

MathStudent2002

#11 h Sep 8, 2018, 5:59 PM • 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.

6555 posts

#12 h Sep 8, 2018, 10:44 PM • 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

MathStudent2002

#13 h Sep 9, 2018, 4:41 PM • 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.

6555 posts

#14 h Sep 9, 2018, 4:50 PM • 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.

3042 posts

#15 h Nov 13, 2018, 6:57 PM • 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.

6555 posts

#16 h Nov 13, 2018, 7:57 PM • 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.

3042 posts

#17 h Nov 14, 2018, 4:41 AM • 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.

6555 posts

#18 h Nov 14, 2018, 4:58 PM • 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.

3042 posts

#19 h Nov 15, 2018, 7:04 AM • 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.

6555 posts

#20 h Nov 15, 2018, 9:40 PM • 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.

1671 posts

pad

#21 h Sep 19, 2019, 6:49 AM • 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.

1576 posts

#23 h Oct 12, 2019, 2:45 PM • 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.

272 posts

#24 h Oct 26, 2019, 5:28 PM • 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.

1218 posts

#25 h Apr 13, 2020, 9:47 AM • 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

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

238 posts

#26 h Aug 29, 2020, 6:26 PM

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.

308 posts

#27 h Sep 3, 2020, 10:46 AM • 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.

1390 posts

#28 h Nov 5, 2022, 8:25 PM

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.

1922 posts

#29 h Dec 19, 2022, 4:54 PM • 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.

1726 posts

awesomeming327.

#30 h May 30, 2023, 12:44 AM • 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.

136 posts

sman96

#31 h Jun 6, 2023, 11:20 AM

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.

1292 posts

#32 h Aug 14, 2023, 2:32 AM

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.

4190 posts

#33 h Dec 16, 2023, 8:23 PM

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.

799 posts

#34 h Jan 4, 2024, 4:00 AM

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.

85 posts

#35 h Feb 9, 2024, 11:25 AM

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.

8867 posts

#36 h Jun 19, 2024, 2:32 AM

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.

1848 posts

PEKKA

#37 h Jul 7, 2024, 10:38 PM

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.

2534 posts

#38 h Dec 3, 2024, 2:40 AM

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.

575 posts

#39 h Apr 30, 2025, 2:55 PM

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

=

© 2025 AoPS Incorporated

a