IMO ShortList 1998, combinatorics theory problem 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

orl

3647 posts

orl

#1 h Oct 22, 2004, 3:22 PM • 8 Y

Y by Wizard_32, Adventure10, megarnie, Mango247, kiyoras_2001, and 3 other users

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$ .)

Attachments:

This post has been edited 1 time. Last edited by orl, Oct 23, 2004, 12:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

orl

3647 posts

orl

#2 h Oct 22, 2004, 3:23 PM • 3 Y

Y by Adventure10, megarnie, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dgreenb801

1896 posts

dgreenb801

#3 h May 25, 2009, 1:09 AM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

No Reason

114 posts

No Reason

#4 h May 27, 2009, 10:33 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dgreenb801

1896 posts

dgreenb801

#5 h Jun 2, 2009, 4:14 AM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JBL

16123 posts

JBL

#6 h Jun 2, 2009, 11:50 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dgreenb801

1896 posts

dgreenb801

#7 h Jun 2, 2009, 12:23 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MellowMelon

5850 posts

MellowMelon

#8 h Jun 2, 2009, 9:56 PM • 4 Y

Y by AlastorMoody, Adventure10, Mango247, and 1 other user

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CatalystOfNostalgia

1479 posts

CatalystOfNostalgia

#9 h Jun 5, 2009, 12:36 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MellowMelon

5850 posts

MellowMelon

#10 h Jun 5, 2009, 1:48 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CatalystOfNostalgia

1479 posts

CatalystOfNostalgia

#11 h Jun 5, 2009, 6:36 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CatalystOfNostalgia

1479 posts

CatalystOfNostalgia

#12 h Jun 5, 2009, 7:54 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math154

4302 posts

math154

#13 h Jul 13, 2010, 5:33 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math154

4302 posts

math154

#14 h Jul 23, 2010, 2:42 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OldMath

23 posts

OldMath

#15 h Aug 28, 2010, 7:28 PM • 6 Y

Y by Adventure10, Mango247, Stuffybear, and 3 other users

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mavropnevma

15142 posts

mavropnevma

#16 h Aug 28, 2010, 8:48 PM • 8 Y

Y by InCtrl, Adventure10, Mango247, Stuffybear, and 4 other users

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!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OldMath

23 posts

OldMath

#17 h Aug 29, 2010, 8:25 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Dumel

190 posts

Dumel

#18 h Aug 29, 2010, 3:26 PM • 2 Y

Y by Adventure10, Mango247

this problem also can be solved using Hall's theorem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mewto55555

4210 posts

Mewto55555

#19 h Sep 17, 2011, 10:08 PM • 2 Y

Y by Adventure10, Mango247

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

Click to reveal hidden text

An example of how to do this

Consider like:

? ? ? ? ? 4
? ? ? ? ? 2
? ? ? ? ? 1
? ? ? ? ? 3
2 2 2 1 3

Now sort the rows/columns in increasing order.

? ? ? ? ? 1
? ? ? ? ? 2
? ? ? ? ? 3
? ? ? ? ? 4
1 2 2 2 3

Fill in the columns from right to left according to which sum is the largest remaining just like our induction:

? ? ? ? 0 1
? ? ? ? 1 2
? ? ? ? 1 3
? ? ? ? 1 4
1 2 2 2 3

This is equivalent to:

? ? ? ?  1
? ? ? ?  1
? ? ? ?  2
? ? ? ?  3
1 2 2 2

Again and again to get:

or

? ? 1
? ? 1
? ? 0
? ? 1
1 2

Eliminate the 0 for

? ? 1
? ? 1
? ? 1
1 2

Now the bottom row to get us to a 2x2:

? ? 1
? ? 1
1 1

which is easy:

1 0 1
0 1 1
1 1

We can now build back up to get:

and then rearrange to

which clearly works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Zhero

2043 posts

Zhero

#20 h Sep 18, 2011, 12:36 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mewto55555

4210 posts

Mewto55555

#21 h Sep 18, 2011, 12:43 AM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

vjdjmathaddict

502 posts

vjdjmathaddict

#22 h Jul 9, 2017, 2:36 PM • 1 Y

Y by Adventure10

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.

This post has been edited 8 times. Last edited by vjdjmathaddict, Jul 9, 2017, 6:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

vjdjmathaddict

502 posts

vjdjmathaddict

#28 h Jul 10, 2017, 12:07 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mocktheta

189 posts

Mocktheta

#29 h Jul 10, 2017, 2:34 PM • 1 Y

Y by Adventure10

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

This post has been edited 1 time. Last edited by Mocktheta, Jul 11, 2017, 12:06 PM
Reason: Mistake on my part

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

vjdjmathaddict

502 posts

vjdjmathaddict

#30 h Jul 10, 2017, 3:41 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

suli

1498 posts

suli

#32 h Feb 17, 2018, 12:29 AM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

suli

1498 posts

suli

#33 h Feb 17, 2018, 12:54 AM • 2 Y

Y by Adventure10, Mango247

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$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Wizard_32

1566 posts

Wizard_32

#34 h Apr 8, 2019, 4:59 AM • 5 Y

Y by e_plus_pi, AlastorMoody, Adventure10, Mango247, math_comb01

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] 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]$
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] 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]$
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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

InCtrl

871 posts

InCtrl

#35 h Aug 15, 2019, 3:59 AM • 2 Y

Y by Adventure10, Mango247

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.

This post has been edited 1 time. Last edited by InCtrl, Aug 15, 2019, 4:00 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Cvirus213

52 posts

Cvirus213

#36 h Oct 10, 2020, 8:40 PM

Y by

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] 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]$
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] 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]$
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???

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Cvirus213

52 posts

Cvirus213

#37 h Oct 13, 2020, 10:31 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rachelshi

501 posts

rachelshi

#38 h Oct 13, 2020, 11:09 PM

Y by

how the heck did you do those asymptote codes

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rachelshi

501 posts

rachelshi

#39 h Oct 13, 2020, 11:10 PM

Y by

[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));

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ilovepizza2020

12154 posts

ilovepizza2020

#40 h Oct 13, 2020, 11:15 PM

Y by

rachelshi wrote:

$[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]$

FTFY

This post has been edited 1 time. Last edited by ilovepizza2020, Oct 13, 2020, 11:15 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

circlethm

98 posts

circlethm

#41 h Jul 25, 2021, 2:00 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Bratin_Dasgupta

598 posts

Bratin_Dasgupta

#42 h Mar 11, 2022, 4:05 PM • 1 Y

Y by Bgmi

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomehuman

499 posts

awesomehuman

#43 h Apr 9, 2022, 5:29 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cj13609517288

1922 posts

cj13609517288

#44 h Nov 25, 2022, 6:59 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1725 posts

awesomeming327.

#45 h Nov 30, 2022, 4:54 AM • 1 Y

Y by sman96

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.

This post has been edited 1 time. Last edited by awesomeming327., Nov 30, 2022, 4:54 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1279 posts

ezpotd

#46 h Aug 31, 2023, 3:19 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

abeot

128 posts

abeot

#47 h Nov 6, 2023, 2:23 AM • 1 Y

Y by centslordm

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$

This post has been edited 1 time. Last edited by abeot, Nov 6, 2023, 2:28 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Leo.Euler

577 posts

Leo.Euler

#48 h Feb 7, 2024, 6:49 AM

Y by

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.

This post has been edited 1 time. Last edited by Leo.Euler, Feb 7, 2024, 6:52 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7585 posts

asdf334

#49 h Mar 28, 2024, 2:39 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Davdav1232

44 posts

Davdav1232

#50 h Apr 19, 2025, 4:43 PM

Y by

Assume all the numbers are between 0 and 1 (if an entry is an integer we assume it is 0). Now assume the sum of the squares of the \emph{free} entries (meaning the non-zero ones) is maximal. We assume they are all variables and satisfy a system of equations, one for each sum of row/column.

If we look at $\mathbb{R}^k$ (where $k$ is the number of free variables) and place the entries as the coordinates, we have the intersection of the unit cube in $\mathbb{R}^k$ , which is compact, and some planes corresponding to the equations on the variables, which are also closed and bounded subsets of $\mathbb{R}^k$ , hence the set is compact. Since the sum-of-squares function is bounded and continuous, it attains a maximum on this set.

Assume we have a maximal configuration on the original rectangular board. We claim all entries are now integers, and that will complete the proof.

Assume there is a non-integer entry. Note that every non-integer has another non-integer in its row and column, so we can go to another non-integer in the same row, then column, and so on, until we close a loop. Clearly, we can construct such a loop with an even number of edges.

Now, add $t$ to half of the entries in the loop (such that no two are adjacent), and subtract $t$ from the other half. We can pick $t$ small enough in absolute value to ensure all variables remain between 0 and 1, and we can choose the sign of $t$ to make the sum of squares increase.

This implies the configuration was not maximal, contradicting our assumption. Therefore, all entries must be integers.

This post has been edited 2 times. Last edited by Davdav1232, Apr 19, 2025, 4:50 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

YaoAOPS

1541 posts

YaoAOPS

#51 h Apr 23, 2025, 2:53 PM

Y by

WLOG add integers to each nonintegral $x$ such that $x \in (0, 1)$ . Then note that if there is one non-integral $x$ in a row / column, there must exist another. This allows us to generate cycles $x_1, x_2, \dots, x_{2k}$ of nonintegral numbers where $x_{2i}, x_{2i+1}$ are in the same row and $x_{2i+1}, x_{2i+2}$ are in the same column with cyclic indices. To do this, take any arbitrary starting $x_i$ and repeatedly take arbitrary pre-existing examples unless we end up with three elements in the same row / column, in which case we start from the second least indexed element in the column and go to the current one. Then we increase all odd indexed $x_{2i+1}$ and decrease all even indexed $x_{2i}$ until at least one number in the cycle becomes an integer, which is equal to the floor or ceiling of itself originally.

Repeat this until all $x$ are integers to suffice.

Z K Y