Find all ordered pairs of positive integers $(m,n)$ for which there exists a set $C=\{c_1,\ldots,c_k\}$ ($k\ge1$) of colors and an assignment of colors to each of the $mn$ unit squares of a $m\times n$ grid such that for every color $c_i\in C$ and unit square $S$ of color $c_i$, exactly two direct (non-diagonal) neighbors of $S$ have color $c_i$.

[i]David Yang.[/i]
1. **Characterization of the Problem:**
   We need to find all ordered pairs of positive integers \((m, n)\) such that there exists a set \(C = \{c_1, \ldots, c_k\}\) of colors and an assignment of colors to each of the \(mn\) unit squares of an \(m \times n\) grid. The assignment must satisfy the condition that for every color \(c_i \in C\) and unit square \(S\) of color \(c_i\), exactly two direct (non-diagonal) neighbors of \(S\) have color \(c_i\).

2. **Construction for Even \(m\) and \(n\):**
   We claim that if both \(m\) and \(n\) are even, then such a coloring is possible. To construct this, we can use \(2 \times 2\) squares. For example, consider the following \(4 \times 4\) grid:
   \[
   \begin{array}{|c|c|c|c|}
   \hline
   c_1 & c_1 & c_2 & c_2 \\
   \hline
   c_1 & c_1 & c_2 & c_2 \\
   \hline
   c_3 & c_3 & c_4 & c_4 \\
   \hline
   c_3 & c_3 & c_4 & c_4 \\
   \hline
   \end{array}
   \]
   Each \(2 \times 2\) block is colored with a single color, and each square in the block has exactly two neighbors of the same color.

3. **Proof that Only Even \(m\) and \(n\) Work:**
   We need to show that if such a coloring exists, then both \(m\) and \(n\) must be even.

   - **Closed Region Definition:**
     Define a *closed region* to be the set of all squares with color \(c_i\) for some \(i\) and the set of all squares that are enclosed by them.

   - **Claim 1: The only closed region that encloses no squares is the \(2 \times 2\) square.**
     - **Proof:**
       Suppose there exists another such region. Let \(C_1\) be any convex corner of the region and \(C_2\) and \(C_3\) the squares that border \(C_1\). Then for \(C_4\) the square such that \(C_1C_2C_3C_4\) is a \(2 \times 2\) square, \(C_4\) is located within the interior of the closed region. It follows that \(C_2\) and \(C_3\) may not border any more squares, from where connectivity implies the region is precisely a \(2 \times 2\) square. \(\blacksquare\)

   - **Claim 2: Every closed region has even dimensions.**
     - **Proof:**
       For simplicity, we will call these closed regions *even regions*. Notice that if a region is a union of two even regions, then it must itself be an even region.

       Now we proceed by induction on the number of squares in the closed region. For the base case, the smallest possible closed region is a \(2 \times 2\) square, which is indeed an even region. For the inductive step, take any closed region and remove all the squares colored \(c_i\). These squares form a "band" around the periphery of the region, so the parity of the width or length measured at any given index will remain the same.

       The region that remains is a union of some (at least one) closed regions. By the inductive hypothesis, each of these closed regions is even, so their union is even, and the original closed region is also even, as required. \(\blacksquare\)

4. **Conclusion:**
   Since our original \(m \times n\) grid is a union of closed regions, it must have even dimensions too. Therefore, both \(m\) and \(n\) must be even.

The final answer is \( \boxed{ (m, n) } \) such that both \(m\) and \(n\) are even.