We got $n\times n$ board colored in different colors. The count of cells with the same color is $\leq \frac{n-1}{16}$. Prove that we can manage to place $n$ rooks on different color cells, so they were "peacefully"(without attacking each other) on board.
Can someone give a hint how to solve this problem? I think we should represent this board as graph, and make graph-coloring task out of this one, but I couldn't manage to do it on my own.
I believe the answer to your question can be found as Theorem 5.6.1 of Alon and Spencer’s book on the probabilistic method.
The theorem states: let $A$ be an $n\times n$-matrix, where no value appears in more than $(n-1)/4e$ entires. Then $A$ contains a “traversal” (or in other words, there exists a permutation $\pi$ such that $A_{1,\pi(1)},\dots,A_{n,\pi(n)}$ are all distinct values).
Please correct me if this not what you’re asking about.
The proof in the book uses a variant of the Lovasz Local Lemma. It’s a bit long, so I won’t copy it here (though if I have time later I might add something). Hope this helps!