k2c901_1 wrote: Every square on a $n\times n$ chessboard is colored with red, blue, or green. Each red square has at least one green square adjacent to it, each green square has at least one blue square adjacent to it, and each blue square has at least one red square adjacent to it. Let $R$ be the number of red squares. Prove that $\displaystyle \frac{n^2}{11} \le R \le \frac{2n^2}{3}$. Is diagonal adjacency counted?

who can slove it i think its not easy

I'll assume diagonal adjacency is not counted. Let X be the set of all cells in the chessboard. Then we know #X = $n^{2}$. Let R, G and B be the set of all RED cells, the set of all GREEN cells, and the set of all BLUE cells. you know #R+#G+#B = #X For x in X, let N(x) = {y in X | y is adjacent to x }. I know #N(x) <= 4. There exists a function F : X -> X satisfying the following three conditions : (1) If r $\in$ R then F(r) $\in$ G $\cap$ N(r). (2) If g $\in$ G then F(g) $\in$ B $\cap$ N(g). (3) If b $\in$ B then F(b) $\in$ R $\cap$ N(b). F is fixed from now on. R_1 = { r in R | r, F(r) and F(F(r)) are either on the same row or on the same column } R_2 = R \ R_1 For example, if r $\in$ R_1 and g = F(r) and b = F(F(r)) then the arrangement of r, g and b must be one of the following 4 forms. r b g g r g b b g r b r If r $\in$ R_2 then the arrangement must be one of the following 8 forms. r g b r r b r g g b b g ... and the rest 4 cases. We'll say a function f : Y -> Z is at-most-d to one if for each z $\in$ Z we have $\# f^{-1}(z)$ <= d. Remember that then we have #Y <= d #Z. Claim: the six important inequalities. #R_1 <= #G #R_2 <= 2 #G #R_1 <= 3 #B #R_2 <= 4 #B (they are 1,2,3,4. beautiful) #R <= 3 #G #R <= 7 #B Proof: 5th ineq follows from 1st and 2nd. 6th ineq follows from 3rd and 4th. Now we only have to prove the first 4 ineqs. Let $(F\mid R_{1})$ be the restriction of F on R_1. Considering possible rgb arrangements, we can show that (F|R_1) is injective. Hence the 1st ineq. Also we can show the function $(F\mid R_{2})$ is at-most-2 to one, considering rgb arrangements. Hence the 2nd ineq. $(F^{2}\mid R_{1})$ is at-most-3 to one (Considering that one of N(b) is red, thus blocking one possible pre-image of F^2. Hence at-most-3. ) Hence the 3rd ineq. $(F^{2}\mid R_{2})$ is at-most-4 to one. Hence the 4th ineq. Done the six inequalities. Apply the proof of 5th and 6th inequalities to cyclic permutations of R,G and B, we have another four ineqs. #G <= 3 #B #G <= 7 #R #B <= 3 #R #B <= 7 #G We've collected enough ineqs to do the lower and the upper bound of #R. The lower bound. 11 #R = #R + 7 #R + 3 #R >= #R + #G + #B = #X The upper bound. Recall the four inequalities which I called 'beautiful'. To get the upper bound, we do 2 (1st ineq) + (2nd ineq) + (4th ineq). 2 #R <= 2 #R_1 + #R_2 + #R_2 <= 2 #G + 2 #G + 4 #B = 4 (#G+#B) = 4 ( #X - #R) Hence, 3 #R <= 2 #X . Done the 1/11 <= #R/#X <= 2/3. sloved it. I'm wondering if there is a nice at-most-2 to 1 function from R to G $\cup$ B. That would make a delicious proof of #R/#X <= 2/3. Let's try to find it. - [edit] Remark: what's done to get the lower bound. If we apply it to get an upper bound, we get #R/#X <= 21/31. The motivation for partitioning R into R_1 and R_2 is to lower this upper bound from 21/31 to 2/3.