MathDB

P3

Part of 2022 Serbia National Math Olympiad

Problems(1)

Combinatorics

Source: Serbian national olympiad 2022 P3

4/8/2022
The table of dimensions n×nn\times n, n∈Nn\in\mathbb{N}, is filled with numbers from 11 to n2n^2, but the difference any two numbers on adjacent fields is at most nn, and that for every k=1,2,…,n2k = 1, 2,\dots , n^2 set of fields whose numbers are 1,2,…,k1, 2,\dots , k is connected, as well as the set of fields whose numbers are k,k+1,…,n2k, k + 1,\dots , n^2. Neighboring fields are fields with a common side, while a set of fields is considered connected if from each field to every other field of that set can be reached going only to the neighboring fields within that set. We call a pair of adjacent numbers, ie. numbers on adjacent fields, good, if their absolute difference is exactly nn (one number can be found in several good pairs). Prove that the table has at least 2(n−1)2 (n - 1) good pairs.
combinatoricsnumbers in a tableSerbian competition