Minimum k such that there is a k-balance label
Source: 2017 VMO Problem 4
January 11, 2017
combinatoricsgraph theorysymmetry
Problem Statement
Given an integer and a grid containing 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 is colored by gray and every couple of unit squares which are symmetry by should be both colred by black or white. In each gray square, they label a number , in a white square, they will label a positive integer and in a black square, a negative integer. A label will be called -balance (with ) if it satisfies the following requirements:i) Each pair of unit squares which are symmetry by are labelled with the same integer from the closed interval 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 , find the minimum value of such that there is a -balance label for the following grid[asy]
size(4cm);
pair o = (0,0); pair y = (0,5); pair z = (5,5); pair t = (5,0); dot("", y, dir(180)); dot("", z); dot("", t); dot("", 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] b) Let . Find the least value of such that there is always a -balance label for a symmetry coloring.