AoPS Academy
cups labeled 
, where the 
-th cup has capacity liters. In total, there are liters of water distributed among these cups such that each cup contains an integer amount of water. In each step, we may transfer water from one cup to another. The process continues until either the source cup becomes empty or the destination cup becomes full.
Prove that from any configuration where each cup contains an integer amount of water, it is possible to reach a configuration in which each cup contains exactly 1 liter of water in at most 
steps.
Prove that in at most 
steps, one can go from any configuration with integer water amounts to any other configuration with the same property.
and 
for which there exists a natural number
such that the number 
is integer for all natural 
.
has 
as the midpoint of 
and orthocenter 
. Let 
be an arbitrary point on the nine point circle of 
. The line through perpendicular to 
intersects at 
. The line through 
perpendicular to 
intersects 
at 
. If 
is the midpoint of , show that 
.
x
. So we separeted the board in sub board 
, in L-triminos and 
sub board in this form, for example 
and 
.. It's easy see, we have 
, L-triminos and sub board of . We note that in each there are at most 
black cells, in each L-triminos there are at most black cells, and in each there is at most 
black cell. In total, there are 
and this is the answer. The example for all n is colored columns 
be a 
board. Some of its cells are colored black in such a way that every 
board of has at most black cells. Find the maximum amount of black cells that the board may have.
by is called as 
which satisfies all conditions of the problem, then we can remove last rows and last columns and still the condition would be satisfied. We will use this but in the opposite direction, being careful because the converse of the statement I made above doesn't hold true.
. Let us say that alternative row coloring has been optimal choice of coloring for some , base case 
fails to work due to pigeon hole principle as two square cannot cover spots in every by square in the by square grid so 
is maximum for 
, only way of acheiving it is the column or row coloring. Now, we can see that PHP argument also tells us that best coloring for by is by alternative row or a full column or vice versa. by , by and by 
rectangle together in a particular manner, we get a by square. Now, we know that we have combined three objects will optimal coloring. It seems that overall this huger coloring is also optimal, we'll call this coloring . Also let us call these three rectangle as 
respectively. Suppose there exists better coloring. Then at least one of the rectangles of this new coloring has more marked squares than the rectangle in the coloring we claimed to be optimal. This contradicts the fact that were given optimal coloring.
To prove this, we induct on 
The base case is trivial; assume that this bound holds for We will prove that it also holds for 
-th row and 
-th column be 
and split the board into an L-shaped piece 
and a 
board 
with the upper-left vertex 
black squares in 
Hence, there are at least 
black squares in 
Now, divide into several (
, more specifically) squares and the four unit squares 
and 
square has at most 2 black squares and has at least black squares, hence and 
must all be black. However, by a symmetrical decomposition of we can deduce that 
and 
must all be black as well. square must have at least black squares in it, which is a contradiction. Therefore, our bound holds for an 
board as well. Equality can be obtained by a chessboard coloring, where 
is black.
consecutive rows of the board, there are atmost black cells. Let's forget the rest of the board for now, and we will show that if we only consider the problem's constraints in the subgrid here, it will still give the required result. Consider each location such that the black square is in the bottom and there is a white cell just to the top of it.
cells colored black, (after this movement, the numner of black cells hasn't changed so don't panic) then the first row must be completely black and at least one of the bottom row cells should be black as well. But then if we consider a board containing that bottom cell, it has black cells, a contradiction. Thus there are at most 
cells as such. Now, divide the original board into such 
boards and one 
array. This immediately gives that there are at most black cells in the entire board. And this is achievable, for if we number the rows of the board from to and color the odd rows black completely then the board satisfies our conditions and has colored cells. Thus the answer to the problem is .
. The base case clearly holds true. Now let the assertion hold true for all 
. Partition the 
board into four rectangles, of dimensions 
respectively. First note that any 
box has a maximum of 
black cells in it (divide it into a box of dimension 
which cannot have more than 
black cells) with equality when each of the two columns have 
black cells and each black cell in one column has an adjacent black cell in the other column. Now if the box has 
black cells, we get the maximum as 
which is less than 
. If the box has black cell, the maximum is 
. If it has black cells, however, one 
box is forced to have 
black cells (equality can’t ever hold) so the maximum remains the same and we are done. box can have at least 
black cells while following the given condition. This means that some column has at least 
black cells. Call such a column good, else call it bad. We make two cases. In the first case, the leftmost column isn’t good. Since we know a good column exists, choose the leftmost one, and pair it with the column on its left, and delete it. So we are left with 
cells and 
columns. In general, it is easy to prove that 
which means that every time we can pair a good column with its adjacent bad column, we can delete them and by php we can always find another good column. Back to the main problem, we just keep choosing the leftmost good column at each step and we can always pair it with an adjacent bad column (in this case just pair every good column with its leftmost column) because no two good columns can be adjacent. Therefore at least of the box’s columns should be good, and at maximum it can have 
black cells, contradiction. In the second case, the leftmost column is good. As usual, keep choosing the leftmost good column and pair it with its adjacent left column if possible (it might not be if it’s already deleted ; in that case choose the right one). If at some point we are able to pair it with its left column, do that and keep pairing the good columns after that with their left ones. This means we can always pair a good column with an adjacent bad column, so we are done by the same reasoning as in the above case. However if it’s not possible, it would mean that column 
are good which means that the maximum is 
, contradiction.
, which can be achieved by coloring every other row black, starting with the uppermost (so we get 
colored rows). To show that this is an upper bound I will use induction, with the base case of 
being clear.
board from a 
board a " L". By inductive hypothesis it suffices to show that at most 
cells in a L are black. We again use induction for this. For the base case of 
, divide the L as such:![[asy]
draw((0,3)--(2,3));
draw((0,2)--(3,2));
draw((0,1)--(3,1));
draw((0,0)--(3,0));
draw((0,3)--(0,0));
draw((1,3)--(1,0));
draw((2,3)--(2,0));
draw((3,2)--(3,0));
draw((0.1,2.9)--(1.9,2.9)--(1.9,1.1)--(0.1,1.1)--cycle, red);
draw((2.9,0.1)--(2.9,1.9)--(1.1,1.9)--(1.1,0.1)--cycle, blue);
draw((0.1,0.1)--(0.9,0.1)--(0.9,0.9)--(0.1,0.9)--cycle, green);
[/asy]](http://latex.artofproblemsolving.com/0/9/a/09aa98ae12821690ddae6ad60b4da039c0916731.png)
as desired. Now, a L is simply a L with two squares added to both "ends" of the L, which increases the number of black cells by at most 
. Therefore, by inductive hypothesis there are at most black cells in a L, so we're done. 
, where equality holds when we color all the odd-indexed rows black. and white square with 
. For double counting reasons, it suffices to show that we can have at most corner black squares and 
edge black squares. Actually, we will show the stronger conclusion that we can have at most 
black squares along the outer periphery. is not optimal. Divide the square into 
layers in succession wrapped around one center square, and define the value of each layer to be the sum of the values of it squares, counted by multiplicity according to how many squares with one edge along the edge of this layer the square belongs to. This means that the value of the outer periphery of squares is greater than 
.
each layer. squares that are formed by squares within the two layers must have values summing to zero. On the other hand, this value equals 
As the value of the four corner squares is at most 
, this implies the result. 
. However, using the previous equality again, this implies that the value of the center square has absolute value greater than (as it is counted in four of the squares), contradiction.
achieved by coloring all the odd numbered rows. with the base case being clear. For the other direction, we are going to decompose our 
board into a square, two 
strips, and a 
square, as shown below.![[asy]
size(6cm); filldraw(box( (0,0), (2,7) ), palegreen, blue+1); filldraw(box( (2,7), (9,9) ), palegreen, blue+1); filldraw(box( (0,7), (2,9) ), palered, blue+1); for (int i=0; i<=9; ++i) { draw( (0,i)--(9,i), grey ); draw( (i,0)--(i,9), grey ); } filldraw(box((2,0), (9,7)), paleyellow, blue+1); label("$(2n-1) \times (2n-1)$", (5.5, 3.5), blue);
[/asy]](http://latex.artofproblemsolving.com/1/1/2/11280312887d8f187563e2716e2d5e6fae1fca00.png)
square has at most two black cells.
black cells, with equality if and only if the rows of length are shaded alternating black. The same is true for the northern green rectangle. black cells, then the red square has at most one black cell (at the northwestern corner).
black squares.![\[ \underbrace{n \cdot (2n-1)}_{\text{by IH}} + \underbrace{(4n+1)}_{\text{green/red}} = (n+1)(2n+1). \]](http://latex.artofproblemsolving.com/d/1/b/d1baeecb112acf76f694ffbb85bbf3462453452a.png)
, achieved by coloring in every other column. Now, we will show that this is true by induction. The base case is vacuous so we move on to the inductive step.
. This is equivalent to a 
square having at most 
black cells. Notice that a square can be dissected into a square, two rectangles, and a square. square be in the bottom-left corner. By the induction hypothesis, the contains at most squares, and we can easily find that the rectangles contain at most squares each with a similar tiling configuration. Then, the square contains at most squares. However, if both equality cases hold for the rectangles, only the top-left square of the square can be colored in, and it is clear that this is optimal. square is![\[k(2k-1)+2k+2k+1 = (k+1)(2k+1),\]](http://latex.artofproblemsolving.com/4/2/4/4241cd79809da31c4d6dfbe9974778a7bfbbb245.png)
, which can be constructed by alternating shading each row. Induct on , with trivial base case .
can be split into a square with side (which our inductive hypothesis tells us has at most black squares), along with a square of side length 2 (which by definition has at most 2) and two rectangles with dimensions 
. These rectangles can be further divided into squares of side length 2 and a 
rectangle, so they have a maximum of black squares with equality only when we have alternating black columns. square and rectangle, so the next best we can do is 
, from which adding to indeed gives us an upper bound of 
, which we've shown to be achieveable. 
. For construction, color the leftmost column black and alternate black/white columns throughout.
. For the base case, it is clearly which our bound equals. For the inductive step, assume it is true for 
for some 
. Note that the bottom-left 
subgrid contains at most 
black cells by our inductive hypothesis. The rest of the grid can be partitioned into 
copies of a grid which have at most 
black cells, and a 
grid missing a corner, which can be easily shown to have at most black cells. Adding our bounds the total number of black cells is at most
as desired.
which is attainable when the rows are filled/not filled in an alternating pattern, with the top row being filled.
The base case, 
is trivial so assume that our proposition holds for some integer 
Then consider a 
board. From the inductive hypothesis, the top left board has at most black squares. Then, the rest of the board can be partitioned into a heart-shaped tile with squares, and two rectangles. The rectangles each can be separated into 
squares, each having at most black cells, therefore the two rectangles combined contribute at most 
black squares. black squares. Otherwise, if we have at least 
we can bash all cases to see that they don't work. (It's not too many anyways) Therefore, we have at most 
so the bound holds for 
, achieved by alternating rows black with the top row black. We proceed using induction with the base case obvious to show. Now, consider a grid. Take out a grid from the bottom right corner to get a "L" shape remaining. We need to show that this shape has at most 
black squares. Partition it into squares as shown in the image below which is easily generalizable. We have this small tetris piece left highlighted in red. It remains to show that this tetris piece cannot be all black which is obvious by considering the square in blue which finishes.
, achievable by coloring alternate columns black and white.![[asy]
defaultpen(0.5);
fill( box( (1, 1), (8, 2) ), palegreen);
fill( box( (7, 2), (8, 8) ), palegreen);
fill( box( (1, 7), (7, 8) ), palegreen);
fill( box( (1, 1), (2, 7) ), palegreen);
fill( box( (2, 2), (7, 3) ), palered);
fill( box( (6, 3), (7, 7) ), palered);
fill( box( (3, 6), (6, 7) ), palered);
fill( box( (2, 3), (3, 7) ), palered);
draw(box( (1, 1), (3, 3) ), blue + 1);
draw(box( (2, 1), (4, 3) ), orange + 1);
draw(box( (1, 2), (3, 4) ), black + 1);
draw(box( (3, 1), (5, 3) ), yellow + 1);
draw(box( (0, 0), (9, 9)), black + 1 );
label("1", (1.5, 1.5));
label("2", (2.5, 1.5));
label("3", (2.5, 2.5));
label("2", (3.5, 2.5));
for (int i=0; i<=9; ++i) { draw( (0,i)--(9,i), grey ); draw( (i,0)--(i,9), grey ); };
[/asy]](http://latex.artofproblemsolving.com/2/d/1/2d1a34bfc5aba9e784c420e004cbc8fc5e4873a8.png)
be the number of black cells in the th layer, which is the ring of cells on the perimeter of a 
square centered at the center of . Additionally, let 
be the number of black squares in the th layer along the diagonals, and let 
be the total number of black cells.
of all squares which contain cells from layers and 
. There are 
such squares, one associated with each non diagonal cell of layer . Consider the sum:![\[ R_k = \sum_ {s \in S_k} (\text{ \# of black squares in $S$}) \]](http://latex.artofproblemsolving.com/d/5/2/d52b68b81e1e05363002b256356f44e261ebbdf0.png)
As each term of this sum is 
, this sum is 
. Considering each type of square(see diagram), we see: diagonal black cells in layer is counted time.
non-diagonal black cells in layer is counted times.
diagonal black cells in layer is counted times.
non-diagonal black cells in layer is counted times.
.![\[ L_k + L_{k - 1} = R_k - \frac{X_{k - 1} - X_k}2 \le 8n - 4 - \frac{X_{k - 1} - X_k}{2} \le 8n - 4 - \frac{0 - 4}{2} = 8n - 2 \]](http://latex.artofproblemsolving.com/0/5/0/0509e88c675c2f5f383fc917c8d4f7efadd5783d.png)
where we have used that by definition, 
.
(if is even) gives us the desired upper bound on 
.
be an arrangement of 
.
board in the bottom left corner has at most 
cells. Now, tile the remaining board with 
squares such that there are 
black cells in the 
black cells.
there can be 
black cells. By the Pigeonhole Principle, there exists at least one column that has three black cells and at least one row that has three black cells. As a result, there would be at least one 
board for a positive integer 
We will show that we can have at most 
black cells on a 
board.
board, a 
board, and a 
board. Each of the 
black cells. Note that, in order for the 
black cells. Assume for the sake of contradiction that equality can be achieved. Then, the four cells that are directly adjacent to the 
black squares in those two rows, and 
in the rest. Thus, we wish to maximize 
over 
Let 
and 
to find that the maximum number of possible black cells the board may have is 
Now, we wish to find a way where this is achieveable. Number the rows 
from top to bottom (assume the board has vertical and horizontal sides). Thus, coloring all rows with odd numbers with black cells yields a board with 
cells are black that also satisfies the condition in the problem.
