СПБГУ 2024
Ошибка.
Попробуйте повторить позже
Кузнечик прыгает по числовой прямой. Каждый свой прыжок он может совершить в любом направлении. Он начинает в точке 0 прыжком единичной длины. Каждый следующий прыжок должен быть на три больше предыдущего (т.е. первый прыжок длины 1, второй длины 4, третий длины 7 и т.д.). За какое наименьшее число прыжков кузнечик сможет оказаться в точке 2024?
Источники:
Подсказка 1
Попробуем как-то оценить n…а как вообще посчитать, насколько далеко мы ушли от начала координат?
Подсказка 2
Заметим, что наши прыжки - это члены арифметической прогрессии a ₙ = 3n-2. Тогда на какое наибольшее расстояние мы можем уйти от нуля? Каким тогда должно быть n?
Подсказка 3
Максимальное расстояние, на которое мы можем уйти - это (3n-1)n/2. И мы знаем, что это число должно быть не менее 2024. Теперь у нас есть какая-то оценка на n. А как (в зависимости от прыжков влево) посчитать местоположение кузнечика?
Подсказка 4
Обозначим общую длину прыжков влево как х. На какой клетке тогда находится кузнечик? Каким тогда должно быть n?
Подсказка 5
Кузнечик будет стоять на точке (3n-1)n/2 - 2х. Осталось лишь понять, каким должен быть n ;)
Процесс прыжков можно описать следующим образом: прыжков кузнечика — это сумма
первых членов арифметической прогрессии
, в которой перед каждым членом стоит
или
. Ясно, что за
прыжков кузнечик сможет оказаться не более, чем в
— сумма
первых членов, в которой все члены взяты с
. Значит, необходимо, чтобы
было не меньше
. То есть
.
Пусть кузнечик прыгал влево некоторое количество прыжков, и суммарно он прыгнул влево на единиц, тогда после
прыжков он
окажется в точке
. Значит, чтобы попасть в
, необходимо, чтобы
было чётным. Значит,
и
прыжков не хватит. В качестве примера на
можно прыгнуть влево на
и на
прыжках, а на остальных —
вправо.
Ошибка.
Попробуйте повторить позже
Найдите угол если известно, что
и
Источники:
Подсказка 1
На что издалека напоминает уравнение из условия?
Подсказка 2
На формулу тангенса суммы! Попробуем tg(2+5) преобразить так, чтобы он еще больше стал похож на уравнение из условия ;)
Подсказка 3
А что если расписать tg(2+5) + 1? В числителе как раз появятся нужные слагаемые
Подсказка 4
Обратите внимание, что 1 - tg(5)² + tg(5) + tg(2) можно разложить на множители! Смотрите, получилось что-то очень похожее на знаменатель из условия ;)
Подсказка 5
Теперь мы знаем, что (1 - tg(5))(1-tg(2)) - 2 = -(tg(7) + 1)(1 - tg(5)tg(2)). Осталось лишь понять, как выразить знаменатель условия и дело остается за малым ;)
Вспомним формулу тангенса суммы:
Проведём с ней некоторые махинации:
Домножим на знаменатель:
Если аналогично рассмотреть выражение , то мы получим, что
Таким образом,
Следовательно, .
Ошибка.
Попробуйте повторить позже
Дан остроугольный треугольник , меньший угол которого
. Внутри треугольника выбрана такая точка
,
что
Через точку провели прямую, параллельную прямой
, она пересекла прямую
в точке
Биссектрисы углов
и
пересекаются в точке
Найдите угол
Источники:
Подсказка 1
Попробуем посчитать какие-то углы…обозначим угол DBF как х. Что интересного можно сказать о четырехугольнике AFDB?
Подсказка 2
AFDB — вписанный (в нем углы, опирающиеся на одну дугу, равны x). Что из этого можно вывести?
Подсказка 3
Треугольник AFD равнобедренный! Попробуем продолжить считать углы…что можно сказать о четырехугольнике AECB?
Подсказка 4
AECB — вписанный! Подумаем, а как нам подобраться к углу DFE? Нужно подобрать к точке F. А что если посчитать угол AED?
Подсказка 5
Оказывается, AED в два раза меньше AFD. Что это значит?
Подсказка 6.
Точка F является центром описанной окружности треугольника ADE? Осталось лишь посчитать угол DFE, исходя из этого;)
Положим для краткости , тогда
и
. По условию
и, значит, .
Следовательно,
и четырехугольник вписанный.
Таким образом, , значит, треугольник
равнобедренный и, в частности,
. Поскольку
биссектриса угла
, а прямые
и
параллельны,
. Следовательно, четырехугольник
является вписанным
В силу вписанности
стало быть, точка является центром описанной окружности треугольника
и, значит,
. Осталось заметить,
что
откуда получаем ответ .
Ошибка.
Попробуйте повторить позже
Решите уравнение в целых числах
Источники:
Подсказка 1
Тот факт, что у нас есть слагаемое, которое мало на что делится, говорит о том, что его, в теории, можно использовать при доказательстве в смысле рассмотрения делимости на его множители. Давайте, к тому же, заметим, что 2024 кратно 11 и будем рассматривать делимости на 11. Что вы можете сказать про делимость на 11 обеих частей при разных n? А при фиксированном n и разных m, k?
Подсказка 2
Возможные остатки квадратов mod 11 - это 0, 1, 3, 4 5, 9. Какие пары этих остатков в сумме дают 0(нам ведь нужна делимость на 11 левой части)? Только пара 0 - 0. Значит, что оба числа кратны 11, а значит левая часть кратна 11². Всегда ли кратна правая часть 11²? Если нет, то при каких n кратна 11²?
Подсказка 3
При n ≥ 2 первое слагаемое кратно 11², а 33 нет. Значит, кратность может быть только при n = 0 или n = 1. При n = 1, у нас правая часть превращается в 17 * 11². Значит, все таки есть кратность 11, а значит верны наши рассуждения про m и k. Но тогда мы можем представить их в виде 11t и сократить на 11², после чего, довести до ответа. А случай n = 0 - оставляется читателю в качестве упражнения.
Числа и
являются целыми числами, следовательно, каждое из чисел
и
являются целыми, а значит, и их сумма
является целыми числом, таким образом, число
также является целым, т.е. число
целое, откуда
.
_________________________________________________________________________________________________________________________________________________________________________________
Пусть . Тогда
делится на 11, поскольку каждое из чисел 2024 и 33 кратно 11, но не делится на
, т.к. первое
слагаемое кратно
, а второе — нет.
Пусть число дает остаток 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 при делении на 11, тогда число
дает соответственно остаток 0, 1, 4, 9, 5, 3, 3,
5, 9, 4, 1 при делении на 11. Докажем, что если хотя бы одно из чисел
и
не делится на 11, то и число
не делится на
11.
Предположим обратное, тогда сумма остатков чисел и
равна 11, следовательно, ровно одно из чисел
и
даёт четный
остаток при делении 11, а значит, соответствующий квадрат даёт остаток 0 или 4 при делении на 11, но тогда второй остаток равен 0 или 7,
что невозможно. Таким образом, каждое из чисел
и
кратно 11, следовательно, каждое из чисел
и
кратно
, таким
образом,
кратно
, но
не кратно
.
_________________________________________________________________________________________________________________________________________________________________________________
Тогда или
Пусть . Тогда
, следовательно,
кратно
, а значит, как мы показали выше,
каждое из чисел
и
кратно 11. Пусть
,
, где
и
являются целыми числами, следовательно,
. Легко
убедиться, что всеми решениями
данного уравнения являются неупорядоченные пары
Следовательно, все пары решений
это
,
.
Пусть . Тогда
. Если каждое из чисел
и
не превосходит по модулю 4, то сумма их квадратов не
превосходит 32, следовательно, наибольшее из чисел
и
по модулю не меньше 5. С другой стороны, если какое-то из чисел по
модулю больше 5, то его квадрат не меньше 36, что невозможно. Таким образом, в паре чисел
хотя бы одно равно
5 по модулю, тогда второе равно 3 по модулю. Тем самым, мы показали, что все пары решений
есть
,
.
Ошибка.
Попробуйте повторить позже
В стране городов. Некоторые из них соединены авиалиниями, а некоторые нет. Известно, что для любых
городов найдётся
пар городов, не соединённых авиалиниями. Какое наибольшее количество авиалиний может быть в стране?
Источники:
Подсказка 1
Переведем задачу на язык графов. Нам нужно придумать, как использовать условие на 200 городов. А что если взять какие-нибудь особенные 200 городов?
Подсказка 2
Рассмотрим подграф А из 200 вершин с наибольшим количеством рёбер и подграф В из оставшихся 200 вершин. Нам нужно как-то оценить количество ребер между А и В. Что можно сказать о степенях вершин в В? А в А?
Подсказка 3
Рассмотрим вершину из А, соединенную с наименьшим количеством вершин (в А). Пусть такая ее степень это х. Какие тогда степени могут иметь вершины из В?
Подсказка 4
Ни одна вершина в В не может быть соединена хотя бы с х+1 вершиной в А. Как тогда оценить количество рёбер между А и В? Нам надо сделать его как можно больше.
Подсказка 5
Между этим графами не более, чем 200*х рёбер. А в подграфах сколько ребер может быть максимально?
Подсказка 6
Не более, чем 2*19600. Итак, теперь нам надо оценить х. Как это можно сделать?
Подсказка 7
Если х — это наименьшая степень вершины в х, то сколько рёбер может быть в А?
Подсказка 8
Не менее, чем 100х. Осталось лишь оценить х, используя полученные оценки на подграф А ;) не забываем про пример!
Рассмотрим граф, в котором города — вершины, а авиалинии — рёбра. Рассмотрим подграф из
вершин с наибольшим количеством
рёбер и подграф
из оставшихся
вершин.
Пусть вершина из подграфа
соединена с наименьшим количеством вершин в этом подграфе (
вершин). Предположим,
что в подграфе
имеется вершина
, которая соединена с хотя бы
вершиной из подграфа
. В таком случае
вершину
можно переместить в подграф
вместо вершины
и в нём будет больше авиалиний, что противоречит
выбору подграфа
. Следовательно, любая вершина из подграфа
связана не более чем с
вершинами из подграфа
.
Значит, между этими подграфами не более рёбер. Внутри же каждого из этих подграфов не более
рёбер.
Значит, всего в графе не более
Как известно, — это наименьшая степень вершины в подграфе
. Значит, в
не менее
рёбер. С другой
стороны, в этом подграфе не более
рёбер, откуда
. Теперь мы можем оценить количество рёбер в графе:
.
_________________________________________________________________________________________________________________________________________________________________________________
Приведём пример на рёбер. Разбиваем города на
групп по
городов. Внутри групп между городами авиалиний нет, а между
городами из разных групп — есть.
Пусть выбрано городов так, что из них
город из первой группы,
из второй,
,
— из
-й. Тогда количество пар, не
соединённых авиалиниями, будет не менее
по неравенству между средним квадратическим и средним арифметическим
Мы показали, что для произвольного подграфа в примере выполняется условие задачи.