MathDB
Problems
Contests
International Contests
Kvant Problems
Kvant 2024
M2785
M2785
Part of
Kvant 2024
Problems
(1)
Counting polylines
Source: Kvant Magazine No. 2 2024 M2785
5/2/2024
A finite set
S
S{}
S
of
n
n{}
n
points is given in the plane. No three points lie on the same line. The number of non-self-intersecting closed
n
n{}
n
-link polylines with vertices at these points will be denoted by
f
(
S
)
.
f(S).
f
(
S
)
.
Prove that[*]
f
(
S
)
>
0
f(S)>0
f
(
S
)
>
0
for all sets
S
;
S{};
S
;
[*]
f
(
S
)
=
1
f(S)=1
f
(
S
)
=
1
if and only if all the points of
S
S{}
S
lie on the convex hull of
S
;
S{};
S
;
[*]if
f
(
S
)
>
1
f(S)>1
f
(
S
)
>
1
then
f
(
S
)
⩾
n
−
1
f(S)\geqslant n-1
f
(
S
)
⩾
n
−
1
, with equality if and only if one point of
S
S
S
lies inside the convex hull; [*]if exactly two points of
S
S{}
S
lie inside the convex hull, then
f
(
S
)
⩾
(
n
−
2
)
(
n
−
3
)
2
.
f(S)\geqslant\frac{(n-2)(n-3)}{2}.
f
(
S
)
⩾
2
(
n
−
2
)
(
n
−
3
)
.
Let
n
⩾
3.
n\geqslant 3.
n
⩾
3.
Denote by
F
(
n
)
F(n)
F
(
n
)
the largest possible value of the function
f
(
S
)
f(S)
f
(
S
)
over all admissible sets
S
S{}
S
of
n
n{}
n
points. Prove that
F
(
n
)
⩾
3
⋅
2
(
n
−
8
)
/
3
.
F(n)\geqslant3\cdot 2^{(n-8)/3}.
F
(
n
)
⩾
3
⋅
2
(
n
−
8
)
/3
.
Proposed by E. Bakaev and D. Magzhanov
combinatorics
geometry