В таблице m строк, n столбцов. Горизонтальным ходом называется такая перестановка элементов таблицы, при которой каждый элемент остаётся в той строке, в которой он был и до перестановки; аналогично определяется вертикальный ход ("строка" в предыдущем определении заменяется на "столбец"). Укажите такое k, что за k ходов (любых) можно получить любую перестановку элементов таблицы, но существует такая перестановка, которую нельзя получить за меньшее число ходов.

   Решение

Тема:    [ Переведем данную прямую на бесконечность ]

Сложность: 7 Классы: 10,11

Прислать комментарий

Условие

Докажите, что для любого нечетного n3 на плоскости можно указать 2n различных точек, не лежащих на одной прямой, и разбить их на пары так, чтобы любая прямая, проходящая через две точки из разных пар, проходила бы еще через одну из этих 2n точек.

Решение

Пусть A₁...A_n — правильный n-угольник, l_i — прямая, содержащая его сторону, противоположную вершине A_i, B_i — точка пересечения прямой l_i с бесконечно удаленной прямой. Разобьем точки A₁,..., A_n, B₁,..., B_n на пары (A_i, B_i). Покажем, что это разбиение обладает требуемым свойством. Для этого нужно рассмотреть прямые B_iB_j, A_iA_j и A_iB_j (ij).
1) Прямая B_iB_j содержит все точки B₁,..., B_n. Поскольку n3, среди них есть точка, отличная от B_i и B_j.
2) Прямая A_iA_j параллельна одной из прямых l_k, поскольку число n нечетно. Следовательно, прямая A_iA_j проходит через точку B_k.
3) Если ij, то прямая, проходящая через вершину A_i параллельно прямой l_j, содержит некоторую вершину A_k, ki. Поэтому прямая A_iB_j проходит через точку A_k.
Применив к набору точек A₁,..., A_n, B₁,..., B_n проективное преобразование, можно добиться, чтобы все эти точки не были бесконечно удаленными.

Источники и прецеденты использования