An $m \times n$ chessboard where $m \le n$ has several black squares such that no two rows have the same pattern. Determine the largest integer $k$ such that we can always color $k$ columns red while still no two rows have the same pattern.
1. **Base Case:**
   - Consider the smallest case where \( n = 1 \). Since \( m \leq n \), we must have \( m = 1 \) as well. In this scenario, we have a \( 1 \times 1 \) chessboard with only one column. Clearly, we can color this single column red, satisfying the condition that no two rows have the same pattern (since there is only one row). This establishes the base case.

2. **Inductive Step:**
   - Assume the statement is true for an \( m \times (n-1) \) chessboard, i.e., we can always color \( (n-1) - m + 1 = n - m \) columns red while ensuring no two rows have the same pattern.
   - Now consider an \( m \times n \) chessboard \( B \). We need to show that we can color \( n - m + 1 \) columns red.

3. **Case 1:**
   - Suppose there exist two rows in \( B \) that are identical except for one column. This column cannot be colored red because doing so would make the two rows identical. 
   - Erase this column and remove one of the two identical rows. If removing this column causes any other pairs of rows to become identical, remove one row from each such pair as well. This results in a new board with \( n-1 \) columns and at most \( m-1 \) rows.
   - By the induction hypothesis, we can color \( (n-1) - (m-1) + 1 = n - m + 1 \) columns red in this reduced board. These same columns can be colored red in the original board \( B \), satisfying the condition.

4. **Case 2:**
   - Suppose any pair of rows in \( B \) differs in at least two columns. This means we can color any single column red without making any two rows identical.
   - Choose one column arbitrarily and color it red. The remaining board now has dimensions \( m \times (n-1) \).
   - If \( m \leq n-1 \), by the induction hypothesis, we can color \( (n-1) - m + 1 = n - m \) more columns red, making a total of \( n - m + 1 \) red columns.
   - If \( m = n \), we only need to color one column red, which we have already done.

5. **Optimality:**
   - To show that \( n - m + 1 \) is the best possible, consider a board where the black squares are those whose row index is greater than the column index (i.e., all squares below a 45-degree diagonal line from a corner).
   - In this configuration, shading any of the first \( m-1 \) columns would make two rows identical. Therefore, at most \( n - (m-1) = n - m + 1 \) columns can be shaded red.

Thus, we have shown both that it is possible to color \( n - m + 1 \) columns red and that this is the maximum number of columns that can be colored red while ensuring no two rows have the same pattern.

The final answer is \( \boxed{ n - m + 1 } \).