СПБГУ - задания по годам → .09 СПБГУ 2023
Ошибка.
Попробуйте повторить позже
В каждой клетке таблицы 
записано натуральное число. В каждой строке имеется по крайней мере 10 различных чисел, а в
каждых четырех последовательных строках не более 15 различных чисел. Какое наибольшее количество различных чисел может быть в
таблице?
Источники:
Подсказка 1
У нас в каждой строке не менее 10 различных чисел, в подряд идущих четырех строчках не больше 15 различных...как будто следующие 3 строчки дают не очень много новых различных чисел. Это наблюдение легко сделать строгим, и останется привести пример)
Подсказка 2
Если вышло, что различных чисел не больше 175, это хорошо. Тогда вот идея для примера: в первой строчке давайте сделаем все числа от 1 до 10, а в 2, 3 и 4 поставим числа от 1 до 5 и от 11 до 15. Придумайте, как это обобщить на всю нашу доску)
В одной строке не менее 10 различных чисел, поэтому в следующих трех строках вместе появляется не более 5 новых чисел. Стало быть,
первые четыре строки содержат не более 15 различных чисел, а каждые следующие три строки дают не более 5 новых чисел и всего чисел не
больше, чем 
Приведем пример на 175 чисел. Занумеруем строки числами от 1 до 100. В первой строке поставим числа от 1 до 10, а в строке с
номерами от 
до 
поставим числа 1 до 5 и числа от 
до 
Тогда в каждой строке будет 5 уникальных чисел и
еще числа от 1 до 5, т.е. ровно 10 различных чисел, а в каждых четырех строках будет ровно 15 различных чисел. Таким образом, в таблице
будут числа от 
до 
Замечание.
Доказать, что количество различных чисел в таблице не превосходит 175, можно по индукции. А именно, доказать, что в любых 
подряд идущих строках расположено не более чем 
различных чисел. База 
верна по условию. Установим
переход от 
к 
Рассмотрим 
подряд идущие строки. Пусть в четвертой с конца строке имеется 
различных чисел. Тогда в трех самых нижних строках не более чем 
различных чисел. А в оставшихся 
строке по индукционному предположению не больше 
чисел. Поэтому всего различных чисел будет более чем
Ошибка.
Попробуйте повторить позже
Найдите все простые 
для которых числа 
и 
являются удвоенными квадратами натуральных чисел.
Источники:
Подсказка 1
Пусть p+1 = 2x², p²+1 = 2y². Вот давайте вычтем эти два выражения: будет p(p-1) = 2(y-x)(y+x). Про что можно тут подумать, раз слева стоит простой множитель?
Подсказка 2
Про делимости! У нас делится на p либо 2, либо y-x, либо y+x. Если проверить p = 2, то он не подойдет. А может ли y-x делится на p?
Подсказка 3
Можно заметить, что т.к. p+1 = 2x², то x<p, а также y<p и x<y. Тогда y-x тем более < p и он на него не делится. Остается, что y+x делится на p. Используя наши оценки на x и y, поймите, чему равно y+x и решите полученную системку!
Пусть
тогда
Поэтому одно из чисел 2, 
и 
кратно 
Если 2 кратно 
то 
что невозможно, поскольку 
не является
удвоенным квадратом.
Первый способ.
Из неравенства 
следует, что
Таким образом, имеем систему из двух уравнений
Решаем её
Значит,
Следовательно, 
Второй способ.
Если 
делится на 
то
Значит, это невозможно. Следовательно, 
делится на 
Заметим, что
Тогда если 
то
Значит,
Стало быть,
Но этого не может быть. Таким образом, осталось рассмотреть случаи 
и 
В первых двух из них 
не является
удвоенным квадратом, а 
подходит.
Ошибка.
Попробуйте повторить позже
Сумма положительных чисел 
и 
не превосходит 
Найдите наибольшее значение выражения
Подсказка 1
Нам дано условие на сумму чисел, а тут стоят какие-то корни с произведениями...Тогда может стоит использовать неравенство о средних? Но просто используя нер-во о средних для двух сомножителей, ничего не выходит хорошего. На что стоит обратить внимание: у нас корень 4 степени, а множителей всего два...
Подсказка 2
Тогда нужно найти еще два множителя) И второе: хочется, чтобы максимум достигался при всех единичках. С помощью этого можно подобрать числа, которые надо вставить внутри корня, чтобы получилось хорошее нер-во)
Первое решение. По неравенству о средних для четырех чисел имеем
Просуммируем это неравенство с тремя аналогичными и получим, что
Равенство достигается, когда 
Второе решение. По неравенству Коши–Буняковского для наборов чисел 
и 
имеем
А по неравенству Коши–Буняковского для наборов 
и 
имеем
Значит, 
Аналогично по неравенству Коши–Буняковского для наборов 
и
имеем
Значит, 
Следовательно,
Равенство достигается, когда 
Третье решение. По неравенству Коши–Буняковского для наборов чисел 
, 
и 
имеем
Оценим по-отдельности сомножители в правой части. По неравенству о средних для двух чисел 
поэтому
Аналогично по неравенству о средних для двух чисел
Значит,
Следовательно,
Равенство достигается, когда 
Ошибка.
Попробуйте повторить позже
Точка 
— центр описанной окружности остроугольного треугольника 
а 
— точка пересечения его высот. Оказалось, что
прямая 
параллельна стороне 
На плоскости отметили такую точку 
что 
— параллелограмм. Отрезки
и 
пересеклись в точке 
В каком отношении перпендикуляр, опущенный из точки 
на отрезок 
делит
Источники:
Подсказка 1
Давайте постепенно раскручивать задачу и понимать, для чего нам дали факты из условия. Предположительно вообще вы можете угадать ответ, и он вас будет как-то направлять, но в любом случае нужно понаблюдать за картинкой. Зададим себе правильные наводящие вопросы. Для чего нам дали параллельность OH? Это ведь не в любом треугольнике верно. Что можно сказать про углы и получившуюся фигуру с параллельными прямыми?
Подсказка 2
Верно, так как высота перпендикулярна стороне BC, то она перпендикулярна и OH из параллельности. Пусть у нас проведена высота AD. Также у нас получилась трапеция. А значит, перпендикуляр OT равен HD. Какой факт тогда можно вспомнить об этих отрезках? Тут полезно вспомнить про прямую Эйлера и факты, связанные с ней.
Подсказка 3
Точно, OT будет в два раз меньше AH из-за подобия треугольников OMT и AHM, где M — это точка пересечения медиан. Но тогда 2HD=AH. Отлично, уже лучше! Теперь займёмся параллелограммом. Заметим, что у нас сторона AK перпендикулярна AC. Что можно подумать тогда сделать? Хотелось бы, чтобы отрезок AK был получше связан с картинкой. Может, стоит продлить его до пересечения с чем-нибудь?
Подсказка 4
Ага, давайте продлим AK за точку A. Тогда с чем хорошо пересечь эту прямую, учитывая 90 градусов? Конечно, давайте пересечём с описанной окружностью треугольника в точке N. Тогда точки N и C диаметрально противоположные. Откуда O лежит на CN. А что ещё можно сказать про точку N? Как она связана с ортоцентром?
Подсказка 5
Верно, точка N центрально-симметричная H относительно AB, так как CN это диаметр. Тогда у нас получается ещё один параллелограмм AHBN. Откуда получается, что AN =BH = AK. Давайте теперь обратим внимание на треугольник NKC. Чем в ней является отрезок OK? А отрезок CA?
Подсказка 6
Точно, это же медианы в треугольнике NKC! Но тогда L — это точка пересечения медиан. Отлично, про точку, казалось бы, непонятно каким образом относящуюся к картинке, мы установили такой факт. Остались последние шаги. Какой факт мы знаем про точку пересечения медиан? Как это можно связать с фактом из 3 подсказки?
Подсказка 7
Верно, точка пересечения медиан делит медиану в отношении 2 к 1 от вершины. Теперь вспоминая, что мы проводили перпендикуляр из L на AH, можем применить теорему Фалеса и равенство отрезков. Победа!
Пусть 
— основание высоты из точки 
а 
— основание перпендикуляра, опущенного из точки 
на 
Прямая 
—
серединный перпендикуляр к отрезку 
поэтому она параллельна высоте 
По свойству ортоцентра 
и 
По условию прямые 
и 
параллельны, следовательно, 
—
прямоугольник и 
Первое решение.
В параллелограмме 
противоположные стороны равны, поэтому 
Треугольники 
и 
подобны по
двум углам (
как вертикальные, 
и их коэффициент подобия равен 2. Пусть 
тогда
и 
поскольку 
— середина стороны 
Стало быть, 
и 
так как
треугольники 
и 
подобны. Пусть 
тогда 
и 
Следовательно, 
и
Таким образом, 
______________________________________________________________________________________________________________________________________________________
Второе решение.
По условию прямые 
и 
параллельны, а прямая 
перпендикулярна прямой 
поэтому 
По
условию 
параллелограмм, значит, 
Отрезок 
— средняя линия треугольника 
поэтому
Кроме того, 
и 
перпендикулярны 
поэтому точки 
и 
лежат на
одной прямой. Таким образом, 
и 
параллельна 
Стало быть, 
— параллелограмм.
Пусть 
— точка пересечения его диагоналей, тогда 
Следовательно, 
и 
— медианы треугольника
, а 
— точка их пересечения, поэтому 
и, значит, 
Из подобия треугольников
и 
следует, что 
Тогда если 
то 
и 
а, значит, 
и
______________________________________________________________________________________________________________________________________________________
Третье решение.
Пусть точка 
— пересечение этой высоты с описанной окружностью треугольника 
точка 
диаметрально противоположна
точке 
на этой окружности, а точка 
— вторая точка пересечения прямой 
с этой окружностью. Из параллельности прямых 
и 
следует, что прямая 
перпендикулярна высоте 
Поскольку 
— диаметр окружности, 
и,
значит, прямые 
и 
параллельны. Стало быть, 
— средняя линия треугольника 
поэтому 
Далее,
поэтому в треугольнике 
отрезок 
является биссектрисой и высотой, а, значит, и медианой. Таким образом, 
Из
равенств 
и 
получаем, что 
По условию прямые 
и 
параллельны, а прямая 
перпендикулярна прямой 
поэтому 
и точки 
и 
диаметрально противоположны. Следовательно, 
и поэтому прямые 
и 
параллельны. Таким образом,
четырехугольник 
является параллелограммом. Стало быть, 
и отрезок 
является медианой в треугольнике
Но отрезок 
также является медианой в этом треугольнике. Следовательно, 
— точка пересечения медиан этого треугольника
и 
Тогда по теореме Фалеса 
Но мы уже знаем, что 
поэтому 
Ошибка.
Попробуйте повторить позже
В классе 
мальчиков и 
девочек (
Они расселись за круглым столом так, что никакие два мальчика и никакие две девочки не
сидят рядом. У учителя есть 
карточек, на них написаны числа 
каждое по одному разу. Он так раздал каждому
школьнику по одной карточке, что число у любой девочки больше числа у любого мальчика. Затем каждая девочка написала на листочке
сумму чисел на трех карточках: ее собственной и сидящих рядом с ней мальчиков. При каких 
все полученные 
чисел могли оказаться
равными?
Источники:
Подсказка 1
По условию понятно, что у мальчиков карточки от 1 до n, а у девочек - от n+1 до 2n. Вот пусть у девочек все суммы вышли равными какому-то m. Тогда можно ли понять, чему равно m?
Подсказка 2
Например, сумма всех чисел, полученных у девочек, будет равна mn. А с другой стороны, это сумма чисел девочек + удвоенная сумма чисел мальчиков) Посчитайте, чему тогда будет равно m.
Подсказка 3
Выйдет, что m = 2n+1 + (n+1)/2, откуда уже понятно, что n - нечетное. Можно ли для любого нечетного n подобрать пример?
Подсказка 4
Можно) Но нужно понять как. Может быть, можно как-то раздать мальчикам карты хорошо, а после по карточкам мальчиков понять, какие у каждой девочки должны быть карты?
По условию мальчики получили карточки с числами от 1 до 
а девочки карточки с числами от 
до 
Предположим, что у всех
девочек на листочках оказалось написано число 
Тогда сумма всех чисел на листочках равна 
с другой стороны она может быть
получена следующим образом: надо сложить все числа, которые есть у девочек и добавить к ним удвоенную сумму всех чисел, которые есть
у мальчиков.
Следовательно,
Стало быть, 
и 
— нечетно. Пусть 
тогда 
Для примера надо последовательно раздать
карточки мальчикам от 1 до 
идя через одного. Если теперь для каждой девочки посмотреть на сумму чисел, на карточках соседних
с ней мальчиков, то по одному разу получатся все суммы от 
до 
Дальше нужно дополнить их числами от 
до 
(раздав соответствующие карточки девочкам) так, чтобы все суммы стали равны 
Пример раздачи карточек для 
и 
показан на рисунке.
при нечетных 
Ошибка.
Попробуйте повторить позже
На доске написаны 
различных натуральных чисел. Оказалось, что для каждого написанного числа а на доске найдется еще хотя бы
одно число в такое, что 
— простое число. Докажите, что можно подчеркнуть не более 
чисел так, чтобы для каждого
неподчеркнутого числа а нашлось подчеркнутое число 
для которого 
— простое число.
Подсказка 1
Пусть числа будут вершинами. Ребром соединим числа, модуль разности которых равен простому числу. Попробуйте разбить вершины на две группы так, чтобы в первой было не больше половины вершин и каждая вершина из второй группы была соединена с хотя бы одной вершиной из первой группы.
Подсказка 2
Попробуйте для этого применить раскраску графа в 2 цвета.
Подсказка 3
Возьмите произвольную вершину А и покрасьте еë в красный. Еë соседей покрасьте в синий. Соседей соседей, которые ещë не покрашены - в красный. Что можно увидеть в графе, раскрашенном таким образом?
Рассмотрим граф, в котором вершины — числа, ребро проводится, если модуль разности этих чисел — простое число. Будем красить каждую компоненту связности этого графа в два цвета: сначала покрасим любую вершину в красный. Затем покрасим всех её соседей в синий. Затем всех соседей синих, которые ещё не покрашены, в красный. Затем соседей красных в синий. И так далее. Легко видеть, что у каждой красной вершины будет хотя бы один синий сосед, а у каждой синей — хотя бы один красный. В каждой компоненте связности выберем цвет, вершин которого не более половины, и подчеркнем вершины этого цвета. Каждая неподчеркнутая вершина будет соединена хотя бы с одной подчеркнутой.
