MathDB
Problems
Contests
National and Regional Contests
Ukraine Contests
Official Ukraine Selection Cycle
Ukraine Team Selection Test
2018 Ukraine Team Selection Test
4
4
Part of
2018 Ukraine Team Selection Test
Problems
(1)
red or blue edges in a square nxn lattice
Source: Ukraine TST 2018 p4
4/29/2020
Let
n
n
n
be an odd integer. Consider a square lattice of size
n
×
n
n \times n
n
×
n
, consisting of
n
2
n^2
n
2
unit squares and
2
n
(
n
+
1
)
2n(n +1)
2
n
(
n
+
1
)
edges. All edges are painted in red or blue so that the number of red edges does not exceed
n
2
n^2
n
2
. Prove that there is a cell that has at least three blue edges.
Coloring
combinatorics