Stay ahead of learning milestones! Enroll in a class over the summer!

G
Topic
First Poster
Last Poster
k a May Highlights and 2025 AoPS Online Class Information
jlacosta   0
Yesterday at 11:16 PM
May is an exciting month! National MATHCOUNTS is the second week of May in Washington D.C. and our Founder, Richard Rusczyk will be presenting a seminar, Preparing Strong Math Students for College and Careers, on May 11th.

Are you interested in working towards MATHCOUNTS and don’t know where to start? We have you covered! If you have taken Prealgebra, then you are ready for MATHCOUNTS/AMC 8 Basics. Already aiming for State or National MATHCOUNTS and harder AMC 8 problems? Then our MATHCOUNTS/AMC 8 Advanced course is for you.

Summer camps are starting next month at the Virtual Campus in math and language arts that are 2 - to 4 - weeks in duration. Spaces are still available - don’t miss your chance to have an enriching summer experience. There are middle and high school competition math camps as well as Math Beasts camps that review key topics coupled with fun explorations covering areas such as graph theory (Math Beasts Camp 6), cryptography (Math Beasts Camp 7-8), and topology (Math Beasts Camp 8-9)!

Be sure to mark your calendars for the following upcoming events:
[list][*]May 9th, 4:30pm PT/7:30pm ET, Casework 2: Overwhelming Evidence — A Text Adventure, a game where participants will work together to navigate the map, solve puzzles, and win! All are welcome.
[*]May 19th, 4:30pm PT/7:30pm ET, What's Next After Beast Academy?, designed for students finishing Beast Academy and ready for Prealgebra 1.
[*]May 20th, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 1 Math Jam, Problems 1 to 4, join the Canada/USA Mathcamp staff for this exciting Math Jam, where they discuss solutions to Problems 1 to 4 of the 2025 Mathcamp Qualifying Quiz!
[*]May 21st, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 2 Math Jam, Problems 5 and 6, Canada/USA Mathcamp staff will discuss solutions to Problems 5 and 6 of the 2025 Mathcamp Qualifying Quiz![/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

Calculus
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

AIME Problem Series A
Thursday, May 22 - Jul 31

AIME Problem Series B
Sunday, Jun 22 - Sep 21

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Yesterday at 11:16 PM
0 replies
Digits permutations all not divisible by 7
NicoN9   0
19 minutes ago
Source: Japan Junior MO Preliminary 2020 P12
Find the number of possible quadruples $(a, b, c, d)$ with $1\le a<b<c<d\le 9$, satisfies the following property:

$24$ integers obtained by arranging four digits $a, b, c, d$ in some order, are all not divisible by $7$.
0 replies
NicoN9
19 minutes ago
0 replies
8 times 8 grid and 64 coins
NicoN9   0
21 minutes ago
Source: Japan Junior MO Preliminary 2020 P11
There are $8\times 8$ grid, and in each cell, there is a coin with one side white, and other side black. We start by all coin facing white. Alice and Bob executes the following operation:

First, Alice choose $8$ pairwise distinct cells, and turn over all of the coins in those cells. Next, Bob chooses one row or column, and turn over all of the coins in that row, or column.

Find the maximum possible positive integer $k$ with the following property:

No matter how Bob plays, Alice can always make $k$ coins facing black, after $2020$ turns.
0 replies
NicoN9
21 minutes ago
0 replies
existence of a circle tangent to AB and AC
NicoN9   0
23 minutes ago
Source: Japan Junior MO Preliminary 2020 P10
Let $ABC$ be a triangle with integer side lengths. Let $D, E$ be points on segment $BC$ such that $B, D, E,C$ are in this order, $BD=4$, and $EC=7$.
Suppose that there exists a circle which is tangent to sides $AB$ and $AC$, passes through $D, E$. Find the minimum of the perimeter of triangle $ABC$.
0 replies
NicoN9
23 minutes ago
0 replies
filling tiles again?
NicoN9   0
25 minutes ago
Source: Japan Junior MO Preliminary 2020 P9
There is a board with regular hexagon shape with side length $1$. As shown below, we dessert the board into $24$ of equilateral triangle, with side length $1/2$. We call the $19$ points of $\circ$ is good in the figure.

IMAGE
There are $12$ of tiles with side length $\frac{1}{2}$, $\frac{\sqrt{3}}{2}$, $1$ (thus the tile is right-angled). How many ways are there to fill the board with these tiles such that
$\bullet$ Each vertex of the tiles are on good points, and
$\bullet$ There doesn't exist $2$ tiles, such that it forms a equilateral triangle of side length $1$.
0 replies
NicoN9
25 minutes ago
0 replies
System of two matrices of the same rank
Assassino9931   1
N 3 hours ago by RobertRogo
Source: Vojtech Jarnik IMC 2025, Category II, P2
Let $A,B$ be two $n\times n$ complex matrices of the same rank, and let $k$ be a positive integer. Prove that $A^{k+1}B^k = A$ if and only if $B^{k+1}A^k = B$.
1 reply
Assassino9931
6 hours ago
RobertRogo
3 hours ago
Putnam 1952 B1
centslordm   4
N 5 hours ago by Gauler
A mathematical moron is given two sides and the included angle of a triangle and attempts to use the Law of Cosines: $a^2 = b^2 + c^2 - 2bc \cos A,$ to find the third side $a.$ He uses logarithms as follows. He finds $\log b$ and doubles it; adds to that the double of $\log c;$ subtracts the sum of the logarithms of $2, b, c,$ and $\cos A;$ divides the result by $2;$ and takes the anti-logarithm. Although his method may be open to suspicion his computation is accurate. What are the necessary and sufficient conditions on the triangle that this method should yield the correct result?
4 replies
centslordm
May 30, 2022
Gauler
5 hours ago
Miklós Schweitzer 1956- Problem 8
Coulbert   2
N 5 hours ago by izzystar
8. Let $(a_n)_{n=1}^{\infty}$ be a sequence of positive numbers and suppose that $\sum_{n=1}^{\infty} a_n^2$ is divergent. Let further $0<\epsilon<\frac{1}{2}$. Show that there exists a sequence $(b_n)_{n=1}^{\infty}$ of positive numbers such that $\sum_{n=1}^{\infty}b_n^2$ is convergent and

$\sum_{n=1}^{N}a_n b_n >(\sum_{n=1}^{N}a_n^2)^{\frac{1}{2}-\epsilon}$

for every positive integer $N$. (S. 8)
2 replies
Coulbert
Oct 11, 2015
izzystar
5 hours ago
Very straightforward linear recurrence
Assassino9931   1
N 5 hours ago by Etkan
Source: Vojtech Jarnik IMC 2025, Category II, P1
Let $x_0=a, x_1= b, x_2 = c$ be given real numbers and let $x_{n+2} = \frac{x_n + x_{n-1}}{2}$ for all $n\geq 1$. Show that the sequence $(x_n)_{n\geq 0}$ converges and find its limit.
1 reply
Assassino9931
6 hours ago
Etkan
5 hours ago
Integration Bee in Czechia
Assassino9931   0
6 hours ago
Source: Vojtech Jarnik IMC 2025, Category II, P3
Evaluate the integral $\int_0^{\infty} \frac{\log(x+2)}{x^2+3x+2}\mathrm{d}x$.
0 replies
Assassino9931
6 hours ago
0 replies
Trace with minimal polynomial x^n + x - 1
Assassino9931   0
6 hours ago
Source: Vojtech Jarnik IMC 2025, Category I, P4
Let $A$ be an $n\times n$ real matrix with minimal polynomial $x^n + x - 1$. Prove that the trace of $(nA^{n-1} + I)^{-1}A^{n-2}$ is zero.
0 replies
Assassino9931
6 hours ago
0 replies
Fast-growing sequences
Assassino9931   0
6 hours ago
Source: Vojtech Jarnik IMC 2025, Category I, P3
Let us call a sequence $(b_1, b_2, \ldots)$ of positive integers fast-growing if $b_{n+1} \geq b_n + 2$ for all $n \geq 1$. Also, for a sequence $a = (a(1), a(2), \ldots)$ of real numbers and a sequence $b = (b_1, b_2, \ldots)$ of positive integers, let us denote
\[
S(a, b) = \sum_{n=1}^{\infty} \left| a(b_n) + a(b_n + 1) + \cdots + a(b_{n+1} - 1) \right|.
\]
a) Do there exist two fast-growing sequences $b = (b_1, b_2, \ldots)$, $c = (c_1, c_2, \ldots)$ such that for every sequence $a = (a(1), a(2), \ldots)$, if all the series
\[
    \sum_{n=1}^{\infty} a(n), \quad S(a, b) \quad \text{and} \quad S(a, c)
    \]are convergent, then the series $\sum_{n=1}^{\infty} |a(n)|$ is also convergent?

b) Do there exist three fast-growing sequences $b = (b_1, b_2, \ldots)$, $c = (c_1, c_2, \ldots)$, $d = (d_1, d_2, \ldots)$ such that for every sequence $a = (a(1), a(2), \ldots)$, if all the series
\[
    S(a, b), \quad S(a, c) \quad \text{and} \quad S(a, d)
    \]are convergent, then the series $\sum_{n=1}^{\infty} |a(n)|$ is also convergent?
0 replies
Assassino9931
6 hours ago
0 replies
Strange ring property
sapience   2
N Yesterday at 11:48 PM by RobertRogo
Let \( (A, +, \cdot) \) be a ring with \( Z(A) \) its centre (\( Z = \{ x \in A \mid xy = yx \text{ for any } x, y \in A \} \)), \( U(A) \) the set of invertible elements and \( A^* = A \setminus \{0\} \).
We will say \(A\) has the property \( \mathcal{P} \) if there exists a subgroup \(H \) of group \( (U(A), \cdot) \) such that \( H \subset Z(A) \), \( H \neq A^* \) and \( x^3 = y^3 \) for any \( x, y \in A^* \setminus H \).
Prove the following:
a) any ring with property \( \mathcal{P} \) is commutative;
b) if \(A \) has the property \( \mathcal{P} \), then \( x^3 = 0 \), for any \( x \in A \setminus U(A) \).

Note: \(0 \) and \(1 \) are the identity elements for \(+ \) and \(\cdot \)
2 replies
sapience
Mar 5, 2025
RobertRogo
Yesterday at 11:48 PM
real analysis
ILOVEMYFAMILY   1
N Yesterday at 5:04 PM by Alphaamss
Source: real analysis
For which value of $p\in\mathbb{R}$ does the series $$\sum_{n=1}^{\infty}\ln \left(1+\frac{(-1)^n}{n^p}\right)$$converge (and absolutely converge)?
1 reply
ILOVEMYFAMILY
Dec 2, 2023
Alphaamss
Yesterday at 5:04 PM
Putnam 1962 B5
sqrtX   4
N Yesterday at 4:56 PM by centslordm
Source: Putnam 1962
Prove that for every integer $n$ greater than $1:$
$$\frac{3n+1}{2n+2} < \left( \frac{1}{n} \right)^{n} + \left( \frac{2}{n} \right)^{n}+ \ldots+\left( \frac{n}{n} \right)^{n} <2.$$
4 replies
sqrtX
May 21, 2022
centslordm
Yesterday at 4:56 PM
IMO ShortList 1998, combinatorics theory problem 1
orl   44
N Apr 23, 2025 by YaoAOPS
Source: IMO ShortList 1998, combinatorics theory problem 1
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$.)
44 replies
orl
Oct 22, 2004
YaoAOPS
Apr 23, 2025
IMO ShortList 1998, combinatorics theory problem 1
G H J
G H BBookmark kLocked kLocked NReply
Source: 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
#1 • 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
#2 • 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
#3 • 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
#4 • 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
#5 • 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
#6 • 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
#7 • 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
#8 • 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
#9 • 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
#10 • 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
#11 • 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
#12 • 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
#13 • 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
#14 • 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. :oops: 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
#15 • 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
#16 • 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
#17 • 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
#18 • 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
#19 • 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
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
#20 • 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
#21 • 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
#22 • 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
#28 • 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
#29 • 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
#30 • 2 Y
Y by Adventure10, Mango247
I don't find anything wrong with the reading nor the solution. :-D
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
#32 • 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
#33 • 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
#34 • 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
#35 • 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
#36
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
#37
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
#38
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
#39
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
12156 posts
#40
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
#41
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:
  1. Consider some cycle in the graph (exists by Euler as vertices have even degree).
  2. Choose the edge $e$ in this cycle whose weight is closest to an integer, with a distance $x$.
  3. Go around each edge in the cycle, alternating between adding and subtracting $x$. Do this such that $e$'s weight becomes an integer.
  4. This leaves the sum of edge-weights at each vertex the same.
  5. 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
#42 • 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
#43
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
1900 posts
#44
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.
1711 posts
#45 • 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$,
  1. The numbers written in each of these squares is non-integer.
  2. The squares $s_{i}$ and $s_{i+1}$ are either on the same row, or the same column.
  3. The squares $s_{i}$ and $s_{i+2}$ are neither on the same row, nor the same column.
  4. 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
1261 posts
#46
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
125 posts
#47 • 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
#48
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
#49
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
39 posts
#50
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
1535 posts
#51
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
N Quick Reply
G
H
=
a