Выбрано 6 задач 
Убрать все задачи
Доказать, что существует бесконечно много натуральных чисел, не представимых в виде p + n2k ни при каких простых p и целых n и k.
AB и AC — две хорды, образующие угол BAC, равный
70o.
Через точки B и C проведены касательные до пересечения в точке M.
Найдите
BMC.
Постройте хорду данной окружности, равную и параллельную заданному отрезку.
Петя и Вася играют в игру на клетчатой доске n×n (где n > 1). Изначально вся доска белая, за исключением угловой клетки – она чёрная, и в ней стоит ладья. Игроки ходят по очереди. Каждым ходом игрок передвигает ладью по горизонтали или вертикали, при этом все клетки, через которые ладья перемещается (включая ту, в которую она попадает), перекрашиваются в чёрный цвет. Ладья не должна передвигаться через чёрные клетки или останавливаться на них. Проигрывает тот, кто не может сделать ход; первым ходит Петя. Кто выиграет при правильной игре?
Что останется от прямоугольника?
Золотой прямоугольник — это такой прямоугольник, стороны a и
b которого находятся в пропорции золотого сечения,
то есть удовлетворяют равенству
a : b = b : (a - b). Представим, что такой прямоугольник вырезан из
бумаги и лежит на столе, обращенный к нам своей более длинной
стороной. Отсечем по левую сторону прямоугольника наибольший
квадрат, который можно из него вырезать; остаток будет снова
золотым прямоугольником. Далее становимся по левую сторону стола
так, чтобы снова иметь перед собой более длинную сторону и
поступаем с новым прямоугольником так же, как и с предыдущим.
Таким образом обходим стол вокруг по направлению хода часовой
стрелки и по очереди отсекаем квадраты. Каждая точка
прямоугольника за исключением одной, будет раньше или позже
отсечена. Определите положение этой исключительной точки.
На плоскости дано множество S, состоящее из чётного числа точек, никакие три из которых не лежат на одной прямой.
Докажите, что S можно разбить на два множества X и Y так, что выпуклые оболочки conv X и conv Y имеют поровну вершин.
|
|
 |
Условие
На плоскости дано множество S, состоящее из чётного числа точек, никакие три из которых не лежат на одной прямой.
Докажите, что S можно разбить на два множества X и Y так, что выпуклые оболочки conv X и conv Y имеют поровну вершин.
Решение
Обозначим через k(X) число вершин выпуклой оболочки conv X множества X.
Пусть A = A1A2...An = conv S, а T – множество всех точек из S, лежащих строго внутри A. Рассмотрим множества Xi = {A1, ..., Ai} ∪ T,
Yi = {Ai+1, ..., An}.
Найдём наименьшее i, для которого k(Xi) ≥ k(Yi). Очевидно, i < n. Если i = 0, можно выбрать такое подмножество T' ⊂ T, что k(T') = n (исключая точки из T по одной). Тогда T' и S \ T' – искомое разбиение.
Пусть 1 ≤ i ≤ n – 1. В силу минимальности i k(Xi) – 1 ≤ k(Xi–1) ≤ k(Yi–1) – 1 ≤ k(Yi). Значит, или k(Xi) = k(Yi) (и требуемое разбиение найдено), или k(Xi) – 1 = k(Xi–1) = k(Yi–1) – 1 = k(Yi). Рассмотрим последний случай.
Пусть X = Xi, Y = Yi. Так как k(X) + k(Y) нечётно, найдётся хотя бы одна точка M ∈ X, не лежащая на границах множеств conv X и conv Y. Если есть такая точка M, не лежащая внутри conv Y, то, перенеся её из X в Y, получим искомое разбиение.
Пусть все такие точки лежат внутри conv X ∩ conv Y. Тогда это пересечение непусто. Положим X' = X \ conv Y. Все точки X' лежат на границе conv X (поскольку все внутренние точки conv X лежат также внутри conv Y), значит, k(X') < k(X) и k(X') ≤ k(Y). Если k(X') = k(Y), то X' и S \ X' задают искомое разбиение. В противном случае будем добавлять к X' точки из X ∩ conv Y, пока не получим такое множество Z, что k(Z) = k(Y). Множества Z и S \ Z задают искомое разбиение.
