Тема ПитерГор (Санкт-Петербургская олимпиада)

ПитерГор - задачи по годам → .04 ПитерГор 2017

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела питергор (санкт-петербургская олимпиада)

Разделы подтемы ПитерГор - задачи по годам

ПитерГор 2014 и ранее

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#71261Максимум баллов за задание: 7

Ученики школы посещают $m$ кружков. В каждый кружок ходит ровно $mk$ детей. Докажите, что можно рассадить всех учеников школы по $k$ кабинетам так, чтобы в каждом кабинете был хотя бы один представитель каждого кружка ( $m$ и $k$ — натуральные числа).

Источники: СпбОШ - 2017, задача 11.1(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Если конструкция с неизвестными пугает, то можно для начала рассмотреть ситуация на фиксированных числах. Попробуйте порассуждать, что будет, если, к примеру, m = 4, k = 6 (ну или любые удобные вам не слишком большие числа).

Подсказка 2

Итак, в каждом из k кабинетов должно быть хотя бы по одному представителю каждого из кружков. Тогда по сколько человек стоит брать из каждой секции, чтобы рассадить по одному в кабинет? Найдётся ли у нас столько учеников?

Показать доказательство

Выберем $k$ учеников из первого кружка, рассадим их в разные кабинеты. Выберем $k$ других человек из второго кружка и рассадим их, и так далее.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Ученики школы посещают $N$ кружков. В каждый кружок ходит ровно $mk$ детей. Всех учеников можно рассадить по $k$ кабинетам так, чтобы в каждом кабинете был хотя бы один представитель каждого кружка, даже если $N$ существенно больше $m.$ Ниже мы докажем, что это можно сделать при $m∕2 N ≈ e .$

Рассмотрим $k+ a$ комнат, где число $a$ определим позже. Посадим каждого школьника в одну из этих комнат, выбирая ее случайно (все комнаты равновероятны). Назовем комнату подозрительной, если в ней оказались представители не всех кружков. Предположим, что случилась УДАЧА: оказалось не более чем $a$ подозрительных комнат. Тогда имеется $k$ неподозрительных комнат, мы можем назвать их кабинетами, и искомая рассадка найдена. УДАЧА заведомо иногда случается, если математическое ожидание $E$ числа подозрительных комнат меньше $a+ 1.$ Заметим, что $E$ равно количеству комнат $k+ a,$ умноженному на вероятность того, что конкретная комната подозрительна. Эта вероятность, в свою очередь, не превосходит $( )km N 1 −k1+a .$ Итак, если

( ) N (k+a) 1 −--1- km < a+ 1 k +a

то при таком $N$ требуемая рассадка существует. Уже при $a =k$ получается экспоненциальное по $m$ выражение, наилучшего результата — около $em-−1 m$ — можно добиться при $a ≈ -k-. m−1$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#71262Максимум баллов за задание: 7

Окружность, проходящая через вершины $A$ и $B$ треугольника $ABC,$ пересекает стороны $AC$ и $BC$ в точках $P$ и $Q$ соответственно. Медиана из вершины $C$ делит дугу $PQ$ этой окружности пополам. Докажите, что треугольник $ABC$ равнобедренный.

$PIC$

Источники: СпбОШ - 2017, задача 11.2(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Откуда вообще могла бы взяться равнобедренность? Медиана и разделённая ею пополам дуга могут наводить на мысли о симметрии чертежа. Но что же делать, когда данных для строгого обоснования не хватает?

Подсказка 2

Попробуем пойти от противного: постройте точку, симметричную одной из вершин нашего треугольника, относительно изображённой медианы. Что за фигуры образуются, если построенная точка не совпадает с другой вершиной треугольника?

Подсказка 3

Во-первых у нас есть теорема Фалеса – он даст параллельность! А равные дуги и симметрия построенной картинки приведут нас к равенству углов.

Подсказка 4

Итак, перед нам вписанная трапеция! Осталось лишь немного поработать с равными отрезками и треугольниками, чтобы в конце концов сделать вывод о противоречии!

Показать доказательство

Пусть $M$ — середина стороны $AB,$ $K$ — середина дуги $PQ,$ лежащая на отрезке $CM, B′$ — точка, симметричная точке $B$ относительно медианы $CM.$

Предположим противное. Тогда $′ B ⁄= A,$ $′ AB ∥CM$ и

′ ∠CAK = ∠PAK = ∠QBK =∠CB K.

$PIC$

Таким образом, $CK$ и $AB′$ — основания вписанной, а следовательно, равнобочной трапеции $AB ′CK.$ Значит, $AK = CB ′ =CB, AC = KB ′ = KB,$ и треугольники $AKB$ и $BCA$ равны по трем сторонам. Противоречие: один из двух равных треугольников не может лежать внутри другого.

Ошибка.
Попробуйте повторить позже

Задача 3#71269Максимум баллов за задание: 7

Числа $x,y,z,t∈ (0,π∕2]$ удовлетворяют условию

2 2 2 2 cos x+ cos y+ cos z+ cos t= 1.

Какое наименьшее значение может принимать величина

ctgx+ ctgy +ctgz+ ctgt?

Источники: СпбОШ - 2017, задача 11.3(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Наверное, нам не зря дано, в какой четверти тригонометрической окружности лежат x, y, z и t. Как это можно применить?

Подсказка 2

Что если попробовать сравнить котангенс с тем самым квадратом косинуса? Это можно сделать как раз таки с использованием области значений тригонометрических функций!

Подсказка 3

Вот и получилось у нас нестрогое неравенство! Осталось лишь понять, когда тут достигается равенство и предъявить конкретные значения переменных.

Показать ответ и решение

Заметим, что

cosx 2cos2x 2cos2x 2 ctgx = sinx-=2-sinxcosx = -sin2x-≥ 2cos x.

Следовательно,

( ) ctgx +ctgy+ ctgz+ ctgt≥ 2 cos2x+ cos2y+ cos2z+ cos2t = 2.

Стало быть, интересующая нас сумма всегда не меньше $2.$ С другой стороны, если $π x= y = 4$ и $π z =t= -2,$ то

1 cos2x+ cos2y+ cos2z+ cos2t= 2⋅2 +2⋅0 =1 ctgx+ ctgy+ ctg z+ctgt= 2⋅1+2⋅0 =2.

Ответ:

Наименьшее значение равно $2$

Ошибка.
Попробуйте повторить позже

Задача 4#71294Максимум баллов за задание: 7

Натуральное число $n$ назовём почти квадратом, если $n$ можно представить в виде $n =ab,$ где $a$ и $b$ — натуральные числа, причем $a ≤b≤ 1,01a.$ Докажите, что для бесконечно многих натуральных $m$ среди чисел $m,m + 1,m + 2,...,m + 198$ нет почти квадратов.

Источники: СпбОШ - 2017, задача 11.4(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Если покрутить конструкцию на конкретных числах, то на уровне общих соображений, то всё становится достаточно понятно: "почти квадраты" лежат очень близко к квадратам (мы можем оценить это с помощью неравенств) и ясно, что с увеличением а у нас будут увеличиваться промежутки, на которых искомых чисел лежать не может. Но как же собрать это в строгое доказательство?

Подсказка 2

Попробуем пойти от противного. Какое утверждение обратно к нашему?

Подсказка 3

Разобьём натуральный ряд на отрезки по 199 чисел. Обратным к искомому будет утверждение о том, что во всех таких отрезках, кроме конечного количества с, будет содержаться "почти квадрат".
Сколько "почти квадратов" будет среди чисел от 1 до n²?

Подсказка 4

Получим оценку с двух сторон: оценка снизу связана с с, а оценку сверху построим из того, что b натурально и лежит в определённом промежутке. Осталось посмотреть, выполнима ли эта оценка при достаточно больших n.

Показать доказательство

Предположим противное. Разобьем натуральный ряд на отрезки по $199$ чисел. Тогда во всех отрезках, кроме, быть может, конечного количества $c,$ имеется почти квадрат. Отсюда следует, что среди чисел от $1$ до $2 n$ количество почти квадратов не меньше чем $n2- 199 − c,$ где $c$ — некоторая константа. С другой стороны, каждый такой почти квадрат имеет вид $ab,$ где $a≤n,$ $[ a-] b∈ a,a + 100 ,$ поэтому их количество не больше чем

n∑ ( ) 2 a100-+1 = n + n(n2+001)< n199 − c a=1

при достаточно большом $n.$ Противоречие.

Ошибка.
Попробуйте повторить позже

Задача 5#71302Максимум баллов за задание: 7

В тетраэдре $PABC$ проведена высота $PH.$ Из точки $H$ на прямые $P A,PB$ и $PC$ опущены перпендикуляры $HA ′,HB ′$ и $HC′.$ Плоскости $ABC$ и $′′ ′ A B C$ пересекаются по прямой $ℓ.$ Точка $O$ — центр окружности, описанной около треугольника $ABC.$ Докажите, что прямые $OH$ и $ℓ$ перпендикулярны.

$PIC$

Источники: СпбОШ - 2017, задача 11.5(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Построим чертёж. Совсем не похоже на то, чтобы OH оказалась перпендикулярна какой-то из плоскостей, которые у нас есть. Поэтому этот, самый очевидный путь, отметаем! Но что же тут можно сделать? Наличие большого количества прямых углов, опирающихся на PH могут навести нас на мысль о сфере с диаметром PH — давайте попробуем посмотреть на это, чтобы побольше узнать о нашей конструкции.

Подсказка 2

Постройте точку Т — пересечение прямых АВ и А'B', что можно сказать о ней? Используйте ранее построенную сферу и некоторые свойства четырёхугольника AA'B'B!

Подсказка 3

Если всё сделано верно, то мы получили интересное равенство, связывающее точку Т с А, В и Н. Как мы можем это применить?

Подсказка 4

Наше равенство по сути означает что точка Т лежит на радикальной оси окружности описанной около △АВС и точки Н. Осталось лишь проделать аналогичные действия на других гранях и задача решена!

Показать доказательство

Заметим, что $PA⋅P A′ =P H2 = PB ⋅PB′,$ так что точки $A,B,A′,B′$ лежат на одной окружности. Пусть $T$ — точка пересечения прямых $AB$ и $′ ′ A B.$ Имеем

′ ′ 2 TA ⋅TB =TA ⋅TB =T H

последнее равенство выполнено в силу того, что прямая $TH$ — касательная к сфере с диаметром $P H,$ а $T B′A ′$ — секущая.

$PIC$

Таким образом, точка $T$ лежит на радикальной оси окружности, описанной около треугольника $ABC,$ и точки $H$ (это частный случай, когда одна из окружностей точка). На ней же лежат точки $BC ∩ B′C ′,AC ∩A′C′.$ Значит, прямая $ℓ= ABC ∩A′B′C′$ и есть эта радикальная ось. Она перпендикулярна линии центров $OH.$

Ошибка.
Попробуйте повторить позже

Задача 6#71374Максимум баллов за задание: 7

В стране некоторые математики знакомы между собой и при любом разбиении математиков на две непустые группы найдутся двое знакомых из разных групп. Известно, что если посадить за круглый стол любой набор из $4$ или более математиков так, чтобы любые два соседа были знакомы, то за столом найдутся двое знакомых, не сидящих рядом. Обозначим через $ci$ количество наборов из $i$ попарно знакомых математиков. Докажите, что

c1− c2+ c3− c4+ ...= 1.

Источники: СпбОШ - 2017, задача 11.6(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Первым же делом введём граф. Вершины — математики, рёбра — знакомства. По условию, в любом цикле длины хотя бы 4 есть ребро внутри него, будем называть такие графы хордовыми. Подумайте, что нам даёт условие про разбиение на группы.

Подсказка 2

Разумеется, это означает, что граф связный, то есть в графе ровно 1 компонента связности. И доказать нас просят, что какая-то штука равна 1. Но пока что рано выдвигать гипотезы. Посмотрим на хордовый граф с двумя компонентами, каждая из которых — треугольник. Посчитаем выражение из условия для этого экспериментального графа. Чему же оно равно?

Подсказка 3

Оно равно двум! И компоненты у нас две. Хмм... А вот сейчас уже можно выдвинуть гипотезу.
Как же будет звучать наше предположение?

Подсказка 4

"Для хордового графа с k компонентами связности выражение из условия равно k". Звучит масштабно. Кажется, доказывать это напрямую будет сложновато, придётся всё считать и доказывать... Попробуем сделать это по-другому. Предположим противное... Но этого будет маловато. Запомните, что в подобного рода утверждениях стоит попробовать применить принцип крайнего!

Подсказка 5

Пусть G — наименьший по количеству вершин граф, который не удовлетворяет предположению. Как-то хотим начать работать с графом. Хотим как-то в ходе доказательства сослаться на минимальность примера, то есть как-то перейти к графам меньших размеров. Как же это можно сделать?

Подсказка 6

Поудалять вершины! Начнём с одной — вершины Y. Пусть наш граф распался на n компонент связности G₁, G₂, ..., Gₙ. Для дальнейшего удобства обозначим с₁ - с₂ + … за f(X) для графа Х. Здесь мы как-раз таки воспользуемся тем, что граф G — минимальный контрпример для нашего предположения, то есть f(G₁) = ... = f(Gₙ) = 1. Хотим как-то связать f(G) и f(G₁), .., f(Gₙ). Но в f(Gᵢ) учтены только клики без Y. Как бы нам посчитать или хотя бы учесть клики с вершиной Y?

Подсказка 7

Клики с участием Y построены на соседях Y (смежных с Y вершинах). Значит, нам нужно отдельно поработать с соседями Y. Пусть Hᵢ — вершины в Gᵢ, которые связаны с Y (соседи) для всех i. Как же нам теперь учесть клики с вершиной Y?

Подсказка 8

f(Hᵢ) — количество клик с участием Y на вершинах, принадлежащих Gᵢ (формально, это клики без участия Y, образованные на вершинах Hᵢ, но все они становятся нужными кликами, если к ним добавить Y, поэтому численные значения совпадают). Итак, какая же итоговая формула для f(G) через f(Hᵢ) и f(Gᵢ)?

Подсказка 9

Докажите, что f(G) = 1 + Σ f(Gᵢ) - Σ f(Hᵢ). Хотим доказать, что f(G) = 1, то есть Σ f(Hᵢ) = n или же f(Hᵢ) = 1 для всех i. Утверждение равносильно тому, что все подграфы Hᵢ — связные. Вспомните, что мы ещё не использовали.

Подсказка 10

Именно! Хордовость графа G. Предположите, что (не умаляя общности) H₁ — не связный, то есть в нём есть хотя бы две компоненты A и B. Осталось доказать, что в этом случае есть цикл длины хотя бы 4 без хорды внутри, иначе говоря, получить, что G — не контрпример. Уверены, у Вас получится! Успехов!

Показать доказательство

Рассмотрим граф знакомств математиков. По условию этот граф хордовый, т.е. в нем любой цикл из $4$ или более вершин содержит хорду (пару смежных вершин, не соседних в цикле). Докажем, что для хордового графа $G$ выражение $f(G):= c1− c2+ c3− ...,$ где $ci$ — количество клик (полных подграфов) в $G$ на $i$ вершинах, равно числу $k(G)$ компонент связности графа $G.$

Предположим, что это не так, и рассмотрим в качестве $G$ наименьший по числу вершин контрпример. Ясно, что граф $G$ содержит больше одной вершины и связен (иначе одна из компонент связности была бы меньшим контрпримером). Удалим из графа $G$ произвольную вершину $v,$ пусть новый граф $G∖v$ распался на компоненты $G1,...,Gk.$ Пусть $H1$ , $H2,...,Hk$ — подграфы в $G1,...,Gk$ соответственно на соседях вершины $v.$ Несложно видеть, что

k k f(G)= 1+ ∑ f (Gi)− ∑ f(Hi) i=1 i=1

где слагаемое $1$ соответствует клике ${v},$ слагаемые $f(Gi)$ — кликам, не содержащим $v,$ слагаемые — $f(Hi)$ — кликам, содержащим $v$ (при удалении из них вершины $v$ меняется четность, а стало быть, знак в выражении для $f$ ). В силу минимальности контрпримера $f (Gi)= 1,f (Hi)= k(Hi).$ Проверим, что $k(Hi)= 1$ при всех $i.$ Предположим противное, тогда вершины одного из графов $Hi$ можно разбить на два непустых подмножества $− + V ,V$ так, что ни одно ребро не ведет из $− V$ в $+ V .$ Рассмотрим наименьший по числу ребер путь $x...y$ из $− V$ в $+ V$ в графе $Gi.$ Тогда цикл $vx...yv$ не имеет хорды в графе $G.$