IMO 2023 Shortlist C4
Let n ě 2 be a positive integer. Paul has a 1 ˆ n2 rectangular strip consisting of n2 unit squares, where the ith square...
Category: Combinatorics
Problem
Let n ě 2 be a positive integer. Paul has a 1 ˆ n2 rectangular strip consisting of n2 unit squares, where the ith square is labelled with i for all 1 ď i ď n2 . He wishes to cut the strip into several pieces, where each piece consists of a number of consecutive unit squares, and then translate (without rotating or flipping) the pieces to obtain an nˆn square satisfying the following property: if the unit square in the ith row and jth column is labelled with aij, then aij ´ pi ` j ´ 1q is divisible by n. Determine the smallest number of pieces Paul needs to make in order to accomplish this. (U.S.A.) 6 Chiba, Japan, 2nd–13th July 2023