MathDB
Equal or Neq on the edges; Black or White in the cells

Source: 2024 imocsl C1 (Night 2-C)

August 8, 2024
combinatoricsColoringalgorithm

Problem Statement

On a n×nn \times n grid, each edge are written with == or ≠\neq. We need to filled every cells with color black or white. Find the largest constant kk, such that for every n>777771449n>777771449 and any layout of == and ≠\neq, we can always find a way to colored every cells, such that at least k⋅2n(n−1)k \cdot 2n(n-1) neighboring cells, there colors conform to the symbols on the edge. (Namely, two cells are filled with the same color if == was written on their edge; two cells are filled with different colors if ≠\neq was written on their edge)
Proposed by chengbilly & sn6dh
Back to ProblemsView on AoPS