Alice drew a regular $2021$-gon in the plane. Bob then labeled each vertex of the $2021$-gon with a real number, in such a way that the labels of consecutive vertices differ by at most $1$. Then, for every pair of non-consecutive vertices whose labels differ by at most $1$, Alice drew a diagonal connecting them. Let $d$ be the number of diagonals Alice drew. Find the least possible value that $d$ can obtain.
Problem
Source: 10th European Mathematical Cup - Problem S1
Tags: combinatorics, minimum value, European Mathematical Cup, emc
22.12.2021 21:14
22.12.2021 21:14
I think this problem is quite tricky for a P1, but it's really cool nonetheless.
22.12.2021 23:53
Great problem. Here's a proof of the bound. The answer is $n-3$. The idea is to prove it by induction: remove the biggest number, and note that it's neighbors have difference smaller than $1$, so the new polygon satisfies the conditions, so using the inductive hypothesis and adding the pair of neighbors to the count of the diagonals finishes. Remark: The idea to induct by removing the biggest number when we have numbers on a circle appears also here: https://artofproblemsolving.com/community/c6h598545p3551877 (it's a totally different problem, but the general idea is similar)