Given an integer $n>1$ and a $n\times n$ grid $ABCD$ containing $n^2$ unit squares, each unit square is colored by one of three colors: Black, white and gray. A coloring is called symmetry if each unit square has center on diagonal $AC$ is colored by gray and every couple of unit squares which are symmetry by $AC$ should be both colred by black or white. In each gray square, they label a number $0$, in a white square, they will label a positive integer and in a black square, a negative integer. A label will be called $k$-balance (with $k\in\mathbb{Z}^+$) if it satisfies the following requirements: i) Each pair of unit squares which are symmetry by $AC$ are labelled with the same integer from the closed interval $[-k,k]$ ii) If a row and a column intersectes at a square that is colored by black, then the set of positive integers on that row and the set of positive integers on that column are distinct.If a row and a column intersectes at a square that is colored by white, then the set of negative integers on that row and the set of negative integers on that column are distinct. a) For $n=5$, find the minimum value of $k$ such that there is a $k$-balance label for the following grid [asy][asy] size(4cm); pair o = (0,0); pair y = (0,5); pair z = (5,5); pair t = (5,0); dot("$A$", y, dir(180)); dot("$B$", z); dot("$C$", t); dot("$D$", o, dir(180)); fill((0,5)--(1,5)--(1,4)--(0,4)--cycle,gray); fill((1,4)--(2,4)--(2,3)--(1,3)--cycle,gray); fill((2,3)--(3,3)--(3,2)--(2,2)--cycle,gray); fill((3,2)--(4,2)--(4,1)--(3,1)--cycle,gray); fill((4,1)--(5,1)--(5,0)--(4,0)--cycle,gray); fill((0,3)--(1,3)--(1,1)--(0,1)--cycle,black); fill((2,5)--(4,5)--(4,4)--(2,4)--cycle,black); fill((2,1)--(3,1)--(3,0)--(2,0)--cycle,black); fill((2,1)--(3,1)--(3,0)--(2,0)--cycle,black); fill((4,3)--(5,3)--(5,2)--(4,2)--cycle,black); for (int i=0; i<=5; ++i) { draw((0,i)--(5,i)^^(i,0)--(i,5)); } [/asy][/asy] b) Let $n=2017$. Find the least value of $k$ such that there is always a $k$-balance label for a symmetry coloring.
Problem
Source: 2017 VMO Problem 4
Tags: combinatorics, graph theory, symmetry
15.01.2017 18:27
For (a), code the unit squares with coordinates. The leftmost and lowest one $(0,0)$, the rightmost and the lowest one $(4,0)$, the rightmost and the highest one $(4,4)$, etc. Consider column $0$ and row $1$, they intersect at the black square $(0,1)$. So squares $(0,0), (0,3), (1,1), (2,1), (4,1)$ must be labelled with distinct positive integers, hence $k\geq5$. The following labeling shows that is is possible to achieve $k=5$: \begin{tabular}[c]{|c|c|c|c|c|} \hline 0&1&-1&-2&2\\ \hline 1&0&3&3&1\\ \hline -1&3&0&4&-3\\ \hline -2&3&4&0&5\\ \hline 2&1&-3&5&0\\ \hline \end{tabular}
26.01.2017 11:44
The answer for part a) is $3$; part b) is $\frac{2017^2-1}{4}$
08.02.2017 19:04
For the question b ; we can change the square into graph theory and by using Turan theorem we found 2017^2-1/4
22.02.2017 04:18
Lam.DL.01 wrote: For the question b ; we can change the square into graph theory and by using Turan theorem we found 2017^2-1/4 Can somebody elaborate how we use turan here? I get something similar but, it clearly isn't turan so I don't get it.
21.03.2017 18:52
The square that have draw by black( do similary in white) we introduce is like a vertices. You can prove ( easily) the graph is the 2-biparite graph.So by Turan we have E <= 2017^2/4
10.06.2020 12:07
Must "distinct" be "disjoint"? Well, I'm not sure whether the statement is wrong or not...