Modeling the number-filling problem in the 2025 THPTQG exam

1. Introduction#

In the 2025 THPTQG exam (Vietnam's national high school graduation exam), the Math paper included a rather novel number-filling problem that surprised many students. This problem also hides quite a bit of interesting structure - in this post, we'll model it together to see exactly where that interest lies.

The original problem asks for the probability that a random arrangement satisfies an arithmetic-progression requirement. In this post, however, we only care about finding every arrangement that satisfies the requirement.

So the problem can be restated in general form as follows: choose $2n$ numbers out of the $n^2$ numbers $\{1, 2, 3, ..., n^2\}$ and arrange them into a sequence at positions $\{0, 1, ..., n - 1\}$ such that every triple of numbers at positions $(2k, 2k + 1, 2k + 2)$ for $\forall k \in \{0, 1, ..., n - 2\}$ forms an arithmetic progression, and the triple at positions $(2n - 2, 2n - 1, 0)$ also forms an arithmetic progression.

2. Modeling the problem#

2.1. Decision variables#

For each position $i \in \{0, 1, ..., n - 1\}$ and each value $j \in \{1, 2, 3, ..., n^2\}$, define variable $x(i, j)$ such that

2.2. Constraints#

• Each position must be filled with a number

• Each number can be used at most once

• Each required triple of positions forms an arithmetic progression

2.3. Finding all solutions#

The model built above only gives us one solution. To find all remaining solutions, we use the following simple logic

BEGIN THPTQG2025
    initialize model M;
    solve M;
    S := solution of M;
    WHILE (M is not infeasible)
        add a constraint so that solution S no longer satisfies the model;
        solve M;
        S := solution of M;
    END
    Return S;
END

Where the constraint used to exclude a solution is as follows

Where $S$ is a solution of the model, of the form $\{(i, j)|i \in \{0, 1, ..., n - 1\}; j \in \{1, 2, 3, ..., n^2\}; \text{position } i \text{ is filled with number } j \}$