Sets, Inclusion-Exclusion and Configurations

Problems

Solutions

Solution: IOQM 2026, Q1

Number the rows and the columns from $1$ to $9$. Moving one square along a row or a column changes the colour and changes the sum of the two coordinates by one, so two squares share a colour exactly when their coordinate sums have the same parity. The centre is $(5, 5)$, with an even sum, so the white squares are those whose row and column numbers are both odd or both even.

Both odd: five choices of row and five of column, $25$ squares. Both even: four and four, $16$ squares. The number of white squares is $$25 + 16 = 41,$$ against $81 - 41 = 40$ black ones, so white is the colour with the square to spare.

Answer 41

Solution: IOQM 2026, Q12

Each row has seven squares and must hold an even number of checkers, so it holds at most six. The seven rows together hold at most $$7 \times 6 = 42.$$

Leave the seven squares of a diagonal empty and fill the other $42$. The diagonal meets every row once and every column once, so each row and each column has exactly six checkers, which is even. The largest number is $42$.

Answer 42

Solution: IOQM 2024, Q9

A knight-move pair is a pair of points differing by one of the vectors $$(\pm2, \pm1) \qquad \text{or} \qquad (\pm1, \pm2).$$ Since a pair is unordered, we may fix the sign of the first coordinate and count the four displacement types $$(2,1), \quad (2,-1), \quad (1,2), \quad (1,-2).$$

Take $(2,1)$. Its starting point $(a,b)$ needs $a \le 2$ so that $a + 2 \le 4$, and $b \le 3$ so that $b+1 \le 4$, giving $3 \cdot 4 = 12$ placements. Each of the other three types is a reflection of this one in a grid symmetry, so each also has $12$ placements.

Hence the number of knight-move pairs is $4 \cdot 12 = 48$.

Answer 48

Solution: IOQM 2025 Part SEP, Q7

The pairs required to differ are $AB$, $BC$, $CD$, $DA$ and $AC$. Read that as two triangles, $ABC$ and $ACD$, sharing the edge $AC$.

Colour $A$ first, in $4$ ways. Then $C$ must differ from $A$, giving $3$ ways. Now $B$ must differ from both $A$ and $C$, which are already different, so $2$ ways; and $D$ must likewise differ from $A$ and $C$, another $2$ ways, with no constraint between $B$ and $D$ since $BD$ is the diagonal that was left free.

Hence the count is $4 \cdot 3 \cdot 2 \cdot 2 = 48$.

Answer 48

Solution: IOQM 2025 Part SEP, Q28

Among $1, \ldots, 6$ the pairs that are not coprime are $$\{2,4\},\ \{2,6\},\ \{4,6\},\ \{3,6\}.$$ So $2$, $4$ and $6$ must pairwise occupy non-adjacent cells, and additionally $3$ must not sit next to $6$.

Colour the board like a chessboard. The two colour classes are $$\{(1,1), (1,3), (2,2)\} \qquad \text{and} \qquad \{(1,2), (2,1), (2,3)\},$$ and these are the only three-cell sets with no two cells adjacent. Indeed the two cells of a column are adjacent, so no column holds two chosen cells, and three cells in three columns then means exactly one per column; consecutive columns must use opposite rows, or their cells would be side by side, so the rows alternate and the set is one of the two above. So $2, 4, 6$ fill one class and $1, 3, 5$ the other, giving $2 \cdot 3! \cdot 3! = 72$ arrangements before the last condition.

Now remove those with $3$ next to $6$. Fix the class holding the evens, place $6$, and count. In either class one cell has three neighbours in the other class and the other two cells have two each. With $6$ on a cell of degree $\delta$, the number of bad arrangements is $$\underbrace{2}_{\text{placing } 2, 4} \times \underbrace{\delta}_{\text{cells for } 3} \times \underbrace{2}_{\text{placing } 1, 5} = 4\delta,$$ so the bad total for one class is $4(3 + 2 + 2) = 28$ out of its $36$ arrangements, leaving $8$. The other class behaves identically, so the answer is $$8 + 8 = 16.$$

Answer 16

Solution: IOQM 2025 Part SEP, Q7

The pair $\{1,2\}$ may go into any envelope except $1$ and $2$, so $4$ choices; likewise $\{3,4\}$ avoids envelopes $3$ and $4$, and $\{5,6\}$ avoids $5$ and $6$. Ignoring the requirement that the three envelopes be different, that is $4^3 = 64$ ways.

Now remove the clashes. If the pairs $\{1,2\}$ and $\{3,4\}$ share an envelope, that envelope must avoid $1, 2, 3, 4$, so it is $5$ or $6$: two choices, and the third pair still has its $4$, giving $2 \cdot 4 = 8$ cases. The same count applies to each of the other two coincidences, by the same reasoning with the labels shifted. All three pairs in one envelope is impossible, since no envelope avoids all six numbers.

By inclusion and exclusion the number of assignments with all three envelopes distinct is $$64 - 3 \cdot 8 = 40.$$

Answer 40

Solution: IOQM 2026, Q17

Put the three values in order as $p \le q \le r$. Whatever order $x$, $y$, $z$ take them in, the three distances are $q - p$, $r - q$ and $r - p$, whose sum is $$(q - p) + (r - q) + (r - p) = 2(r - p).$$ So the condition is $r - p = 4$: the largest and the smallest values differ by exactly $4$.

The smallest value $m$ has $m + 4 \le 8$, so $m$ is one of $1, 2, 3, 4$. With $m$ fixed, the triple takes values in $\{m, \ldots, m + 4\}$ and must use both ends. Of the $5^3 = 125$ ordered triples in that range, $4^3 = 64$ miss $m$ and $64$ miss $m + 4$, and $3^3 = 27$ miss both, so by inclusion and exclusion $$125 - 64 - 64 + 27 = 24$$ use both ends. Four choices of $m$ give $4 \times 24 = 96$ triples.

Answer 96

Solution: PRMO 2017, Q22

This question was discounted by the organisers, and the ambiguity is in the word polygons.

Under the first reading, a polygon means one of the regions into which the lines cut the plane. Three lines in general position form seven regions, just one of them bounded. On adding a fourth line, its three distinct intersections split it into four pieces, each of which splits an old region in two. The new total is therefore eleven. In general, line $k$ meets the previous $k-1$ lines in distinct points and adds $k$ regions. Starting from one region with no lines, ten lines in general position, no two parallel and no three concurrent, therefore cut the plane into $$1 + 10 + \binom{10}{2} = 56$$ regions. To count the unbounded ones, draw a circle large enough to contain every intersection. Each line crosses it twice, giving $20$ distinct crossing points and $20$ arcs between them. Each arc meets exactly one unbounded region, and every unbounded region meets one arc, so there are $20$ such regions. So the number of bounded regions is $$56 - 20 = 36,$$ which one can also write as $\binom{9}{2}$.

Under the second reading, a polygon is any closed figure with finite area whose sides lie along the given lines, whether or not it is a single region. Then every three lines already bound a triangle, so there are at least $\binom{10}{3} = 120$ polygons before quadrilaterals and larger figures are counted at all.

Both readings are natural, they give $36$ and something above $120$, and the paper offers no way to choose. That is why the question carries no answer.

Answer none

Solution: PRMO 2019, Q27

The word is $B\,H\,A\,R\,A\,T$, with the two $A$s in positions $3$ and $5$ and the four distinct letters $B, H, R, T$ in positions $1, 2, 4, 6$. A rearrangement has no fixed letters when no position holds the letter that was originally there.

Placing the $A$s

Neither $A$ may go into position $3$ or position $5$, so the two of them occupy two of the four positions $1, 2, 4, 6$. Since the $A$s are identical, that is a choice of a pair: $\binom{4}{2} = 6$ ways.

Placing the rest

Whichever pair the $A$s take, four positions remain for $B, H, R, T$: the two of $\{1,2,4,6\}$ left over, and positions $3$ and $5$. Positions $3$ and $5$ originally held $A$, so any of the four letters may go there. The two remaining positions from $\{1,2,4,6\}$ each forbid exactly one letter, and the two forbidden letters are different.

So we must count the ways of matching four letters to four positions, one letter each, avoiding two specified letter-position pairs. By inclusion-exclusion, $$4! - 2 \times 3! + 1 \times 2! = 24 - 12 + 2 = 14.$$

Multiplying the two independent choices, $$6 \times 14 = 84.$$

The reason this is so much easier than a general count of arrangements with nothing in its own place is that the repeated letter was handled first. Trying instead to run inclusion-exclusion over all six positions at once means tracking how many $A$s have been fixed, which works but takes three times the writing.

Answer 84

Solution: IOQM 2020, Q15

Number the seats $1, 2, 3$ across the front row and $4, 5, 6$ across the back, with seat $i$ directly in front of seat $i+3$. A couple is badly placed exactly when it occupies one of $$\{1,2\},\ \{2,3\},\ \{4,5\},\ \{5,6\} \quad \text{(same row, adjacent)},$$ $$\{1,4\},\ \{2,5\},\ \{3,6\} \quad \text{(same column)},$$ which is seven forbidden pairs. Counting the good arrangements directly means tracking three interacting restrictions at once, whereas counting the bad ones lets inclusion-exclusion do the bookkeeping. Let $A_i$ be the event that couple $i$ is badly placed, out of $6! = 720$ seatings.

One couple badly placed

Choose one of the seven forbidden pairs, seat that couple in it in $2$ ways, and arrange the remaining four people freely in $4! = 24$ ways, so $|A_i| = 7 \cdot 2 \cdot 24 = 336$ and the first sum is $3 \cdot 336 = 1008$.

Two couples badly placed

Now two of the seven pairs must be disjoint, since two couples cannot share a seat. The seven pairs meet the six seats with degrees $2, 3, 2, 2, 3, 2$ respectively, so the number of pairs of forbidden pairs that share a seat is $\sum \binom{d}{2} = 1+3+1+1+3+1 = 10$, leaving $\binom{7}{2} - 10 = 11$ disjoint pairs. Assigning them to the two couples in $2$ ways, ordering each couple in $2 \cdot 2$ ways, and seating the last two people in $2!$ ways gives $|A_i \cap A_j| = 11 \cdot 2 \cdot 4 \cdot 2 = 176$, so the second sum is $3 \cdot 176 = 528$.

All three couples badly placed

Here the three forbidden pairs must be disjoint and between them cover all six seats. Seat $1$ appears in only two forbidden pairs, $\{1,2\}$ and $\{1,4\}$, so split on which one is used.

If $\{1,2\}$ is used, seat $3$ is left, and its only other pair is $\{3,6\}$, since $\{2,3\}$ now clashes. Seats $4$ and $5$ remain, and $\{4,5\}$ is indeed forbidden, giving $\{1,2\}, \{3,6\}, \{4,5\}$.

If $\{1,4\}$ is used, seat $3$ takes $\{2,3\}$ or $\{3,6\}$. The first leaves seats $5, 6$, and $\{5,6\}$ is forbidden, giving $\{1,4\}, \{2,3\}, \{5,6\}$. The second leaves seats $2, 5$, and $\{2,5\}$ is forbidden, giving $\{1,4\}, \{3,6\}, \{2,5\}$.

Every branch closed, so there are exactly three coverings. Assigning these to the couples in $3!$ ways and ordering within each couple in $2^3$ ways gives $3 \cdot 6 \cdot 8 = 144$.

Inclusion-exclusion now yields $1008 - 528 + 144 = 624$ bad seatings, so the number of acceptable arrangements is $720 - 624 = 96$.

Answer 96

Solution: IOQM 2021 Part A, Q11

The seats are identical, so two seatings that differ by a rotation are the same seating. The tidiest way to handle that is to place the men first and let them absorb the symmetry. Four men arranged in a circle up to rotation can be done in $(4-1)! = 3! = 6$ ways.

Once the men are down, the four women must occupy the four gaps between consecutive men, which is what makes the seats alternate. Number the men $M_1, M_2, M_3, M_4$ round the circle and number the gaps so that gap $i$ lies between $M_i$ and $M_{i+1}$, indices read cyclically. Wife $W_i$ may not sit next to her own husband, so she is barred from gaps $i-1$ and $i$, which leaves her the other two: $$\begin{array}{c|c} \text{wife} & \text{gaps she may use} \\ \hline W_1 & 2, 3 \\ W_2 & 3, 4 \\ W_3 & 4, 1 \\ W_4 & 1, 2 \end{array}$$

Two gaps each is few enough to settle by looking at $W_1$. If $W_1$ takes gap $2$, then gap $2$ is gone, so $W_4$ must take gap $1$; that closes gap $1$, so $W_3$ must take gap $4$; and $W_2$ is left with gap $3$. If instead $W_1$ takes gap $3$, the same chain forces $W_2$ to gap $4$, then $W_3$ to gap $1$, then $W_4$ to gap $2$. So there are exactly two seatings of the wives, $$(W_1, W_2, W_3, W_4) \mapsto (2,3,4,1) \qquad \text{and} \qquad (3,4,1,2),$$ and both are legal.

Multiplying the two independent choices, the number of seatings is $6 \times 2 = 12$.

Answer 12

Solution: IOQM 2023, Q16

Of the $\binom63 = 20$ triangles $A_iA_jA_k$, most are free. If two of the three chosen vertices are neighbours on the hexagon, the side joining them is a side of the hexagon, which is red, and the triangle is satisfied whatever we do. So the only triangles that impose anything are those whose three vertices are pairwise non-adjacent, and in a hexagon there are exactly two such triples, $$\{A_1, A_3, A_5\} \qquad \text{and} \qquad \{A_2, A_4, A_6\}.$$

Their sides are the six short diagonals, three for each triangle, and the two sets of three do not overlap. The hexagon’s three long diagonals $A_1A_4$, $A_2A_5$, $A_3A_6$ appear in neither, so they may be coloured freely.

Counting is now immediate. Each of the two triangles must avoid being all blue, which rules out $1$ of the $2^3 = 8$ colourings of its three sides, leaving $7$; the choices for the two triangles are independent because they share no diagonal; and the three long diagonals contribute a factor $2^3 = 8$. Hence $$N = 7 \cdot 7 \cdot 8 = 392,$$ and the sum of the squares of the digits is $3^2 + 9^2 + 2^2 = 9 + 81 + 4 = 94$.

Answer 94

Solution: IOQM 2024, Q19

Suppose some point $V$ had three red edges, to $X$, $Y$, $Z$. If any of $XY$, $YZ$, $ZX$ were red it would close a red triangle with $V$; and if all three were blue then $XYZ$ would be a blue triangle. Either way a monochromatic triangle appears. The same argument applies with the colours exchanged, so at each of the five points exactly two of the four edges are red and two are blue.

So the red edges form a graph on five vertices in which every vertex has degree two, that is, a disjoint union of cycles covering all five vertices. The only possibility is a single cycle of length five, since a shorter cycle would leave two or fewer vertices to carry a cycle of their own, and cycles need at least three vertices. The blue edges are then the complementary five edges, which also form a five-cycle, namely the "pentagram" of the red one.

Conversely, if the red edges form a five-cycle, no red triangle exists (a triangle would need three mutually adjacent vertices on a five-cycle) and neither does a blue one, by the same argument applied to the complementary five-cycle.

So the colourings correspond exactly to the five-cycles through the five points, and the number of these is $$\frac{4!}{2} = 12,$$ since a cycle can be written starting from a fixed vertex in $4!$ orders, and each cycle is counted twice, once in each direction.

Answer 12

Solution: IOQM 2025 Part SEP, Q28

Describe the situation by recording, for each of the four stories, the set of girls who like it. Since no story is liked by all three girls, each story gets one of the $2^3 - 1 = 7$ subsets other than $\{G_1,G_2,G_3\}$. Without further conditions there are $7^4$ possibilities.

The remaining requirement is that each of the three two-girl subsets $\{G_1,G_2\}$, $\{G_1,G_3\}$, $\{G_2,G_3\}$ is the label of at least one story, since a story liked by exactly that pair is a story liked by the pair and not by the third girl.

The requirement is that all three of those labels appear. Inclusion and exclusion applies with the three labels as the forbidden things: $$n = \sum_{j=0}^{3}(-1)^j\binom3j (7-j)^4 = 7^4 - 3 \cdot 6^4 + 3 \cdot 5^4 - 4^4.$$ Evaluating, $$n = 2401 - 3888 + 1875 - 256 = 132,$$ and the sum of the squares of the digits is $1 + 9 + 4 = 14$.

Answer 14

Solution: IOQM 2026, Q26

Every point has three red segments, so $n \ge 4$, and each point has $n - 4$ blue ones.

Fix a point $B$ and a red neighbour $A$ of it. For every $C$ with $BC$ blue, condition (a) makes $AC$ red. So $A$ has red segments to $B$ and to all $n - 4$ blue neighbours of $B$, which is $n - 3$ red segments. There are only three, so $n \le 6$.

$n = 4$. Every segment is red, so (a) never applies, and each point has three red segments. This works.

$n = 5$. Each point has exactly one blue segment, so the blue segments pair off the five points, which is impossible for an odd number of points.

$n = 6$. Split the points into two groups of three. Colour segments inside a group blue and segments between groups red. Each point has three red segments, to the other group. If $AB$ is red then $A$ and $B$ are in different groups, and if $BC$ is blue then $C$ is in $B$’s group, so $A$ and $C$ are in different groups and $AC$ is red. This works.

The possible values are $4$ and $6$, and their sum is $10$.

Answer 10

Solution: PRMO 2018, Q26

Two choices of sixty squares are easy to find, and between them they account for sixty-two selections. Everything after that is one long argument that there is nothing else, so it is worth knowing in advance that the target is $62$ and that the work lies entirely in the uniqueness.

Colour the board like a chessboard, calling a square black when its row and column numbers have the same parity. There are $36 + 25 = 61$ black squares and $60$ white ones, and no two squares of the same colour share a side.

Two families that work

Any $60$ of the $61$ black squares form a legal choice, which is $\binom{61}{60} = 61$ ways. So do all $60$ white squares, for one more. The claim is that there is nothing else, making $62$.

Rows and columns cannot do better than six

In a single row of eleven squares, no two chosen squares are adjacent, so at most six are chosen; and six is possible only by taking columns $1, 3, 5, 7, 9, 11$. Call a row full when it holds six. The same statement holds for columns, with rows in place of columns.

Since the eleven rows hold $60$ squares in all and no row holds more than six, the total shortfall $\sum_i (6 - r_i)$ is exactly $6$. Every row that is not full contributes at least $1$, so at most six rows are not full: at least five rows are full. The same argument gives at least five full columns.

Full rows and full columns have the same parity

Suppose row $i$ is full, so the chosen squares of that row sit exactly in the odd columns, and suppose column $j$ is full, so the chosen squares of that column sit exactly in the odd rows. Look at the square $(i,j)$. The row says it is chosen exactly when $j$ is odd; the column says it is chosen exactly when $i$ is odd. So $i$ and $j$ have the same parity.

Since at least one full column exists, all full rows share its parity, and so all full rows have the same parity as each other.

The even case gives the white squares

If the full rows are even-numbered there are only five of them available, so all of $2, 4, 6, 8, 10$ are full, and likewise all of the columns $2, 4, 6, 8, 10$. The full even rows contribute the $30$ squares (even row, odd column), the full even columns contribute the $30$ squares (odd row, even column), and these are all white and all distinct. That is already $60$ squares, so the choice is exactly the white class.

The odd case gives the black squares

Otherwise the full rows are odd-numbered. If all six odd rows are full, they contribute the $36$ squares (odd, odd). Each even row then lies between two full rows, so its squares must avoid the odd columns, leaving at most the five even columns; the five even rows therefore contribute at most $25$, and to reach $60$ they contribute $24$. So the choice is every black square but one.

If instead exactly five odd rows are full, then the six remaining rows, namely the five even rows and one odd row $t$, each fall short by exactly one, so each holds five squares. Every even row still has a full odd neighbour, so it is confined to the even columns and takes all five of them, which are black. Row $t$ is odd, so its neighbours in the board are even rows, and it has at least one of them, namely row $2$ if $t = 1$, row $10$ if $t = 11$, and both otherwise. That neighbour occupies every even column, so row $t$ can use none of them: it is confined to the odd columns and takes five of those six. Again the choice is every black square but one.

The count

Every legal choice of $60$ is therefore all the white squares, or all but one of the black squares: $$1 + 61 = 62.$$

Answer 62

Solution: IOQM 2020, Q27

The bug moves only horizontally and vertically, so the length of a path is measured by the taxicab distance, and the shortest route from $A = (-3,2)$ to $B = (3,-2)$ has length $6 + 4 = 10$. A lattice point $P$ lies on some path from $A$ to $B$ of length at most $14$ precisely when going via $P$ costs at most $14$, that is when $$d(A,P) + d(P,B) \leq 14,$$ and any such detour can always be realised as an actual staircase path. The parity looks after itself, since $d(A,P) + d(P,B)$ always has the same parity as $10$.

Now write out that condition for $P = (x,y)$: $$|x+3| + |x-3| + |y-2| + |y+2| \leq 14.$$ The two halves separate, and each is a familiar shape. The sum $|x+3| + |x-3|$ equals $6$ whenever $x$ lies between $-3$ and $3$, and equals $2|x|$ outside that range, so it is $g(x) = \max(6, 2|x|)$. Likewise $|y-2|+|y+2|$ is $h(y) = \max(4, 2|y|)$. The condition is $g(x) + h(y) \leq 14$, and since $g$ is at least $6$ and $h$ at least $4$ there is not much room.

Work through the possible values of $g$. When $g = 6$, which happens for the seven values $x = -3, \ldots, 3$, we need $h(y) \leq 8$, and that allows $|y| \leq 4$, giving nine values of $y$ and so $63$ points. When $g = 8$, at $x = \pm 4$, we need $h(y) \leq 6$, allowing $|y| \leq 3$, which is seven values and $14$ points. When $g = 10$, at $x = \pm 5$, we need $h(y) \leq 4$, allowing only $|y| \leq 2$, which is five values and $10$ points. When $g \geq 12$ we would need $h(y) \leq 2$, which is impossible since $h$ is never less than $4$.

The total is $63 + 14 + 10 = 87$.

Answer 87

Solution: IOQM 2023, Q18

Throughout, $n = 50$. The one fact we need first is that a set of pairwise non-crossing diagonals of a convex $n$-gon has at most $n - 3 = 47$ members.

Why a non-crossing family has at most $n-3$ members

Keep adding non-crossing diagonals until no more can be added. Every region is then a triangle, since a region with four or more vertices admits another diagonal. Say the final set has $D$ diagonals and cuts the polygon into $T$ triangles. Each diagonal, when it was drawn, split one region into two, so the number of regions rose by one each time and $$T = D + 1.$$ Now count the sides of the triangles. Each of the $n$ edges of the polygon lies on exactly one triangle, and each diagonal lies on exactly two, so $$3T = n + 2D.$$ Substituting $T = D+1$ gives $3D + 3 = n + 2D$, that is $D = n - 3$. The original set was part of this one, so it had at most $n-3$ diagonals.

The upper bound

Let $\mathcal F$ be minimally friendly and let $c$ be the number of crossing pairs inside it. Since each diagonal meets at most one other, these pairs are disjoint: they form a matching. Delete one diagonal from each pair. What is left is pairwise non-crossing, so $$|\mathcal F| - c \le 47, \qquad \text{that is} \qquad |\mathcal F| \le 47 + c.$$

It remains to bound $c$, and this is where the structure appears. Take one crossing pair, with diagonals $PR$ and $QS$ meeting inside, where $P, Q, R, S$ occur in this cyclic order. These two diagonals cut the polygon into four regions, one containing each of the four arcs $PQ$, $QR$, $RS$, $SP$. Now take any other crossing pair. Neither of its diagonals may cross $PR$ or $QS$, so each lies inside one of the four regions; and since the two of them cross each other, they lie in the same region. So every other crossing pair sits inside one of the four regions.

Let $g(m)$ be the largest possible number of crossing pairs when the available vertices number $m$, and let us show $$g(m) \le \left\lfloor \frac{m-2}{2} \right\rfloor \qquad (m \ge 2),$$ We use induction on $m$. The claim holds for $m\le3$ because then $g(m)=0$. For larger $m$, if there is no crossing pair the bound is already true. Otherwise pick one crossing pair as above. Each of its four regions excludes two of the four selected endpoints, so it has at most $m-2$ original vertices. The induction hypothesis therefore applies inside every region. If the four regions have $m_1, m_2, m_3, m_4$ available vertices, then $m_1 + m_2 + m_3 + m_4 = m + 4$, because each of $P, Q, R, S$ is available to two of the regions. Hence, dropping the floors on the right, $$g(m) \le 1 + \sum_{i=1}^{4} g(m_i) \le 1 + \sum_{i=1}^{4} \frac{m_i-2}{2} = 1 + \frac{m+4-8}{2} = \frac{m-2}{2}.$$ The left side is a whole number, so it is at most $\lfloor (m-2)/2 \rfloor$, as claimed. With $m = 50$ this gives $c \le \lfloor 48/2 \rfloor = 24$, and therefore $$|\mathcal F| \le 47 + 24 = 71.$$

The construction

Triangulate the $50$-gon in a zigzag, drawing the diagonals $$A_2A_{50},\ A_2A_{49},\ A_3A_{49},\ A_3A_{48},\ A_4A_{48},\ \ldots$$ so that the $48$ triangles form a chain, each sharing an edge with the next. That is $47$ diagonals, pairwise non-crossing.

Now pair the triangles along the chain: the first with the second, the third with the fourth, and so on, giving $24$ pairs. Each pair forms a convex quadrilateral whose two triangles share a diagonal of the triangulation. Add the other diagonal of that quadrilateral. It is a genuine diagonal of the $50$-gon, since a quadrilateral inscribed in the polygon has two vertices strictly between the endpoints of each of its diagonals. It stays inside its own quadrilateral, so it meets no added diagonal from another pair and no triangulation diagonal other than the original shared diagonal of that quadrilateral.

The result has $47 + 24 = 71$ diagonals, each meeting at most one other, so the largest possible size is exactly $$|\mathcal F| = 71.$$

Answer 71

Solution: IOQM 2025 Part SEP, Q7

Only $n = 1$ fails, and it fails immediately: the single pair is $\{1,2\}$ and the product is $3$, not a square.

For even $n$, pair each $k$ with $2n+1-k$. Every pair sums to $2n+1$, so the product of the sums is $(2n+1)^n$, which is a perfect square because $n$ is even.

For odd $n \ge 3$, handle the first six numbers by hand. The pairing $$\{1,5\},\quad \{2,4\},\quad \{3,6\}$$ gives sums $6, 6, 9$ and product $324 = 18^2$. The remaining numbers are $7, 8, \ldots, 2n$, an even block, and pairing $k$ with $2n+7-k$ makes every one of those $n-3$ sums equal to $2n+7$. As $n$ is odd, $n - 3$ is even, so that part of the product is $(2n+7)^{n-3}$, a perfect square. The whole product is a square times a square.

So every $n$ from $2$ to $37$ works and only $n = 1$ does not, giving $$37 - 1 = 36$$ values.

Answer 36