Browse · MathNet
PrintTHE Tenth STARS OF MATHEMATICS COMPETITION
Romania counting and probability
Problem
Given a positive integer , determine the smallest integer satisfying the following condition: No matter how the cells of an array are colored one of colors, there exist cells and , and , sharing the same color.
Solution
Assuming such a coloring exists, let be the set of colors of the off-diagonal cells on row , and notice that the (re)stated condition shows that no contains an , , so the form an antichain.
Conversely, given an antichain of subsets of an -element set, assigning an off-diagonal cell an element in , and extending arbitrarily to on-diagonal cells yields a coloring satisfying the (re)stated condition.
Conversely, given an antichain of subsets of an -element set, assigning an off-diagonal cell an element in , and extending arbitrarily to on-diagonal cells yields a coloring satisfying the (re)stated condition.
Final answer
C(m, floor(m/2)) + 1
Techniques
Coloring schemes, extremal argumentsCounting two ways