Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Is this correct? Assume the array is m rows x n columns. Let's assume for now that none of the numbers are integers. We can subtract any integer amount from any of the numbers without altering the problem. Thus, we can assume all the numbers are between 0 and 1, exclusively. In this case, the sum of all the rows will be less than n, and the sum of all columns will be less than m. We can make any of the numbers equal to either 0 or 1. Note that the sum of all the rows must equal the sum of all the columns, so the sum of the row totals equals the sum of the column totals. So if the sum total in row k is $ a_{k}$, we know there will be $ a_{k}$ 1's in that row and the rest 0s. Starting with the first row, place the $ a_k$ 1's in all the leftmost columns that currently need it, this must work in the end since the total number of 1's need for the rows is the same as the number needed for the columns. Now, if s of the numbers in a row are integers then they will turn to a 0 but will not be needed for that row because the row sum will be less than n-s, so we are fine in this case.

How will you do in this case with "0" and "1",dgreenb801 ? Collumn sums: 2 2 3 4 0 Row sums: 5 4 1 1

The column sum for the last column must be greater than 0 unless they are all integers, in which case the row sum would have to be less than 5, as I showed before.

dgreenb801 wrote: Starting with the first row, place the $ a_k$ 1's in all the leftmost columns that currently need it, this must work in the end since the total number of 1's need for the rows is the same as the number needed for the columns. This is extremely sketchy, and it does not obviously rule out something like what No Reason wrote. Since the problem is true, no one can actually produce a counter-example, but I'm certainly not convinced by the rigor of what you've written. (I mean, you've given an algorithm that almost certainly works, but your proof of its correctness is just an assertion.)

Hmm, I'm not really sure of how you would rigorously prove something that seems so obvious. Possibly we could assume the process doesn't work, then either we need more 1s or we run out of 1s, in either case it's a contradiction as the row sums don't equal the column sums? Anyways, if there are any integers, we can just leave the 0s where they are and the row and column they are in will just need that much less.

dgreenb801 wrote: Hmm, I'm not really sure of how you would rigorously prove something that seems so obvious. Can't prove it $ \Rightarrow$ not obvious. If your proof is an algorithm, you must do two things: 1. Show the algorithm does what it's supposed to. 2. Show the algorithm terminates. Leaving out one of these steps as "trivial" is at your own peril. My personal suggestion is to go back to the drawing board; patching up what you have I think is actually harder than finding some of the other solutions to this problem.

This may not work but I think it does. First, note that we only have to consider the fractional parts of all of the numbers in the grid, so that every number is in [0,1). Say the rectangle is $ m\times n$ ($ m$ rows, $ n$ columns). Along the side of length $ m$, let the sums of the numbers in the rows be $ a_{1},a_{2},\ldots,a_{m}$. Similarly, along the side of length $ n$, let the columns have sums $ b_{1},b_{2},\ldots,b_{n}$. We wish to show that given $ \sum a_{i}=\sum b_{i}$, we can place 0's and 1's in the rectangle so that we get the desired sums. We do this by induction. The claim is clear when $ m=n=1$. Now, consider adding a row or a column to a board, so that it's, say $ m\times(n+1)$. We now have $ a_{1},a_{2},\ldots,a_{m}$ and $ b_{1},b_{2},\ldots,b_{n+1}$. Note that there are at least $ b_{n+1}$ nonzero values among $ a_{1},a_{2},\ldots,a_{m}$, since if not, the sum of the values in the $ (n+1)$-st column will be at most $ b_{n+1}-1$, because there are at most this many nonzero values, and the values in these boxes are all less than 1 (in the original board). Now, take the corresponding rows to $ b_{n+1}$ of the nonzero $ a_{i}$, and put a 1 in the box of the $ n+1$-st column for each. What's left is an $ m\times n$ board, with non-negative sums for the rows and $ b_{1},b_{2},\ldots,b_{n}$ for the sums of the columns. Also, we can check that $ b_{1}+b_{2}+\cdots+b_{n}$ is equal to the sum of the sums of the rows, since $ a_{1}+a_{2}+\cdots+a_{m}=b_{1}+b_{2}+\cdots+b_{n+1}$, and we subtracted the same amount from each sum in filling out the $ (n+1)$-st column. Thus, by the inductive hypothesis, we can fill in the rest of the grid.

Are you sure you can apply the inductive hypothesis? Haven't you made the row sums nonintegral? By the way, your solution suggests that if there are no nonzero entries, we can take any row or column and arbitrarily relabel it with 0s and 1s to get the right sum, and still be okay. However, 0.5 0.5 1 0.5 0.5 1 In this board, taking the second row and relabeling it as 1,1,0 fails. So something has to have gone wrong.

Well for the first point, I don't think so, because I fill in the rightmost box in a given row with a 0 or 1, and what's left will be integral because the whole thing was originally integral. And for the second, I was assuming that everything in the grid is less than 1, because we can take the fractional parts of every entry - thus the 1's would be 0's. I agree that this is a little weird, though, I'll have to think about it more but I'm not sure I see the hole just yet.

OK, I see the problem now. You need to allow rows with all 1's as well, because at some point you will need to start a row or column with a string of consecutive 1's (even if it's one 1). Before, I was assuming that if $ a_{i}=n+1$, you're still allowed to put a 0 in this row, but this makes it so that in the $ m\times n$ grid, you have that $ a_{i}$ is too big. But this isn't hard to deal with; first take all the rows such that $ a_{i} = n + 1$, and fill them in accordingly, then you can essentially ignore them by deleting these rows and adjusting (decreasing) all of the $ b_{i}$'s by 1 for each row that we fill in with all 1's. Then, you should be able to fill in the rightmost column arbitrarily (avoiding the zero rows).

I think dgreenb801's argument can be slightly modified to work... the idea is that there's a lot of freedom in filling out $1$'s. First, we can take out the rows and columns that only have integers. It's also clear that we only care about the fractional part of each square, so we can assume that all squares contain a nonnegative number strictly less than $1$, and every row and column has at least one number that is not an integer (in fact, there must be at least two or else the sum of the row or column would be non-integral). Let $a_i\ge1$ be the sum of the numbers in row $i$ and $b_j\ge1$ be the sum of the numbers in column $j$. Also let $r_i$ be the number of non-integers in row $i$ and $c_j$ be the number of non-integers in column $j$, so because all the numbers in squares are nonnegative and strictly less than $1$, we have $r_i\ge a_i+1\ge2$ and $c_j\ge b_j+1\ge2$ for all $i,j$. Now we see that taking the floor of a number is simply changing it to $0$ and taking the ceiling is changing it to $1$. We want to change the non-integers to $0$'s and $1$'s and end up with exactly $a_i$ $1$'s in row $i$ and $b_j$ $1$'s in column $j$ for all $i,j$. In row $i$, there are exactly $r_i$ numbers we change to $0$ or $1$, and in column $j$, there are exactly $c_j$ numbers we change to $0$ or $1$ (call such a number available). Note that $\sum r_i=\sum c_j$ and $\sum a_i=\sum b_j$. We prove that this is always possible by strong induction on $m+n$. I think the base cases are when $mn=0$, which is hopefully trivial (it should be since it means we've finished changing everything). We will take out column $1$, in which we want to place $b_1$ $1$'s (with $c_1\ge b_1+1$ available numbers to choose from). Without loss of generality, we can rearrange the rows so that rows $1$ through $c_1$ have their column $1$ squares available. Say we make the first $b_1$ of these $1$ and the others $0$. Case 1: $r_i\ge a_i+2$ for $b_1<i\le c_1$. If we take out column $1$, then for $1\le i\le b_1$, $a_i,r_i$ are both reduced by $1$, for $b_1<i\le c_1$, $r_i$ is reduced by $1$ (the squares in column $1$ and row $i$ here are the available squares in column $1$ which have been made $0$), and for $c_1<i\le m$, $a_i,r_i$ are unaffected. Hence $r_i$ will remain at least $a_i+1$ for all rows, and the columns from $2$ to $n$ are unaffected, so this case follows from the inductive hypothesis. Case 2: $r_i\ge a_i+2$ for $b_1<i\le x<c_1$, and $r_i=a_i+1$ for $x<i\le c_1$ (we can assume without loss of generality that the rows are ordered like this). For $x<i\le c_1$, this means that row $i$ has $r_i=a_i+1$ available numbers, and since the squares in column $1$ and row $i$ have been made $0$, taking out column $1$ reduces $r_i$ by $1$ to $a_i$. Since we need $a_i$ squares in row $i$ to be $1$'s, though, we need to make all $r_i$ squares in row $i$ not in column $1$ equal to $1$. If we do this for all $x<i\le c_1$ (we are essentially taking out these rows), then it's clear that for each column $2\le j\le n$, the respective $b_j$ and $c_j$ are both reduced by the same amount (more precisely, both decrease by the number of squares column $j$ has available in rows $x<i\le c_1$). Hence after taking out rows $x<i\le c_1$, $c_j$ is still at least $b_j+1$. Furthermore, taking out these rows does not affect any other rows, so we can use the same analysis as in case $1$ to conclude that $r_i$ will remain at least $a_i+1$ for all rows not taken out. By the inductive hypothesis, we can place $1$'s into the remaining array as desired.

Sorry, what I wrote is completely wrong... if $a_i$ ever becomes zero, then we need to take row $i$ out, which screws everything up. I really need to get better at combo...

Consider the bipartite graph corresponding to the table and put the numbers on corresponding edges. In an arbitrary graph we call an edge with non-integer number on it temporary and also call the subgraph consisting of the temporary edges temporary. We apply series of operations to numbers on edges so that operations have three propeties (*): 1.If the number on an edge before and after an operation is $x$ and $y$ we have $\lfloor x \rfloor \le y \le \lceil x \rceil$ 2. At least one non-integer number becomes integer or equivalently number of temporary edges decrease. 3.Sum of numbers on neighboring edges of any vertex become unchanged. It is not hard to see that by these properties the procedure will end and at last we will have the desired numbers. Procedure is as follows(**):Suppose we have a bipartite graph $G$ so that sum of numbers on neighboring edges of any vertex is an integer. Call its temporary graph $H$.The degree of any vertex in $H$ can't be $1$. If all degrees are zero we stop and we are done. If not ,we will have a cycle in $H$ .let $x_{1},...,x_{2k}$ be numbers on the cycle's edges. let $f(x)=min{\{ |x-\lfloor x \rfloor|,|x-\lceil x \rceil| \} }$ and $\varepsilon=min { \{ f(x_{1}),...,f(x_{2k}) \} }$. Now we shift these numbers by $\varepsilon$ so that (*) hold.Step is done and we goto (**) again. Is it right?

Again graph theory comes to the rescue. I will slightly rearrange your argument, for increased clarity. You consider the complete bipartite graph $G$ of vertices $R \cup C$, where the edge between a row in $R$ and a column in $C$ is labeled by the number filling their intersecting cell. By eliminating the edges labeled with integer values, you obtain your temporary subgraph $H$. No vertex $v$ in $H$ may have degree $1$, since that would contradict the sum of the labels of the edges incident with $v$ being an integer. Also eliminate from $H$ all isolated vertices (of degree zero), if any. Since now all degrees of the vertices in $H$ are at least $2$, $H$ will contain a cycle; since $H$ remains bipartite, the cycle is of even length. You define your value $\varepsilon > 0$ (no edge in $H$ is labeled with an integer). Now alternately shift the values of the labels by $\pm \varepsilon$, starting with the one realizing the minimum represented by $\varepsilon$ (for which the label now will become integer). This ensures that all labels remain within the floor and the ceiling of their original values, and moreover, that the sums of the labels of the edges incident with any vertex stay integer, since exactly two labels are affected for any row or column participating in the cycle, and since those edges are adjacent, the effect of the alternating shift cancels (or no labels are affected for the rows and columns not participating in the cycle). Finally, we noticed that at least one edge is now labeled with an integer, which makes that returning to creating a new temporary subgraph $H$ will strictly decrease its number of edges. The process can only stop when $H$ is empty, which is what was required. Congratulations!

Thanks mavropnevma.You filled details I didn't mention:cycle has even length and we must shift alternately and why we don't have degree 1 and why sums become unchanged.I see your proof is more coherent and readable than mine

this problem also can be solved using Hall's theorem

Perhaps I'm missing something, but can't we just do:

Mewto55555 wrote: Now, given that we can fill in a $m \times n$, which satisfies all our conditions, we show we can fill in an $m \times (n+1)$ Sort the columns by sum, with the greatest in position $n+1$. Let column $n+1$ sum to $x$; in column $n+1$ just fill in 1's in the $x$ rows which have greatest row sums. This doesn't work because some of the 1's you fill in could be in squares that you're not allowed to modify (i.e. if a square contains an integer, you cannot do anything with it).

Zhero wrote: Mewto55555 wrote: Now, given that we can fill in a $m \times n$, which satisfies all our conditions, we show we can fill in an $m \times (n+1)$ Sort the columns by sum, with the greatest in position $n+1$. Let column $n+1$ sum to $x$; in column $n+1$ just fill in 1's in the $x$ rows which have greatest row sums. This doesn't work because some of the 1's you fill in could be in squares that you're not allowed to modify (i.e. if a square contains an integer, you cannot do anything with it). Good point, but that's easily fixed; if a row of $m$ has $k$ 0's and there are $n$ columns, then it can sum to at most $n-k-1$ instead of $n-k$; similarly with columns. So, just fill in the others and you reach a situation where you win; all you have to do is slightly modify the inductive hypothesis. EDIT: No, math154 provided a counterexample to troll this line of argument.

Can someone please check this algoritmic solution I doubt the validity. We do the filling greedily. WLOG we assume the rows and columns to be arranged in decreasing order Let the sum of numbers in row $i$ be $N_i$, and those in column $i$ be $M_i$. Firstly look at the table as an $n*n$ matrix. We say that we switch on a number if we change it into least integer the element $x_{ij}$, and we switch of the element if we change into greatest integer. Now the algorithm Initially switch off every element Step 1 Switch on one by one each elements in each row $i$(suppose) starting from column 1 till you reach $N_i$. Step 2 If at any moment switching on $x_{j1}$(remember the rows and columns are arranged in decreasing order) increases the sum more than $M_1$ go to the nearest column where we switch on the elements and continue from step 1.Continue the same for other columns. Claim By the end of the process the desired configuration is reached Suppose the desired configuration is not reached. Now there are two bad things that could happen (1) The row sums are reached before column sums are reached. (2) The column sums are reached before row sums are reached. Suppose (1) happens Note that the sum of rows is same as that of the sum of the columns. That means there must be some numbers in some column $i$ such that the sum of numbers in some column must exceed $M_i$ but this contradicts the algorithm. Suppose (2) happens then similar to the argument above the sum of number in some row must exceed $N_i$ impossible by algorithm. Also since elements are finite the algorithm terminates.

someone who cares to check. The above if correct is a totally new solution.

.................

I don't find anything wrong with the reading nor the solution.

For each square, define its weight to be the minimum distance between it and an integer. (Formally, $w(x) = \min(\{x\}, 1 - \{x\})$ where $\{x\}$ is the fractional part of $x$.) Our goal is to make all squares have weight zero while preserving the row and column sums. Suppose there are $N$ squares with nonzero weight, where $N \ge 1$. Consider the bipartite graph $G$ with rows and columns as vertices, and two vertices (one row and one column) connected by an edge of weight $w$ if the intersection of the row and column has weight $w > 0$. There are $N$ edges in $G$. Notice that it is impossible for a vertex to have degree exactly $1$, as that implies the corresponding row or column has non-integer sum. Thus, each non-isolated vertex has degree at least $2$, implying the existence of a cycle. The graph being bipartite ensures the cycle has even length. Let $w$ be the minimum weight in the cycle. Then by alternating adding and subtracting $w$ to the squares corresponding to edges of the cycle, we preserve the row and column sums. Furthermore, we can choose to start the alternating add/subtract such that an edge with weight $w$ will have weight $0$ after the transformation. Thus, the number of edges (and the number of squares) with nonzero weight decreases by at least $1$, so after finitely many steps we can decrease $N$ to $0$, as desired. Example: the cycle of squares with values 1.5, 2.3, 3.6, 1.8 has edge weights 0.5, 0.3, 0.4, 0.2. The minimum weight is 0.2, attained for the 1.8 square. Now alternate adding/subtracting 0.2 to get 1.3, 2.5, 3.4, 2.0, and 2 is an integer (with 0 weight).

vjdjmathaddict wrote: Can someone please check this algoritmic solution I doubt the validity. We do the filling greedily. WLOG we assume the rows and columns to be arranged in decreasing order Let the sum of numbers in row $i$ be $N_i$, and those in column $i$ be $M_i$. Firstly look at the table as an $n*n$ matrix. We say that we switch on a number if we change it into least integer the element $x_{ij}$, and we switch of the element if we change into greatest integer. Now the algorithm Initially switch off every element Step 1 Switch on one by one each elements in each row $i$(suppose) starting from column 1 till you reach $N_i$. Step 2 If at any moment switching on $x_{j1}$(remember the rows and columns are arranged in decreasing order) increases the sum more than $M_1$ go to the nearest column where we switch on the elements and continue from step 1.Continue the same for other columns. Claim By the end of the process the desired configuration is reached Suppose the desired configuration is not reached. Now there are two bad things that could happen (1) The row sums are reached before column sums are reached. (2) The column sums are reached before row sums are reached. Suppose (1) happens Note that the sum of rows is same as that of the sum of the columns. That means there must be some numbers in some column $i$ such that the sum of numbers in some column must exceed $M_i$ but this contradicts the algorithm. Suppose (2) happens then similar to the argument above the sum of number in some row must exceed $N_i$ impossible by algorithm. Also since elements are finite the algorithm terminates. How do you handle $N_1 = 5, N_2 = 1, N_3 = 0, M_1 = 2, M_2 = 2, M_3 = 2$?

ISL 1998 C1 wrote: A rectangular array of numbers is given. In each row and each column, the sum of all numbers is an integer. Prove that each nonintegral number $x$ in the array can be changed into either $\lceil x\rceil $ or $\lfloor x\rfloor $ so that the row-sums and column-sums remain unchanged. (Note that $\lceil x\rceil $ is the least integer greater than or equal to $x$, while $\lfloor x\rfloor $ is the greatest integer less than or equal to $x$.) Let the array be $m \times n.$ For any given row $\mathcal{R}$, let the elements be $y_i$ for $1 \le i \le n.$ Call the value of $\mathcal{R}$ the number of terms on which we use $\lceil \circ \rceil$ so that the sum of the row remains constant. A simple calculation shows that $\text{value} (\mathcal{R})=\{y_1\}+\cdots+\{y_n\} \in \mathbb{N}$. From this note that the $0<\text{value}<n.$ The only issue now is to choose which elements in each row so that the choice corresponds with the columns. To see this, draw a bipartite graph with the rows and the columns as the two parts. Label each vertex by its value. Consider the simple algorithm of choosing the first point (i.e. the left most point) from the first part, then connecting it to as many vertices as its value. This is possible since $\text{value}<n=\text{no. of vertices in the second part}.$ For instance: [asy][asy] unitsize(3); int y=20; //y-gap between parts int x=15; //x-gap between dots draw((0,y)--(0,1), arrow=Arrow(HookHead), blue); draw((0,y)--(x,1), arrow=Arrow(HookHead), blue); draw(circle((0,0),1)); label("$2$",(0,-5)); fill(circle((0,0),1)); draw(circle((x,0),1)); label("$1$",(x,-5)); fill(circle((x,0),1)); draw(circle((2x,0),1)); label("$3$",(2x,-5)); fill(circle((2x,0),1)); draw(circle((0,y),1)); label("$2$",(0,5+y)); fill(circle((0,y),1)); draw(circle((x,y),1)); label("$2$",(x,5+y)); fill(circle((x,y),1)); draw(circle((2x,y),1)); label("$1$",(2x,5+y)); fill(circle((2x,y),1)); draw(circle((3x,y),1)); label("$1$",(3x,5+y)); fill(circle((3x,y),1)); [/asy][/asy] Repeat this procedure for the points in the first part moving from left to right. If the value of a vertex from the second part is achieved at some point, delete it. Keep following this algorithm. [asy][asy] unitsize(3); int y=20; //y-gap between parts int x=15; //x-gap between dots draw((0,y)--(0,1), arrow=Arrow(HookHead), blue); draw((0,y)--(x,1), arrow=Arrow(HookHead), blue); draw((x,y)--(0,1), arrow=Arrow(HookHead), red); draw((x,y)--(2x,1), arrow=Arrow(HookHead), red); draw((2x,y)--(2x,1), arrow=Arrow(HookHead), magenta); draw((3x,y)--(2x,1), arrow=Arrow(HookHead), purple); draw(circle((0,0),1)); label("$2$",(0,-5)); fill(circle((0,0),1)); draw(circle((x,0),1)); label("$1$",(x,-5)); fill(circle((x,0),1)); draw(circle((2x,0),1)); label("$3$",(2x,-5)); fill(circle((2x,0),1)); draw(circle((0,y),1)); label("$2$",(0,5+y)); fill(circle((0,y),1)); draw(circle((x,y),1)); label("$2$",(x,5+y)); fill(circle((x,y),1)); draw(circle((2x,y),1)); label("$1$",(2x,5+y)); fill(circle((2x,y),1)); draw(circle((3x,y),1)); label("$1$",(3x,5+y)); fill(circle((3x,y),1)); [/asy][/asy] This algorithm would stop with each vertex satisfied since the sum of the values of the two parts are equal. Hence we are done. $\square$

Here's an approach that doesn't use graph theory, but the machinery of linear algebra instead. Assume for the sake of contradiction that we've done the maximal number of rounding we can do, and we still have non-integer terms. Then, there are at least two of them in each row/column. Replace these by variables. Now, write for each row/column an equation relating the unknowns and numbers in the grid to the integer sum. This gives a system of $m+n$ equations. However, we know that there is at least one redundant equation in here as the sum of the $m$ row equations is equal to the sum of the $n$ column equations. Thus, we have strictly less than $m+n$ linearly independent equations. However, we have at least $\max{(2x,2y)}\ge x+y>x+y-1$ variables, so our system has nontrivial null space. In particular, some of our variables are free, so we can swap one of them for the nearest integer, contradicting our maximality assumption.

Wizard_32 wrote: ISL 1998 C1 wrote: A rectangular array of numbers is given. In each row and each column, the sum of all numbers is an integer. Prove that each nonintegral number $x$ in the array can be changed into either $\lceil x\rceil $ or $\lfloor x\rfloor $ so that the row-sums and column-sums remain unchanged. (Note that $\lceil x\rceil $ is the least integer greater than or equal to $x$, while $\lfloor x\rfloor $ is the greatest integer less than or equal to $x$.) Let the array be $m \times n.$ For any given row $\mathcal{R}$, let the elements be $y_i$ for $1 \le i \le n.$ Call the value of $\mathcal{R}$ the number of terms on which we use $\lceil \circ \rceil$ so that the sum of the row remains constant. A simple calculation shows that $\text{value} (\mathcal{R})=\{y_1\}+\cdots+\{y_n\} \in \mathbb{N}$. From this note that the $0<\text{value}<n.$ The only issue now is to choose which elements in each row so that the choice corresponds with the columns. To see this, draw a bipartite graph with the rows and the columns as the two parts. Label each vertex by its value. Consider the simple algorithm of choosing the first point (i.e. the left most point) from the first part, then connecting it to as many vertices as its value. This is possible since $\text{value}<n=\text{no. of vertices in the second part}.$ For instance: [asy][asy] unitsize(3); int y=20; //y-gap between parts int x=15; //x-gap between dots draw((0,y)--(0,1), arrow=Arrow(HookHead), blue); draw((0,y)--(x,1), arrow=Arrow(HookHead), blue); draw(circle((0,0),1)); label("$2$",(0,-5)); fill(circle((0,0),1)); draw(circle((x,0),1)); label("$1$",(x,-5)); fill(circle((x,0),1)); draw(circle((2x,0),1)); label("$3$",(2x,-5)); fill(circle((2x,0),1)); draw(circle((0,y),1)); label("$2$",(0,5+y)); fill(circle((0,y),1)); draw(circle((x,y),1)); label("$2$",(x,5+y)); fill(circle((x,y),1)); draw(circle((2x,y),1)); label("$1$",(2x,5+y)); fill(circle((2x,y),1)); draw(circle((3x,y),1)); label("$1$",(3x,5+y)); fill(circle((3x,y),1)); [/asy][/asy] Repeat this procedure for the points in the first part moving from left to right. If the value of a vertex from the second part is achieved at some point, delete it. Keep following this algorithm. [asy][asy] unitsize(3); int y=20; //y-gap between parts int x=15; //x-gap between dots draw((0,y)--(0,1), arrow=Arrow(HookHead), blue); draw((0,y)--(x,1), arrow=Arrow(HookHead), blue); draw((x,y)--(0,1), arrow=Arrow(HookHead), red); draw((x,y)--(2x,1), arrow=Arrow(HookHead), red); draw((2x,y)--(2x,1), arrow=Arrow(HookHead), magenta); draw((3x,y)--(2x,1), arrow=Arrow(HookHead), purple); draw(circle((0,0),1)); label("$2$",(0,-5)); fill(circle((0,0),1)); draw(circle((x,0),1)); label("$1$",(x,-5)); fill(circle((x,0),1)); draw(circle((2x,0),1)); label("$3$",(2x,-5)); fill(circle((2x,0),1)); draw(circle((0,y),1)); label("$2$",(0,5+y)); fill(circle((0,y),1)); draw(circle((x,y),1)); label("$2$",(x,5+y)); fill(circle((x,y),1)); draw(circle((2x,y),1)); label("$1$",(2x,5+y)); fill(circle((2x,y),1)); draw(circle((3x,y),1)); label("$1$",(3x,5+y)); fill(circle((3x,y),1)); [/asy][/asy] This algorithm would stop with each vertex satisfied since the sum of the values of the two parts are equal. Hence we are done. $\square$ From this solution it is clear to me that the algorithm will stop.But then in which cells will we apply the ceiling function???

Sorry, but bumping it to get an answer of my above question

how the heck did you do those asymptote codes

[asy] unitsize(3); int y=20; //y-gap between parts int x=15; //x-gap between dots draw((0,y)--(0,1), arrow=Arrow(HookHead), blue); draw((0,y)--(x,1), arrow=Arrow(HookHead), blue); draw((x,y)--(0,1), arrow=Arrow(HookHead), red); draw((x,y)--(2x,1), arrow=Arrow(HookHead), red); draw((2x,y)--(2x,1), arrow=Arrow(HookHead), magenta); draw((3x,y)--(2x,1), arrow=Arrow(HookHead), purple); draw(circle((0,0),1)); label("$2$",(0,-5)); fill(circle((0,0),1)); draw(circle((x,0),1)); label("$1$",(x,-5)); fill(circle((x,0),1)); draw(circle((2x,0),1)); label("$3$",(2x,-5)); fill(circle((2x,0),1)); draw(circle((0,y),1)); label("$2$",(0,5+y)); fill(circle((0,y),1)); draw(circle((x,y),1)); label("$2$",(x,5+y)); fill(circle((x,y),1)); draw(circle((2x,y),1)); label("$1$",(2x,5+y)); fill(circle((2x,y),1)); draw(circle((3x,y),1)); label("$1$",(3x,5+y)); fill(circle((3x,y),1));

rachelshi wrote: [asy][asy] unitsize(3); int y=20; //y-gap between parts int x=15; //x-gap between dots draw((0,y)--(0,1), arrow=Arrow(HookHead), blue); draw((0,y)--(x,1), arrow=Arrow(HookHead), blue); draw((x,y)--(0,1), arrow=Arrow(HookHead), red); draw((x,y)--(2x,1), arrow=Arrow(HookHead), red); draw((2x,y)--(2x,1), arrow=Arrow(HookHead), magenta); draw((3x,y)--(2x,1), arrow=Arrow(HookHead), purple); draw(circle((0,0),1)); label("$2$",(0,-5)); fill(circle((0,0),1)); draw(circle((x,0),1)); label("$1$",(x,-5)); fill(circle((x,0),1)); draw(circle((2x,0),1)); label("$3$",(2x,-5)); fill(circle((2x,0),1)); draw(circle((0,y),1)); label("$2$",(0,5+y)); fill(circle((0,y),1)); draw(circle((x,y),1)); label("$2$",(x,5+y)); fill(circle((x,y),1)); draw(circle((2x,y),1)); label("$1$",(2x,5+y)); fill(circle((2x,y),1)); draw(circle((3x,y),1)); label("$1$",(3x,5+y)); fill(circle((3x,y),1)); [/asy][/asy] FTFY

Rough and sloppy solution for storage, which I think is similar to OldMath's solution. Solution. Consider the bipartite graph with a vertex for each row and column in the graph, and edges weighted by the corresponding array entry. Remove all edges with integers weights. Repeat the following procedure: Consider some cycle in the graph (exists by Euler as vertices have even degree). Choose the edge $e$ in this cycle whose weight is closest to an integer, with a distance $x$. Go around each edge in the cycle, alternating between adding and subtracting $x$. Do this such that $e$'s weight becomes an integer. This leaves the sum of edge-weights at each vertex the same. After doing this, for each edge that has become an integer, we apply either the floor or ceiling function to the corresponding array entry, and then remove the edge from the graph. Since this procedure removes edges, we can repeat until there is no edges left, at which point there will be no non-integer elements in the array, and the final row and column sums will stay the same (since we kept the sum of edge-weights at each vertex constant). Remark. I had a look in the IMO Compendium after doing this problem, and I think the proof they use there is the same as this proof, modulo graph theory.

Let the distance between a square and an integer be $\Theta$. Let $\Theta_{\text{min}}$ be defined as the strength of a square. The main goal of the problem is to make the strength of all the squares equal to $0$, this however needs to be done while preserving the sums of the row and the coloumns. Now suppose that there are $X$ squares that have non-zero strength. Where we have $X \ge 1$. Now we employ graph theory to solve the problem. Consider a bipartite graph $\Omega$ where we have the rows and coloumns as vertices and we have one row and one coloumn that is connected by an edge having strength $\nabla$. If the intersection of the row and column have strength of $\nabla > 0$. Thus there are $X$ edges in $\Omega$. Observe the fact that it is impossible to have a vertex of degree $1$, if this happens, then it implies that the corresponding row or coloumn sum is not an integer. This implies the existense of a cycle. Since $\Omega$ is bipartite, the length of the cycle will be even. Let $\nabla$ be the minimum strength of the cycle, then we do alternate adding and subtracting with $\nabla$ to the squares with corresponding edges of the cycle. This way we preserve the row and the coloumn sum. We can also choose to start the alternation addition or subtraction in such a way that an edge having a strength of $\nabla$ will be having a strength of $0$ after the process. Hence the number of edges having strength $\nabla > 0$ decreases at least by $1$. Hence after a finite number of steps we can decrease $X$ to $0$, which is what the problem desired for. $\blacksquare$

Let a "nonintegral cell" be a cell with a nonintegral number. We will use induction on $n$, the number of nonintegral cells. The base case is when $n=0$. In this case, doing nothing satisfies the condition. Note that every nonintegral cell has another nonintegral cell in the same row and another in the same column. Otherwise, the row and column sum wouldn't be an integer. If $n>0$, let $x_1$ be some nonintegral cell. For odd $i>1$, let $x_i$ be a nonintegral cell in the same row as $x_{i-1}$ and for even $i>1$, let $x_i$ be a nonintegral cell in the same column as $x_{i-1}$ such that $x_i\neq x_{i-1}$. We know this is possible because every nonintegral cell has another nonintegral cell in the same row and another in the same column. Let $k$ be the smallest value of $k$ such that there exists $j< k$ such that either of the following are true: -$k$ is even, and $x_k$ and $x_j$ are in the same row (we know $x_k\neq x_j$, since if they were equal then $x_{k-1}$ would be in the same column as $x_j$, satisfying the condition below, a contradiction) -$k$ is odd, and $x_k$ and $x_j$ are in the same column ($x_k\neq x_j$ by the same logic as above) Note this must be possible since there are a finite number of rows and columns. Moreover, after $k$ has been chosen, let $j$ be the highest value less than $k$ such that one of the above is true. Then, let $a_j,\ldots, a_k$ be a finite sequence of cells with $a_j,\ldots, a_k=x_j,\ldots, x_k$. We claim that in each row and column, there is either $1$ cell $a_i$ with $i$ odd and $1$ cell $a_i$ with $i$ even or there is no cell $a_i$. First we will show that each row with any cell $a_i$ has a cell of each parity. To do this, we will first show that $j$ and $k$ have different parity. Assume $k$ is even. Assume towards a contradiction that $j$ is even. Then, $a_k$ and $a_j$ are in the same row. However, $a_{j+1}$ is also in this row, so $j$ is not maximal, a contradiction. By similar logic, $k$ and $j$ cannot both be odd. WLOG, assume $k$ is even and $j$ is odd. Then, they are in the same row. In other rows, if $i\neq k, j$, then either $a_{i-1}$ or $a_{i+1}$ must be in the same row as $a_i$. For columns, for odd $i$, $a_{i+1}$ is in the same column as $a_i$ and $a_{i-1}$ is in the same column as $a_i$ for even $i$. We will now show that no row or column has more than two of the $a_i$. Assume towards a contradiction that $x$ and $y$ are both even and $a_x$ and $a_y$ are in the same column with $y>x$. Then, $a_{y-1}$ is also in this column, and $y-1$ is odd. Also, $x<y-1$, $y-1$ is odd, and $a_x$ and $a_{y-1}$ are in the same column. Therefore, $k$ is not minimal, a contradiction. Assume towards a contradiction that $x$ and $y$ are both odd and $a_x$ and $a_y$ are in the same column with $y>x$. Then, $a_{x+1}$ is also in this column. So, $y>x+1$, $y$ is odd, and $a_y$ and $a_{x+1}$ are in the same column. If $y\neq k$, then $k$ is not minimal, a contradiction. If $y=k$, then $x+1>j$, so $j$ is not maximal, a contradiction. Apply the same logic to rows, and we find that any row or column with any of the $a_i$ has one $a_i$ with $i$ even and one $a_i$ with $i$ odd. Let $x\in\mathbb{R}$ such that $x+a_i$ is an integer for some $i$ and $|x|$ is minimized. Add $x$ to all of the cells $a_m$ with $m\equiv i\pmod{2}$. Subtract $x$ from all of the cells $a_m$ with $m\not\equiv i\pmod{2}$. Because every row and column has the same number of odd- and even-indexed cells from $a_j,\ldots,a_k$, this will not affect row and column cells. Since $|x|$ is minimal, this will not affect the floor or ceiling of any of the cells that don't become integers. So, at least 1 non-integral cell will become an integer. So, by induction, we can take the floor or ceiling of every other non-integral cell such that the row and column sums stay the same. tldr: Because each non integral cell has another non integral cell in the same row and column, we can make a "cycle" of non integral cells such that we can add some constant to half of them and subtract some constant from the other half such that the row and column sums stay the same. Then, we can use induction to turn all the cells into integers.

Assume WLOG that every number in the grid is in the interval $[0,1)$. We will create an algorithm that works on grids that aren't only integers yet that changes the grid such that each number in the grid is still in the interval $[0,1]$, each row and column sum is unchanged, no cell that is already an integer is modified, and the number of integers in the grid strictly increases. By repeatedly applying the algorithm, the number of integers in the grid will be a strictly increasing monovariant until the entire grid is filled with only $0$s and $1$s where the cells that were previously $0$s stay $0$s, when we will be clearly done. For the algorithm, first pick any noninteger in the grid and let Catloe be on it. Note that if a row or column has at least one noninteger, it must have at least two nonintegers. So, select another noninteger in the row, and let Catloe walk to it in a straight line. Now, select another noninteger 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 nonintegers. Let the turns, in order, be $t_1,t_2,\dots,t_n$. Note that $n$ has to be even. Define a number's awaness to be its distance to the closer of $0$ or $1$. Choose the $t_i$ with the lowest awaness(ties can be broken arbitrarily). Assume WLOG that it is closer to $0$. Then we reduce the cell $t_i$ to $0$, and go around the loop and alternate increasing and decreasing each cell by $t_i$(so increase $t_{i+1}$ by $t_i$, decrease $t_{i+2}$ by $t_i$, etc, increase $t_{i-1}$ by $t_i$). Clearly, nothing gets out of bounds, no integer is modified, the number of total integers is increased, and the row and column sums are preserved(for every pair in a row/column, one is decreased while the other is increased). Therefore, our algorithm works, and we are done.

Quite a beautiful problem, actually. If there are no non-integers then we are done. Otherwise, we claim that there exists squares $s_1,s_2,\dots,s_{2k}$ such that $s_0=s_{2k},s_{1}=s_{2k+1}$, and for $0\le i\le 2k-1$, The numbers written in each of these squares is non-integer. The squares $s_{i}$ and $s_{i+1}$ are either on the same row, or the same column. The squares $s_{i}$ and $s_{i+2}$ are neither on the same row, nor the same column. The squares $s_1,s_2,\dots,s_{2k}$ are pairwise distinct. First, we note that each row and each column which does contain non-integers has at least two of them. If one only has one non-integer, then the sum must be non-integer, which is a contradiction. Using that fact, we may start from any non-integer square $s$, and then move onto a non-integer square of the same row, which must exist. Then, we may move onto a non-integer square of the saw column, which also must exist. Repeating this, we must either eventually reach a square we've reached before. Suppose the first time this happens, we reached $s_1$ for the second time. Now, let the path we took land on the squares $s_1,s_2,\dots,s_{2k},s_1.$ Connect squares with adjacent indices $\pmod {2k}$. Note that any such must land on an even number of squares, because at each square there is one horizontal and one vertical segment, so there are equal amounts of horizontal and vertical segments, and therefore an even number of segments total, meaning that even number of squares. Now, none of the squares $s_1,s_2,\dots,s_{2k}$ are the same because that violates the fact that the second $s_1$ is the first time a square is stepped on twice. Our path's algorithm dictates that $\text{(i)}$, $\text{(ii)}$ and $\text{(iii)}$ are followed. Therefore, our claim is proven. Now, of these squares $s_1,s_2,\dots,s_{2k}$ and selected one of the ones that is closest to an integer, WLOG let it be $s_1$. Now, move this to the closest integer, move $s_{i+1}$ by the same amount that $s_i$ was moved, but in the opposite direction. One can check that each row's and column's sum is preserved, and there is at least one more integer square. Repeat this until there are no more non-integer squares, at which point we are done.

Let there be $m$ rows and $n$ columns. Let each of the elements in the array be in the range $(0,1]$. We now have the much simpler problem of assigning $0,1$ to elements of an array such that the rows and columns sum to known target quantities. In addition, some of the elements are forced to be $1$(namely the integer ones). Now we just take the following greedy algorithm, take the column whose target sum $k$ is least, then we are forced that the total target sum is $kn$, so by pigeonhole there must exist at least $k$ rows which have nonzero target sum. Observe that the fixed $1$ elements do not matter because we can just take them and then we will still have enough good rows left. After this procedure is done, literally just delete the column and adjust the target sums for the rows accordingly. Repeating finishes.

Notice that we can subtract the floor parts of each element, and simplify the task to the following: - We are given an $m \times n$ grid - We have row totals $a_1, a_2, \dots, a_m$ where all $0 \leq a_i < n$ - We have column totals $b_1, b_2, \dots, b_n$ where all $0 \leq b_i < m$ - Prove that we can put ones and zeroes to satisfy the above conditions. Now, we can prove the claim by induction. The base case when $m = 1$ is trivial, so now we will solve the problem for $m+1$ rows where the problem for $m$ rows is true. First, note that if any of the columns has a total sum $b_i = 0$, then we can just delete the column since we know it must be all zeroes anyways. Pick the row that has the largest total $a_i$. Note that $ma_i \geq S$, where $S$ is the total number of $1$'s needed. This implies that $a_i$ is at least the number of $b_j$'s that are equal to $m-1$. Then, this means that if we put the $1$'s in the $i$th row such that the $1$'s are placed in the columns with the greatest totals required (the columns with the greatest $b_j$), then deleting that row (since we've finished filling it) leaves us with a problem satisfying the constraints but for the $m \times n$ case. This proves the induction. $\blacksquare$

First, smooth so that all numbers have integer part $0$. Then, delete any rows or columns that have all $0$s, to obtain a new $m \times n$ grid. Upon imposing a coordinate system, the grid can be understood as the graph $K_{m, n}$, where edges of the graph that have weight $0$ are deleted. Since this graph $G$ is bipartite, there exists a cycle of even length. Let $e$ denote edge whose weight is closest to $0$ or $1$, and let $w$ denote it's weight. Let $w' = \min(w, 1-w)$. Then starting with $e$, alternate between adding and subtracting $w'$ to the weights in the cycle, where the value of $w$ is changed to one of $0$ and $1$, and after that delete all integral edges. Do this for all cycles. Repeat this process until all weights are made either $0$ or $1$. Clearly, the total sum in each row and column is preserved, and all numbers are changed to $0$ or $1$. Thus we are done.

oops what am i doing somehow no solve oops motivation is like to change one thing, see how it changes another thing, and then just keep going like that and this just solves smh my head though it is essentially the same concept as JMO 2024/2