[/quote]
,
,
may have in the range 
, as 
runs through integers 
.
be a scalene triangle, and let 
be its incenter. A point 
is chosen on line 
,
intersects 
at 
,
intersects 
at 
.
intersects 
and 
and 
intersect at 
,
and 
intersect at 
.
.
. Prove that
,
is circumcircle. Let 
.
and 
,
(opposite to 
and tangents to 
)
is midpoint of the arc 
.
be a sequence of positive real numbers, and 
be a positive integer, such that![\[a_n = \max \{ a_k + a_{n-k} \mid 1 \leq k \leq n-1 \} \ \textrm{ for all } \ n > s.\]](http://latex.artofproblemsolving.com/f/1/2/f12c9c5e0f154549118a33a2f359329333f432a7.png)
and ![\[a_n = a_{\ell} + a_{n - \ell} \ \textrm{ for all } \ n \geq N.\]](http://latex.artofproblemsolving.com/b/0/b/b0b2bd4507621302eeee27ae50ed9c0afd72c6ef.png)
and 
be two triangles inscribed in the same circle, centered at 
,
.
with respect to triangle 
.
.
lie in this order on the circle and form a convex, non-degenerate hexagon.
of 
.
and Anna plays first. The game is won by whom who shall be first able to write a number bigger or equal to 
.
be the circumcircle of 
and let 
be A-excircle .Let the two common tangents of 
cut 
.
.
satisfying the following condition: 
,
,
,
,
.
be variable points on 
is tangent to 
-- the circumcenter of triangle 
.
so that all of its sides are tangent to 
and 
,
and 
intersects on 
and 
be touch points of the incenter of 
and 
and 
,
and 
concurrent.
are such that 
,
Y by nguyendangkhoa17112003, Adventure10, Mango247
Let 
be a positive integer. Consider a 
array of square unit cells. Two corner cells that lie on the same longest diagonal are colored black, and the rest of the array is white. A move consists of choosing a row or a column and changing the color of every cell in the chosen row or column.
What is the minimal number of additional cells that one has to color black such that, after a finite number of moves, a completely black board can be reached?
be a positive integer. Consider a 
array of square unit cells. Two corner cells that lie on the same longest diagonal are colored black, and the rest of the array is white. A move consists of choosing a row or a column and changing the color of every cell in the chosen row or column.What is the minimal number of additional cells that one has to color black such that, after a finite number of moves, a completely black board can be reached?
,
,
.
in it, a white cell as it has 
in it. A move is denoted as choosing a column or a row and times every number in that row (or column) by 
as the number of times we time column 
by 
for column. Hence, after some move to get all black board, cell 
(column 
,
)
.
or 
is even. If a cell 
coloured black (or has 
must have the same parity for all 
(since they all start with white colour and all end with black colour) or 
have the same parity. On the other hand, since cell 
is black cell therefore, cells 
must also have black cells at the beginning in order to satisfy all 
have same parity.
,![[asy] fill((0,8)--(8,8)--(8,9)--(0,9)--cycle, gray);
fill((8,8)--(9,8)--(9,0)--(8,0)--cycle, gray);
for (int i=0; i<=9; ++i) { draw((0,i)--(9,i)^^(i,0)--(i,9)); }
[/asy]](http://latex.artofproblemsolving.com/0/0/2/0026348715138fe5833c206d47c4ac04410a8035.png)
black cells in column 
,
black cells. Hence, the minimum number of cells required is 
.
are black.
or 
.
denote the square containing cells 
.
is trivial. Consider an 
and 
must contain at least one other black cell. Suppose cell 
(or 
symmetrically) is colored. If there are two black cells in the first row or first column, we can invoke the induction hypothesis to get that there are at least 
black cells on the board to begin with. If, collectively, row 
and 
to get that there are at least 
black squares on the board. So we can assume that neither 
is colored black. If 
is also coloured, we consider 
to get that there are at least 
black squares (each square in the sequences above 'adds' a black cell, creating a snake-like pattern extending across the board. Note that by adding a black cell to 
we also add one to 
because otherwise 
is colored black. This allows us to consider 
and 
to conclude that at least 
squares are colored unless the cell 
,
and 
,
must be colored black so that 
contains two black cells. In all cases we must have at least 
squares colored black in order for the procedure to work. The construction is noted in the post above.
additional cells.
rows;
columns.
.![\[ k = a(n-b) + b(n-a). \]](http://latex.artofproblemsolving.com/3/e/1/3e18ce8682d7aa82654e02f55267e077b13d7c8e.png)
It will be more economical actually to write ![\[ n^2 - k = ab + (n-a)(n-b) \le \sqrt{ \left( a^2+(n-a)^2 \right) \left( b^2+(n-b)^2 \right)}. \]](http://latex.artofproblemsolving.com/f/d/e/fde824ce1b9951ecf801791f247b7d30af639417.png)
We now analyze two cases:
or 
in order to have two black cells not in the same row or column.
for 
,![\[ n^2 - k \le 1^2 + (n-1)^2 \]](http://latex.artofproblemsolving.com/5/6/f/56f479aca93d05e146fa42be9cc9383ab3590755.png)
which means 
.
;
,
. Also, my solution is almost the same solution as shinichiman's but I did not use the notation he used.
is trivial, so we let 
.
be the number of times we change the colors in the 
for the rows.) For any cell 
(if 
(if 
There is exactly one black cell in the first column.
is odd for all 
.
is initially black, we need all of the cells in the 
more cells( 
have the same parity). Also, notice that for any 
has the same parity, so initially, they are either all black or all white. (leaving the first cell in all the columns). To minimize we keep 
There is more than one black cell in the first column.
is again odd, so 
additional black cells in the first column, we basically have 
additional black cells in the rest of the columns except for the last one. Using the same parity argument for the last column, we see that we atleast need 
painted squares. This is because 
.
painted squares. If 
,
and 
yield at least 
when 
.![\[0\le (n-a-b)^2=[n^2+2ab-n(a+b)]-[n(a+b)-a^2-b^2]\]](http://latex.artofproblemsolving.com/4/2/2/422da26d2bcdfaf6cbf037f9efa8469833e8cfd0.png)
so ![\begin{align*}[ab+(n-a)(n-b)]-[2n-2]&=2ab+n^2-n(a+b)-2n+2\\&\ge n(a+b)-a^2-b^2-2n+2\\&=[n(a-1)-a^2+1]+[n(b-1)-b^2+1]\\&=(n-a-1)(a-1)+(n-b-1)(b-1)\\&\ge 0\end{align*}](http://latex.artofproblemsolving.com/6/0/0/60099a360bb788e54f4b7966961413e41d3c5481.png)
as desired. 
rows and columns that are not along the periphery of the grid are chosen. Then the number of intersection points between these rows and columns is at least 
.
square is at most 
.
more white squares among the non-corner periphery squares, as both of the edge rows and columns can be toggled or neither can be toggled to keep the corner square black. (Note that the two other corners can be made white.) As a result, the total number of white squares is at most 
This proves the bound for 
,
.
We will prove this by induction. For the base case when 
the answer is clearly 
with 2 moves being performed. For the case of simplicity, assume that all rows and columns are only inverted 
Note that since one row and one column are added and at least 2 moves are being performed, at least 
cells are required to be coloured black for 
so we can eventually turn all cells into black. This can be easily proven by contradiction, because if 
cells are required for 
then for 
it requires at most 
so 
This completes the induction. We wish to fnd a construction such that this value is achieveable. On a 
grid, we make the 
t
.![\[n^2-ab+(n-a)(n-b) \ge n^2-\sqrt{(a^2+(n-a)^2)(b^2+(n-b)^2)}\]](http://latex.artofproblemsolving.com/b/b/a/bbaeaa5f634301f71df3d5b9ee828f74fd94f92e.png)
squares starting out black. Taking away the corners gives our desired minimum.
,
.![\[(ab + (n - a)(n - b)) \leq \sqrt{(a^2 + (n - a)^2)(b^2 + (n - a)^2}\]](http://latex.artofproblemsolving.com/e/d/3/ed3fe7af8e1fa042b72094478cc7ba070627508f.png)
![\[\sqrt{(a^2 + (n - a)^2)(b^2 + (n - a)^2} \geq \sqrt{(1^2 + (n - 1)^2)(1^2 + (n - 1)^2} = n^2 - 2n + 2\]](http://latex.artofproblemsolving.com/5/3/d/53d557141d143edafb7dae7da1fa885b4098c1e9.png)
.![\[n^2 - (n^2 - 2n + 2) = 2n - 2\]](http://latex.artofproblemsolving.com/c/b/1/cb1eec7c18dcce72b8b370f439a17698a3e7765f.png)
.
which is achievable by coloring 
cells on the bottom row(without coloring in the corner cell) and then coloring 
rows and 
columns, where 
.![\[ab + (n-a)(n-b) = n^2-(a+b)n+2ab,\]](http://latex.artofproblemsolving.com/6/6/2/662a97b568a3608f74dad4b4a7f2a4695020198c.png)
fails, so the next best we can do is 
,![\[\left(n^2-n \cdot n + 2(n-1)\right) - 2 = \boxed{2n-4}.\]](http://latex.artofproblemsolving.com/e/a/e/eaeb531dce311c7b4ff718440f8a31c52f641991.png)
refer to the color of the cell at the 
is currently white, we must flip column 
columns. For each row, the flipped cells and not flipped cells must initially have different colors in order for the rows to be monochromatic after applying the column moves. Thus, there are either 
,![\[n\min\{k,n-k\}-2\ge 2n-2\]](http://latex.artofproblemsolving.com/a/3/b/a3b752760647d132d9158e4bca6de776156b5b1a.png)
For 
or 
,![\[(n-1) + \underbrace{1 + \cdots + 1}_{n-1} - 2 = 2n-4\]](http://latex.artofproblemsolving.com/c/0/1/c01c157521957d8809375517f7f011af7c5c0927.png)
For 
or 
and 
black for 
.
and exactly one of 
are toggled. Whence the answer is 
(Case 1), in which case optimality follows since pairs of non-vertex points on opposite sides are of opposite states. If 
are toggled (or 
but WLOG let it be the former; Case 2), ... let's do something silly: label a row by 
is the number of untoggled rows and so on, we want to min![\[\text{Im}((r_u+r_ti)(c_u+c_ti))=r_uc_t+r_tc_u.\]](http://latex.artofproblemsolving.com/6/8/2/6826d9c4df6cdeee46cc63ba2fb1ec364ad61f6a.png)
Here in Case 2, we have 
,
at, say, 
.
the answer is trivially 
we claim the answer is 
.
columns to the left of it. Define similarly for rows from the bottom. Then assign each cell a coordinate 
on column 
and 
or 
.
and row 
black cells on the array. Suppose we toggle 
rows and 
columns, there will be
black cells. WLOG 
.
generate the three smallest possible values of the above quantity in order. Clearly toggling 
rows cannot form two opposite black corners, but 
has a valid construction (we described it earlier.) Hence plugging in we have
and we are done.
additional black squares can be colored so that the grid can be made entirely white. Notice that flipping the color of any row or column twice will do nothing, so we can assume that we flip the color of any row or column at most once.
in order for it to be possible to choose rows and columns so that the two corner squares are turned black. Similarly we have 
Then, observe that after the operations, there are always 
black squares. This also equals 
It thus suffices to maximize 
Clearly both of these factors are either positive or negative. If they are both positive, we wish to minimize both 
Thus either 
In the former case we get 
while the other cases yield 
Clearly the maximum is 
are both negative. Therefore, the minimum is indeed 
row as 
and define 
similarly. Consider the parity of these variables. We start by proving the claim that there's at least one row and one column of parity different than the others. To do this, use a Proof by Contradiction: Assume WLOG that all rows have the same parity. This fails because we would need the first and last column to be all black squares, which gives us at least 
more squares to be blackened. We know the minimum of 
exists, so this fails.
squares. This is minimized when 
giving us 
as desired. 
and 
be the number of times a row and column are toggled, then we want to minimize the number of even sums. 
.
which can be done with simple manipulation
