[/quote]
,
be the circumcircle of 
and let 
be A-excircle .Let the two common tangents of 
cut 
in 
.
.
,
and 
.
can be partitioned into several 
the following inequality holds:
prove that
is a prime number. We have a number of cards, each of which has a number written on it such that each of the numbers 
appears at most once and 
exactly once. To design a game, for each pair of cards 
and 
,
If card 
,
If card 
,
must not win over card 
.
of natural numbers such that for every pair of natural numbers 
and 
,![\[
\frac{1}{2} < \frac{\gcd(a_r, a_s)}{\gcd(r, s)} < 2
\]](http://latex.artofproblemsolving.com/1/6/7/167679c1707b957d87311298ea5b72347a9bdc45.png)
such that
the following equation :
Y by cubres
Exactly 
cells of an 
square grid are colored black, and the remaining cells are white. The cost of such a coloring is the minimum number of white cells that need to be recolored black so that from any black cell 
, one can reach any other black cell 
through a sequence 
of black cells where each consecutive pair 
are adjacent (sharing a common side) for every 
. Let 
denote the maximum possible cost over all initial colorings with exactly black cells. Determine a constant 
such that
![\[
\frac{1}{3}n^{\alpha} \leq f(n) \leq 3n^{\alpha}
\]](//latex.artofproblemsolving.com/0/a/0/0a06d4ff52479c8cb785c6450cea8748bf7769b6.png)
for any 
.
cells of an 
square grid are colored black, and the remaining cells are white. The cost of such a coloring is the minimum number of white cells that need to be recolored black so that from any black cell 
, one can reach any other black cell 
through a sequence 
of black cells where each consecutive pair 
are adjacent (sharing a common side) for every 
. Let 
denote the maximum possible cost over all initial colorings with exactly black cells. Determine a constant 
such that![\[
\frac{1}{3}n^{\alpha} \leq f(n) \leq 3n^{\alpha}
\]](http://latex.artofproblemsolving.com/0/a/0/0a06d4ff52479c8cb785c6450cea8748bf7769b6.png)
for any 
.This post has been edited 1 time. Last edited by Assassino9931, Apr 9, 2025, 8:54 AM
from bottom to top and left to right, respectively.
and 
as 
.
be the largest integer such that 
.
,
in ascending order. Next, consider the columns congruent to 
,
cells such that the distance between any two black cells is at least 
new black squares. Note that the distance between any two black cells is at least 
new black cells. Since 
,
.
.
white cells such that the black cells satisfy the required condition.
black squares on an 
grid, there exists two squares whose distance is at most 
.
,
.
(these may lie outside the 
squares. Since the pairwise distance between black squares is at least 
,
.
Solving the inequality leads to a contradiction.
.![$$\sum_{m=2}^{n}\sqrt{\dfrac{2}{m+1}}\cdot (n+1) + n\leq \left[2(n+1)\right]^{3/2} + n<3n^{3/2}$$](http://latex.artofproblemsolving.com/c/0/c/c0ca85f7cfe1db7159b2cc4379a5c127aacaa6e0.png)
This completes the proof.
,
for 
.
additional cells. We also have 
cells from the 
columns and ![\[
n(m - 1) + mn + n = 2mn < 3n^{3/2}.
\]](http://latex.artofproblemsolving.com/9/a/e/9aefa63d61b39e763258bcfdf78b07a3458e1f29.png)
.
where 
(they are in the table, since 
,
)
,
within the starting black cell). These sets for different points do not intersect (they may only share boundary points).
black cells from the boundary of the initial black cell to the boundary of the corresponding area (if that number is fractional, then at least one of the newly added cells and on the boundary between two areas and not belonging fully to either of the two neighboring regions). This means that:![\[
f(n) \geq \frac{n}{2}(m - 1) \geq \frac{n}{2}(\sqrt{n - 1} - 2)
\]](http://latex.artofproblemsolving.com/3/a/5/3a5990385ddd8dd1ccd1a075e7da10b0a6742f06.png)
![\[
\frac{1}{2}(\sqrt{n - 1} - 2) \geq \frac{1}{3}\sqrt{n}
\]](http://latex.artofproblemsolving.com/2/1/1/21159c9efd1f45974f1266a2ce1f191533ef2421.png)
![\[
3\sqrt{n - 1} \geq 2\sqrt{n} + 6
\]](http://latex.artofproblemsolving.com/9/6/5/9651e6016594997925413ed005e80681bb0acf8d.png)
![\[
9n - 9 \geq 4n + 24\sqrt{n} + 36
\]](http://latex.artofproblemsolving.com/0/2/4/024ab2f23a94a9d3eae0197a04a7d04d7b0a3bd6.png)
![\[
5n - 45 \geq 24\sqrt{n}
\]](http://latex.artofproblemsolving.com/5/f/1/5f1c2b0fb034af8a8ef34228573def2c5403bc8a.png)
,
.
(here 
)
and 
)
and color in black a centered cell (unique if 
starting from the black cell and going out the 
square it belongs to; hence the total number of new squares is at least 
,
for something like 
.
instead, as it is anyway one of my favourite constants... Fortunately, this affected only one student and by not much (there were a few others in this trap, but they either quickly figured out an optimization or just bashed more efficiently smaller cases and this did not affect their overall performance in the day). All others with very good partials had combinatorial issues for the lower bound (like trying a spanning tree, which does not work easily/at all) or had very lazy constructions which required an upper bound constant much bigger than 
.
with 
vertices (cells) and edges that connect each two adjacent cells (sharing a side). We want to choose 
An easy calculation shows that it's enough to take 
.
be the set of 
be a connected subgraph of 
such that 
.
,
from 
,
,
,
and each edge of 
.
.
as to the white vertices and to the vertices in 
be a white vertex of 
be the neighbor of 
whose length is at least 
,
be all the leaves that 
.
where we assume 
.
since all 
are black. Summing up these inequalities, we get:
Now, we delete the vertex 
.
.
as 
.
