Maths Olympiad Prep

Library / /20 of 27

Geometry Difficulty 7.2 National olympiad, round 2 Find the answer

Let n>5n>5 be an integer. There are nn points in the plane, no three of them collinear. Each day, Tom erases one of the points, until there are three points left. On the ii-th day, for 1<i<n31<i<n-3, before erasing that day's point, Tom writes down the positive integer v(i)v(i) such that the convex hull of the points at that moment has v(i)v(i) vertices. Finally, he writes down v(n2)=3v(n-2) = 3. Find the greatest possible value that the expression
v(1)v(2)+v(2)v(3)++v(n3)v(n2)|v(1)-v(2)|+ |v(2)-v(3)| + \ldots + |v(n-3)-v(n-2)|
can obtain among all possible initial configurations of nn points and all possible Tom's moves.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given an integer n>5 n > 5 , there are n n points in the plane with no three collinear. Tom sequentially erases a point each day until only three points remain. On the i i -th day (1<i<n3 1 < i < n-3 ), he notes a positive integer v(i) v(i) representing the number of vertices in the current convex hull. Finally, v(n2)=3 v(n-2) = 3 when only three points remain. We aim to find the greatest possible value of the expression:

v(1)v(2)+v(2)v(3)++v(n3)v(n2). |v(1)-v(2)|+ |v(2)-v(3)| + \ldots + |v(n-3)-v(n-2)|.

### Solution Approach

1. Initial Setup:
- Initially, the convex hull can have at most n n vertices.
- Reducing the number of points step by step affects the vertices of the convex hull.

2. Understanding Convex Hull Changes:
- Removing a point from inside the convex hull does not change the number of vertices.
- Removing a point from the boundary reduces the vertex count by at least 1.

3. Maximizing the Expression:
- Begin with the maximal convex hull having all n n points as vertices, i.e., v(1)=n v(1) = n .
- Gradually remove the points strategically so that the convex hull loses its vertices one by one, ideally decreasing the vertex count by 1 each day.
- You will thus achieve a maximum change in the convex hull vertices each day, resulting in the expression v(i)v(i+1)=1 |v(i) - v(i+1)| = 1 maximized wherever possible.

4. Expression Calculation:
- The sequence of vertex counts could be as simple as decreasing the hull by 1 vertex per day: n,n1,n2,,4,3 n, n-1, n-2, \ldots, 4, 3 .
- The expression becomes:
(n)(n1)+(n1)(n2)++43 |(n) - (n-1)| + |(n-1) - (n-2)| + \ldots + |4 - 3|
- The number of terms in the expression is n4 n - 4 , with each term equaling 1, giving a sum:
(n4)×1=n4 (n-4) \times 1 = n-4

5. Ensuring Maximum Value:
- Each day except the very last when 3 3 vertices are expected, has differences yielding 1 1 , ensuring maximum configuration is used.
- Subtract 1 1 for each day's reduction starting at n n until reaching v(n2)=3 v(n-2) = 3 .

Thus, the greatest possible value that the expression can obtain is:

2n8 \boxed{2n - 8}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.