How many ways can four vertices be chosen from the vertices of a convex $n$-gon so that the sides of the convex quadrilateral determined by them are diagonals of the $n$-gon?
I. Solution. Let us denote the vertices of the given convex $n$-gon (in positive order) by the numbers $1, 2, \ldots, n$. Each set of four vertices that meets the requirement corresponds to a set of four numbers where

A) there are no adjacent (with a difference of 1) pairs of numbers,

B) the numbers 1 and $n$ do not appear together.

(Indeed, the appearance of adjacent numbers, or the simultaneous appearance of 1 and $n$, would mean that one of the sides of the chosen quadrilateral is also a side of the polygon.) Conversely, every such set of four numbers corresponds to a set of four vertices that meet the original requirement. Therefore, the number of such vertex quadrilaterals is given by the number of sets of four numbers that have properties $A$ and $B$. This latter number can be determined by subtracting the number of sets of four numbers that have property $A$ but not property $B$ from the number of sets of four numbers that have property $A$.

The number $N(A)$ is essentially the same problem as the 2nd problem of the 1970 Kürschák competition, 1 with the number of lottery numbers 90 replaced by $n$, and the number of lottery numbers drawn at once 5 replaced by 4. We apply the reasoning of the first solution given in the cited place with these changes.

Let us denote the numbers of a properly chosen set of four numbers in increasing order by $a$, $b$, $c$, and $d$, so the validity of the set is equivalent to the inequality chain

$$
1 \leqq a < a+1 < b < b+1 < c < c+1 < d \leqq n
$$

Thus, with the notation

$$
b' = b-1, \quad c' = c-2, \quad d' = d-3
$$

the inequality chain

$$
1 \leqq a < b' < c' < d' \leqq n-3
$$

also holds. Conversely, if the numbers $a, b', c', d'$ satisfy (3), then the numbers $a, b, c, d$ derived from them according to (2) satisfy (1). Therefore, $N(A)$ is equal to the number of sets of four numbers that satisfy (3), or the number of sets of four different numbers (arranged in monotonically increasing order) that can be chosen from the first $(n-3)$ natural numbers:

$$
N(A) = \binom{n-3}{4}
$$

If a set of four numbers has property $A$ but not property $B$, then the set contains the numbers 1 and $n$, and for the other two elements

$$
3 \leqq b < b+1 \leqq n-2
$$

holds, where $b$ and $c$ denote these elements. The number of pairs of numbers that satisfy (4) can be determined similarly to the above, yielding

$$
N(A \bar{B}) = \binom{n-5}{2}
$$

Thus, the number of sets of four numbers that have properties $A$ and $B$ is

$$
\begin{gathered}
N(AB) = N(A) - N(A \bar{B}) = \binom{n-3}{4} - \binom{n-5}{2} = \\
= \frac{(n-3)(n-4)(n-5)(n-6)}{4!} - \frac{(n-5)(n-6)}{2!} = \\
= \frac{(n-5)(n-6)}{4!} \left(n^2 - 7n + 12 - 12\right) = \frac{n}{4} \binom{n-5}{3}
\end{gathered}
$$

Remarks. 1. Our result is valid in terms of content (both geometrically and in terms of the computational reasoning) only for the cases $n \geqq 8$. For $n=8$, $N=2$, one solution is the selection of the vertices with odd numbers, the other is the selection of the vertices with even numbers. However, the formula gives the correct result even for $n=5$.

2. We can reach the goal somewhat faster based on the following idea. Let the vertices of the quadrilateral determined by the selected set of four vertices be denoted by $P$, $Q$, $R$, and $S$ (in positive order). First, choose the vertex $P$ from the vertices of the $n$-gon (we have $n$ ways to do this), then number the vertices of the polygon starting from $P$ in positive order. It can be easily shown by the above reasoning that we have $\binom{n-5}{3}$ ways to choose the remaining three vertices, thus we get $n \binom{n-5}{3}$ quadrilaterals. However, in this way, each quadrilateral is counted 4 times - we can label its vertices in 4 ways in positive order with the letters $P, Q, R, S$ - so the number of different quadrilaterals is $\frac{n}{4} \binom{n-5}{3}$.

II. Solution. The vertices of the $n$-gon determine $\binom{n}{4}$ convex quadrilaterals, among which there are also those that have 3, 2, or 1 side in common with the $n$-gon. (All 4 sides could only be $n$-gon sides if $n=4$, but we ignore this and focus on the cases $n \geqq 8$.) We determine the number of these cases of coincidence and form the desired number $N$ by subtraction.

a) A quadrilateral has 3 sides in common with the $n$-gon if we select 4 consecutive vertices. This means we only choose the first one - which we can do in $n$ ways - and the other 3 follow.

b) If 2 sides are in common, these can be 2 adjacent - or 3 consecutive - sides of the $n$-gon, or 2 more distant sides. In the first case, the 3 consecutive vertices can be chosen in $n$ ways, but the fourth vertex of the quadrilateral cannot be adjacent to these, so it can be chosen from $(n-5)$ vertices of the $n$-gon; the number of such possibilities is therefore $n(n-5)$. In the second case, we will have two pairs of adjacent vertices on the $n$-gon. The first pair's first vertex can again be chosen in $n$ ways, and the second pair's first vertex in $(n-5)$ ways (if, for example, the first pair is $A_{n-1}, A_{n}$, then the first vertex of the second pair can be $A_{2}, A_{3}, \ldots, A_{n-4}$). In the thus thought $n(n-5)$ connections, however, each desired selection is obtained twice, so the number of such quadrilaterals is $n(n-5) / 2$.

c) Finally, if a quadrilateral has 1 side in common with the $n$-gon, then after selecting this, the remaining 2 vertices of the quadrilateral can be chosen from the remaining $(n-4)$ vertices in $\binom{n-4}{2}$ ways, but in $n-5$ cases these are adjacent to each other, so the number of quadrilaterals belonging to this is:

$$
n \left\{ \binom{n-4}{2} - (n-5) \right\} = n \binom{n-4}{2} - n(n-5)
$$

According to all this,

$$
N = \left( \frac{n}{4} \right) - \left\{ n + \left( 1 + \frac{1}{2} - 1 \right) n(n-5) - n \binom{n-4}{2} \right\}
$$

which, after appropriate rearrangement, agrees with the result of the first solution.


[^0]:    ${ }^{1}$ What is the probability that among the five numbers drawn in a lottery, there are at least two adjacent numbers (with a difference of 1)? - See the solution in: László Lovász: Solution to the problems of the 1970 József Kürschák Mathematical Student Competition. K. M. L. 42 (1971) 193 - 198, specifically on pages $195-197$.