2019-04-01
1997 фишек расположены на плоскости в вершинах выпуклого 1997-угольника. За один ход можно разбить их на две группы и фишки первой группы сдвинуть на какой-нибудь вектор, а остальные фишки оставить на месте. Может ли случиться, что после а) 9; б) 10 ходов все фишки окажутся на одной прямой?
Решение:
а) Пусть число $n$ таково, что $2^n < N \leq 2^{n+1}$ ($N$ - число фишек). На каждой прямой лежит не более двух вершин выпуклого $N$-угольника (фишек). После первого хода на каждой прямой может оказаться не более четырёх фишек, после второго - не более 8, после $(n?1)$-го - не более $2n$. Таким образом, собраться на одной прямой фишки могут не менее чем через $n$ ходов. При $N = 1997$ можно взять $n = 10$ (1024 = 2^10 < 1997 \leq 2^11 = 2048)$.
б) Построить пример можно так. Пусть $N \leq 2^{n+1}$ (в частности,
для $N = 1997$ можно взять $n = 10$). Проведём $2^n$ параллельных прямых на равных расстояниях друг от друга и расположим на них фишки в вершинах выпуклого $N$-угольника, как показано на рис.
Сдвинув все фишки, лежащие на левой половине прямых на вектор $\vec{\upsilon}$ так, чтобы эти прямые совпали соответственно с прямыми правой половины (рис.), мы соберём все фишки на $2^{n?1}$ прямых, а через $n$ аналогичных шагов (со сдвигами на векторы $\vec{\upsilon}/2, \vec{\upsilon}/4$ и т. д.) все они соберутся на одной прямой.
Ответ: а) не может; б) может.