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

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

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

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

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

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

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

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

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

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

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

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

Бумажный квадрат со стороной $100$ разрезали $99$ вертикальными и $99$ горизонтальными прямыми, получив таким образом $10000$ прямоугольников (необязательно с целыми сторонами). У какого наименьшего количества прямоугольников площадь может оказаться меньшей или равной $1?$

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

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

Подсказка 1

Такс... сперва давайте обозначим как-то длины отрезков, на которые разбиты стороны. Например, пусть одна сторона разбита на отрезки a₁ ≤ a₂ ≤ ... ≤ a₁₀₀, а другая на отрезки b₁ ≤ b₂ ≤ ... ≤ b₁₀₀. На какую оценку намекает формула площади прямоугольника и сумма длин отрезков?)

Подсказка 2

Конечно! Т.к. площадь прямоугольника это ab, то можно воспользоваться неравенством о средних. Как это сделать?

Подсказка 3

Давайте рассмотрим числа √a₁*√b₁₀₀, √a₂* √b₉₉, ..., √a₁₀₀*√b₁. По неравенству о средних √a*√b ≤ (a+b)/2. Как тогда можно оценить сумму этих чисел?

Подсказка 4

Да! Их сумма не превосходит половины суммы всех aᵢ и bᵢ, т.е. не превосходит 100. О чем это говорит?

Подсказка 5

Верно! Тогда можно сказать, что найдётся такой номер j, что aⱼb₁₀₀ -ⱼ≤ 1. Теперь осталось рассмотреть индексы, меньше j для a и 100 - j для b и показать, что таких пар ≥100. Не забудем построить пример!!!

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

Пример.

Одну из сторон разобьём на $100$ отрезков длины $1,$ а другую — на $99$ отрезков длины $1,01$ и оставшийся отрезок длины $0,01$ . Тогда только $100$ прямоугольников с узкой стороной длины $0,01$ имеют площадь меньше $1.$
Оценка.

Первый способ
Пусть одна из сторон разбита на отрезки длины $a1 ≤ a2 ≤...≤a100,$ а другая — на отрезки $b1 ≤b2 ≤ ...≤ b100.$ Рассмотрим числа $√ -----√---- a1b100, a2b99$ , $√ ----- ..., a100b1.$ В силу неравенства $√ -- a+b ab ≤ 2 ,$ сумма всех этих чисел не превосходит половины суммы всех $ai$ и $bi,$ т.е. не превосходит $100.$ Поэтому найдётся такой номер $j,$ что $ajb101−j ≤ 1.$ Но тогда и для всех пар $k,n$ при $k ≤j,n≤ 101− j$ тоже выполнено неравенство $akbn ≤ 1,$ причём количество таких пар равно $j(101− j)≥ 100.$ Это значит, что все прямоугольники со сторонами $ak$ и $bn$ имеют площадь не больше $1,$ и число этих прямоугольников не меньше $100.$
Второй способ
Пусть одна из сторон разбита на отрезки длины $a0,a1,...,a99,$ а другая — на отрезки $b0,b1,...,b99.$ Для удобства будем считать, что отрезки занумерованы остатками от деления на $100.$ Возьмём произвольное $k$ от $0$ до $99$ и рассмотрим выражение

∘ ---- ----- ----- ------- ( a0bk+ ∘a1bk+1 +∘ a2bk+2+ ...+ ∘a99bk+99)2.

По неравенству Коши-Буняковского-Шварца оно не превосходит

(a0+a1+ ...+ a99)(bk+ bk+1+...+bk+99)= 1002.

Следовательно, $√---- ∘ ----- ∘----- ∘ ------- a0bk+ a1bk+1+ a2bk+2 +...+ a99bk+99 ≤100,$ и значит, одно из его слагаемых не превосходит $1.$ Стало быть, мы доказали существование прямоугольника малой площади, у которого номера сторон различаются ровно на $k.$ А поскольку $k$ может быть любым числом от $0$ до $99,$ существует не менее $100$ таких прямоугольников.

Ответ:

$100$

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

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

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

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

Числа $x$ и $y$ удовлетворяют условиям $x2+ y2 = 1$ и $20x3− 15x =3.$ Найдите $|20y3− 15y|.$

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

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

Подсказка 1

Не напоминает ли нам первое условие какую-нибудь теорему из области тригонометрии? Возможно, это даст нам неплохую идею для замены!

Подсказка 2

Итак, первое уравнение позволяет нам заменить одну из переменных на синус, а вторую — на косинус. Но что же делать дальше? Какую формулу напоминает второе условие, после вынесение общего множителя слева за скобки?

Подсказка 3

Удивительно! Второе условие и неизвестное выражение очень напоминают нам тригонометрические формулы для тройных углов, с точностью до умножения на коэффициент. Осталось лишь чуть-чуть повычислять, снова вспомнить об ОТТ и задача решена!

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

Первое решение.

Подберём $α$ таким образом, чтобы выполнялось равенства $x= sin(α),y = cos(α).$ Тогда $3 3 sin(3α)= 3sin(α)− 4sin (α)=3x− 4x = −3∕5.$ Следовательно,

3 3 |20y − 15y|= |20cos(α)− 15cos(α)|=

∘-----2--- = |5cos(3α)|= 5 1 − sin (3α) =4

Второе решение.

Найдём значение выражения $|4y3− 3y|.$ Для этого достаточно найти значение его квадрата, а потом извлечь корень. Но квадрат этого выражения равен

3 2 2 2 2 4 2 |4y − 3y|= y (4y− 3) =y (16y − 24y + 9).

Подставим $1− x2$ вместо $y2,$ преобразуем и получим выражение

6 4 2 2 2 (3)2 16 − 16x + 24x − 9x + 1= 1− x(4x− 3) = 1− 5 = 25-

Следовательно, $()2 |4y3− 3y|2 = 45 ,$ откуда и находим ответ.

Ответ:

$4$

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

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

Натуральные числа $a$ и $b$ больше $1.$ Известно, что числа $a2+ b$ и $a +b2$ простые. Докажите, что числа $ab+ 1$ и $a+ b$ взаимно простые.

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

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

Подсказка 1

Если утверждение не получается доказать напрямую, то можно пойти от противного: пусть требуемое не выполняется! А что точно есть у чисел, не являющихся взаимно простыми? Какие противоречия стоит искать, используя условие о двух данных простых числах?

Подсказка 2

На что может делиться произведение двух простых чисел? Попробуйте доказать, что если (ab + 1) и (a + b) имеют общий делитель p, то и произведение двух данных простых чисел, тоже делится на p.

Подсказка 3

Внимательная группировка поможет нам представить это произведение в виде суммы двух слагаемых, одно из которых делится на (ab + 1), а второе — на (a + b).

Подсказка 4

Осталось лишь аккуратно сформулировать, почему p не может быть равно какому-либо из данных простых чисел, а является именно его ещё одним делителем.

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

Пусть они не взаимно простые. Тогда $ab+1$ и $a+ b$ имеют общий простой делитель $p.$ Рассмотрим произведение чисел $a2+b$ и $a+ b2$ и преобразуем

2 2 22 3 3 2 2 (a + b)(a+ b)= a b +ab+ a +b = ab(ab+ 1)+ (a+ b)(a − ab+ b).

Тогда произведение тоже делится на $p.$ Но поскольку $p ≤a+ b< min(a2+ b,b2+ a),$ число $p$ является собственным делителем какого-то из чисел $a2+b$ или $a+ b2,$ что противоречит их простоте.

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

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

Набор разновесов содержит по одной гире каждого из весов $1,3,5,7,9...$ граммов. Для натурального $n> 1$ докажите, что количество способов набрать этими гирями $n$ граммов не больше, чем количество способов набрать $n+ 1$ грамм.

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

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

Подсказка 1

Так-с, давайте введём несколько переменных, зависящих от n. Пусть a(n) — количество способов собрать вес n без гири в 1 г, a b(n) — количество способов собрать вес n с гирей в 1 г.

Подсказка 2

Хмммм, что же теперь делать. Интуитивно кажется, что собрать n + 1 грамм легче, чем собрать n грамм. Попробуем это доказать строго. Для строгого обоснования данного факта нам нужна индукция.

Подсказка 3

Применив мат. индукцию, мы получили, что a(n + 1) ≥ a(n), а также b(n + 1) ≥ b(n). Кажется, остаётся просто сложить 2 получившихся неравенства!

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

Пусть имеется $a n$ способов выбрать $n$ граммов без использования гири в $1$ г и $b n$ способов набрать $n$ граммов с использованием гири в $1$ г.

Добавив к каждому из способов первой группы гирю в $1$ г, мы получим суммарный вес $n +1$ граммов. Значит, $bn+1 ≥an$ (способов выбрать $n$ граммов без единицы может быть равно нулю, поэтому знак больше или равно).

С другой стороны, если для каждого способа набрать $n$ граммов с использованием гири в $1$ г мы уберём эту гирю и заменим самую большую использованную гирю в этом способе на ту, которая весит на $2$ г больше, снова получится суммарный вес $n+ 1$ граммов.

Следовательно, $an+1 ≥bn$ (при нечётном $n$ появляется ещё один способ взять гири вне этого алгоритма, поэтому знак больше или равно).

Сложив полученные два неравенства, имеем требуемое.

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

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

Дан выпуклый четырехугольник $ABCD.$ Описанная окружность треугольника $ABC$ пересекает стороны $AD$ и $DC$ в точках $P$ и $Q$ соответственно. Описанная окружность треугольника $ADC$ пересекает стороны $AB$ и $BC$ в точках $S$ и $R$ соответственно. Оказалось, что четырехугольник $P QRS$ — параллелограмм. Докажите, что и четырехугольник $ABCD$ — параллелограмм.

$PIC$

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

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

Подсказка 1

Для начала, как и всегда в геометрии, стоит сделать аккуратных чертёж, с которым удобно работать! На что нам намекают окружности, когда нет никаких явных значений длин и почти нет их соотношений?

Подсказка 2

С отрезками работать не особо тут продуктивно, значит будем смотреть на углы! Поотмечайте всякие равные вписанные уголочки. Удаётся ли заметить таким образом пары параллельных прямых?

Подсказка 3

Параллельности, конечно, есть, но пока не те что нам нужны. Что же ещё может нам помочь? Пока мы не использовали тот факт, что внутренний четырёхугольник — параллелограмм!

Подсказка 4

Параллелограмм и параллельности дают нам красивую симметрию! Посмотрите внимательно на точку пересечения диагоналей параллелограмма и задача будет решена.

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

Заметим, что $∠ADR = ∠ACR = ∠ACB = ∠APB$ по свойствам вписанных углов, откуда $P B∥DR.$ Аналогично, $DS ∥BQ.$ Следовательно, симметрия относительно точки пересечения диагоналей параллелограмма $PQRS$ переводит треугольник $SDR$ в треугольник $QBP$ , в частности, $D$ отображается в $B$ . Тогда точка пересечения прямых $BR$ и $DQ$ переходит в точку пересечения симметричных им прямых $DP$ и $BS,$ т. е. $C$ переходит в $A.$ Таким образом, четырехугольник $ABCD$ симметричен относительно той же точки, и значит, является параллелограммом.

$PIC$

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

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

В стране Центумии некоторые пары городов соединены дорогами, причем из каждого города выходит ровно $100$ дорог. Пучком называется набор из $10$ дорог, выходящих из одного города. Докажите, что все дороги можно разбить на несколько пучков.

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

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

Подсказка 1

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

Подсказка 2

Это намекает на циклы. Но будем действовать по порядку. Разобьём граф на компоненты связности. В каждой компоненте выделим наибольший по длине простой цикл. Удалим все входящие в них рёбра, запомним эти циклы. У каких-то вершин степень уменьшилась ровно на 2. Хм, интересно, может продолжить делать что-то подобное, пока не придём в "конечную позицию"?

Подсказка 3

Действительно! После этого снова разобьём граф на компоненты (могли появиться новые). Снова в каждой выделим цикл и т.д., пока циклы не закончатся. Интересно, как выглядит это конечная позиция?

Подсказка 4

Степень каждой вершины всегда кратна 2. Значит, в каждой компоненте всегда есть цикл, если есть рёбра (осознайте это). То есть в конце рёбер не останется. Какой из этого вывод можно сделать?

Подсказка 5

Все рёбра графа разбились на непересекающиеся простые циклы. Граф стал гораздо понятнее, через каждую вершину проходит ровно 50 циклов (осознайте это). Но пока не особо понятно, как выбрать из 100 рёбер вершины 10 пучков. Если выбирать произвольно, можно получить пересечения двух пучков из смежных вершин. Хочется, чтобы эти рёбра пучков как бы "смотрели в одну сторону", тогда они точно не совпадут для смежных вершин. Как бы это сделать...?

Подсказка 6

Идея! А давайте ориентируем наши циклы произвольным образом. Тогда из каждой вершины выходит по 50 рёбер и в каждую входит по 50 рёбер. А вот теперь осталось внимательно посмотреть на выходящие рёбра и понять, что если разбить их на пучки, то вы докажите утверждение задачи. Мы в вас верим! Успехов!

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

Рассмотрим граф $G$ , в котором вершины — это города, а рёбра — дороги. Степени всех вершин этого графа равны $100.$ Разобьем все рёбра графа $G$ на реберно непересекающиеся циклы. В каждом цикле зададим произвольно порядок обхода и ориентируем рёбра в направлении обхода цикла. Тогда в каждую вершину $G$ входит $50$ ребер и из каждой вершины выходит тоже $50$ ребер. Разобьем все ребра, выходящие из каждой вершины, на 5 пучков. Тогда все рёбра графа $G$ разобьются на пучки.

Предыдущая подтема

Следующая подтема