positive real C is n−vengeful if it is possible to color the cells of an n×n chessboard such that: i) There is an equal number of cells of each color. ii) In each row or column, at least Cn cells have the same color. a) Show that 34 is n−vengeful for infinitely many values of n. b) Show that it does not exist n such that 45 is n−vengeful.
Problem
Source: 25th Olympic Revenge
Tags: combinatorics, Chessboard
04.08.2022 07:11
a) For n=4, consider the following chessboard T. [asy][asy] unitsize(0.5cm); for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { fill(box((i, j), (i + 1, j + 1)), ((i, j) == (0,0) || (i, j) == (0,1) || (i, j) == (0,2) || (i, j) == (3,1) || (i, j) == (3,2) || (i, j) == (3,3) || (i, j) == (1,1) || (i, j) == (2,2)) ? black : white); } } for (int i = 0; i <= 4; ++i) { draw((i, 0)--(i, 4)); draw((0, i)--(4, i)); draw((i, 0)--(i, 4)); draw((0, i)--(4, i)); } [/asy][/asy] For n=4k, just take a k×k formed by k2 copies of T. b) We will prove that 34 is the best possible constant C. Let A and B be the two colors and UV be the sub-table induced by taking the rows with at least Cn cells of the color U and the columns with at least Cn cells of the color V, for U,V∈{A,B}. Let x and y be the proportions of rows and columns with at least Cn cells of the color A, respectively. From now on, we will count the proportion of cells that are of a given color (so z cells should be interpreted as zn2 cells). Taking AB, AA, and BA, there are at least Cx A cells in the first two, Cy in the last two, but at most xy in their intersection AA. So there are at least Cx+Cy−xy A cells in total and Cx+Cy−xy≤12⟺C≤12+xyx+y≤12+(x+y2)2x+y≤34⟺2+(x+y)2≤3(x+y)⟺(x+y−1)(2−x−y)≥0, and we are done (WLOG x+y≥1, otherwise change A and B).