Решения: Городские олимпиады, Олимпиада города Алматы (Мусабаевская)

Городская олимпиада по математике среди физ-мат школ г. Алматы, 2017 год

Дан выпуклый n-угольник

M

$M$ . Пусть

k

$k$ – наименьшее число точек, которое можно отметить внутри

M

$M$ так, чтобы внутри любого пятиугольника, вершины которого являются вершинами

M

$M$ , оказалось ровно 3 точки из отмеченных. Докажите, что

k \geq n - 2

$k\ge n-2$ . («внутри» означает строго внутри, не на границе) ( Ильясов С. )

посмотреть в олимпиаде

Комментарий/решение:

Комментарии от администратора Комментарии от администратора №1.
Любой $n=3m+2$ -угольник, $m\ge 2$ , можно разбить на выпуклые пятиугольники, что легко можно видеть на примере 11-угольника. Каждый следующий 5-угольник после первого использует 2 уже задействованные вершины и 3 новые. Тогда количество пятиугольников равно $1+\frac{3m+2-5}{3}=m$ . Тогда $k\ge 3m=n-2$ .

Любой

n = 3 m + 3

$n=3m+3$ -угольник,

m \geq 2

$m\ge 2$ , можно разбить на треугольник и

3 m + 2

$3m+2$ -угольник. Значит,

k \geq 3 m = n - 3

$k\ge 3m=n-3$ . Если хотя бы один из треугольников, состоящих из трех подряд идущих вершин, содержит хотя бы одну точку (возможно даже на ребре внутри