MathDB

On a straight road, points

1, 2, \ldots, n

are marked. The distance between any two adjacent points is 1. A "placement" refers to the arrangement of

n

cars, numbered with the same numbers, at the marked points (there can be multiple cars at one point). The "distance" between two placements is defined as the minimum total length of sections that need to be paved so that cars from the first placement can drive on the asphalt, forming the second one (cars can change places on the road). Prove that for any

\alpha<1

, there exists an integer number

n

for which there are

100^n

placements, the pairwise distances between which are greater than

\alpha n

.
Proposed by Ilya Bogdanov

Problem Statement