Competition problem — Combinatorics

Combinatorics Difficulty 4.9 AIME Prove it Romania

Given a positive integer $m$ , determine the smallest integer $n \ge 2$ satisfying the following condition: No matter how the cells of an $n \times n$ array are colored one of $m$ colors, there exist cells $(i, j)$ and $(j, k)$ , $i \neq j$ and $j \neq k$ , sharing the same color.

Solution

Assuming such a coloring exists, let $S_i$ be the set of colors of the off-diagonal cells on row $i$ , and notice that the (re)stated condition shows that no $S_i$ contains an $S_j$ , $i \neq j$ , so the $S_i$ form an antichain.

Conversely, given an antichain $S_1, \dots, S_n$ of subsets of an $m$ -element set, assigning an off-diagonal cell $(i, j)$ an element in $S_i \setminus S_j$ , and extending arbitrarily to on-diagonal cells yields a coloring satisfying the (re)stated condition.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.