Тема СПБГУ

СПБГУ - задания по годам → .08 СПБГУ 2022

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

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

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

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

Подтемы раздела спбгу

Разделы подтемы СПБГУ - задания по годам

СПБГУ 2015 и ранее

СПБГУ 2016

СПБГУ 2017

СПБГУ 2018

СПБГУ 2019

СПБГУ 2020

СПБГУ 2021

СПБГУ 2022

СПБГУ 2023

СПБГУ 2024

СПБГУ 2025

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

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

Задача 1#70475

На картинке нарисовано несколько кружочков, соединённых отрезками.

$PIC$

Саша выбирает натуральное число $n$ и расставляет в кружочках различные натуральные числа так, чтобы для всех этих чисел выполнялось свойство: если числа $a$ и $b$ не соединены отрезком, то сумма $a+b$ должна быть взаимно проста с $n,$ a если соединены, то числа $a+ b$ и $n$ должны иметь общий натуральный делитель, больший 1.

При каком наименьшем $n$ существует такая расстановка?

Источники: СПБГУ-22, 11.1 (см. olympiada.spbu.ru)

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

Подсказка 1

Чтобы как-то снизить количество вариантов для n, давайте подумаем: а может ли n быть чётным?

Подсказка 2

Нет, поскольку если n чётно, то по принципу Дирихле найдутся два числа одинаковой чётности, которые не будет соединены! А значит их сумма кратна 2, поэтому НОД не будет равен 1. А теперь, зададимся вопросом: а могут ли три суммы четырех последовательно соединенных чисел быть кратны одному и тому же делителю числа n?

Подсказка 3

Нет, ведь в таком случае сумма крайних чисел(которые не соединены ребром) - тоже будет кратна этому делителю! То есть, число n не может равняться степени нечётного простого, поэтому оно кратно хотя бы двум различным нечётным простым! Теперь мы хотим взять минимальные простые(дли минимальности n), то есть, надо узнать, а может ли n быть кратно 3?

Подсказка 4

И опять-таки нет, n не может быть кратно 3. Поскольку, в таком случае найдётся пара чисел, соединенных ребром, сумма которых не будет кратна 3(для этого достаточно рассмотреть остатки при делении 3) То есть тройки не может быть среди простых! Осталось проверить, можно ли составить пример для n=5*7.

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

Сделаем два замечания.

1) $n$ нечетно. Действительно, пусть $n$ четно. Среди семи чисел всегда есть три числа одной четности, и по условию они должны быть попарно соединены. Но на картинке нет циклов длины 3.

2) Если $q$ — простой делитель $n,$ то среди четырех последовательно соединенных чисел существует пара соседних, сумма которых не кратна $q.$ Возьмем цепочку $(a,b,c,d)$ последовательно соединенных чисел. По условию

. a +d= (a+ b)− (b+c)+ (c+ d).. p

Тогда числа $a$ и $d$ тоже соединены, то есть на картинке получился цикл длины 4, которого там нет.

Из 1) и 2) вытекает, что число $n$ имеет по крайней мере два различных нечетных простых делителя. Пусть их ровно два (скажем, $p$ и $q).$ Покажем, что они отличны от 3. Допустим, например, что $p= 3.$ Не более двух чисел делятся на 3 (если их три, то они образуют цикл). Остальные числа разобьем на две группы, дающие при делении на 3 остатки 1 и 2. Одна из этих групп пуста, иначе любое число из меньшей группы будет соединено по крайней мере с тремя числами из другой группы, что невозможно. Сумма чисел из одной группы на 3 не делится. Поэтому существует трехзвенная цепочка, в которой сумма любой пары соединенных чисел не кратна 3 и, значит, делится на $q.$ Но это противоречит 2).

Таким образом, если $n$ имеет ровно два различных нечетных простых делителя, то $n ≥5 ⋅7 =35.$ Если же таких делителей больше двух, то $n≥ 3⋅5⋅7= 105 >35$ . Расстановка для $n= 35$ приведена на рисунке.

$PIC$

Ответ: 35

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

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

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

Задача 2#70476

При $x,y,z ∈ (0,2]$ найдите максимальное значение выражения

(x3− 6) 3√x+-6+ (y3− 6) 3√y-+6+ (z3 − 6)√3z-+6 A = ---------------x2+y2+-z2---------------

Источники: СПБГУ-22, 11.2 (см. olympiada.spbu.ru)

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

Подсказка 1

Для начала, давайте попробуем понять какой ответ, хотя бы на пальцах. Если мы увеличиваем х, то увеличивается значение, которое зависит от х, и в числителе, и в знаменателе, но при этом в числителе у нас степень функции больше трех, то есть, при х > 1 у нас числитель растет быстрее чем знаменатель. Все, что меньше единицы не очень понятно, но если мы верим в светлое будущее(то есть верим, что ответ достигается при х > 1) то нам надо посмотреть, чему равно значение дроби на всех двойках. И мы получим предполагаемый ответ. Теперь, когда мы знаем(а вернее - верим) в каких точках достигается ответ, то можно попробовать оценить как-то слагаемое в числителе, чтобы степень получившегося многочлена была равна 2(чтобы вероятно сократить с знаменателем), и при этом наша оценка достигалась именно в точке 2.

Подсказка 2

Корень можно оценить как <=2, так как х<=2(как раз в этой точке и достигается равенство). Второй множитель тогда можно оценить через 2х^2 - 6(опять же, равенство достигается в точке 2). Тогда, всю дробь можно оценить через (4(x^2 + y^2 + z^2) - 36)/(x^2 + y^2 + z^2). Ну а это уже достаточно легко оценить, зная, что все переменные меньше или равны 2.

Подсказка 3

Верно, выходит дробь 4 - 36/(x^2 + y^2 + z^2) <= 4 - 36/12 = 1. То есть, у нас есть оценка на дробь и при этом, мы так проводили неравенства, что каждое равенство в них достигалось в точке, в которой достигается итоговая оценка. Значит, у нас точно есть пример в котором это неравенство достигается. Запомните эту очень важную мысль, если у вас уже есть ответ и вы знаете в каких точках достигается равенство, то можно попробовать оценивать некоторые выражения, которые у вас есть так, чтобы равенство достигалось именно в той точке, где достигается равенство в изначальном выражении. Этот метод часто встречается на олимпиадах ИТМО, СПбГУ и других.

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

При $x∈ (0,2]$ справедливы неравенства $√3x-+-6≤ 2$ и $x3 ≤2x2$ , откуда

(3 ) 3√---- ( 2 ) x − 6 x+6 ≤2 2x − 6

Аналогичным образом оцениваются два других слагаемых в числителе $A.$ Поэтому

2x2− 6-+2y2−-6+2z2−-6 ----36---- 36 A ≤ 2⋅ x2+ y2+ z2 = 4− x2+ y2+z2 ≤4− 12 =1.

Равенство реализуется при $x =y =z =2.$

Ответ: 1

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

Задача 3#70477

Диагонали вписанного четырехугольника $ABCD$ пересекаются в точке $O.$ Внутри треугольника $AOB$ выбрана такая точка $K,$ что прямая $KO$ является биссектрисой угла $CKD.$ Луч $DK$ вторично пересекает описанную окружность треугольника $COK$ в точке $L,$ а луч $CK$ вторично пересекает описанную окружность треугольника $DOK$ в точке $M.$ Найдите отношение площадей треугольников $ALO$ и $BMO.$

Источники: СПБГУ-22, 11.3 (см. olympiada.spbu.ru)

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

Подсказка 1

Давайте попробуем найти какую-то связь между сторонами этих треугольников. Например: т.к. ABCD- вписан, то △BOC и △AOD подобны. Значит BO/AO=CO/DO. Что мы можем сказать про отношение CO/OD?

Подсказка 2

Мы видим, что в окружностях на CO и на OD смотрят одинаковые уголочки ∠CKO и ∠DKO => CO/OD=R₁/R₂, где R₁- радиус окружности, описанной около △COK, а R₂- радиус окружности, описанной около △DOK. Тогда BO/AO=R₁/R₂. А что мы можем сказать про отношение OL/OM?

Подсказка 3

Т.к. ∠LKO=180°-∠DKO=180°-∠CKO=∠MKO => LO/OM=R₁/R₂. Но тогда (BO*OM)/(AO*OL)=(R₁*R₂)/(R₂*R₁)=1. Мы знаем, что S(△BOM)=sin∠BOM*BO*OM/2 и S(△AOL)=sin∠AOL*AO*OL/2. Если мы докажем, что ∠BOM=∠AOL, то искомое отношение будет равно 1. Как это сделать?

Подсказка 4

Т.к. ∠OLK=∠OCK и ∠ODK=∠OMK, то треугольники △LOD и △MOC подобны по двум углам. А это значит, что ∠LOD=∠MOC. Осталось лишь докрутить это и понять, что ∠BOM=∠AOL и победа будет за нами!

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

$PIC$

Пусть $r1$ и $r2$ — радиусы окружностей, описанных около треугольников $COK$ и $DOK$ соответственно. Заметим, что

∠LKO = 180∘− ∠DKO =180∘− ∠CKO = ∠MKO

откуда $LO r1 MO- = r2$ . Кроме того, из вписанности $ABCD$ вытекает, что треугольники $AOD$ и $BOC$ подобны по двум углам. Тогда

-AO = OD-= r2 BO OC r1

так как хорды $OD$ и $OC$ соответствуют одинаковым вписанным углам. Поэтому

LO- ⋅ AO-= 1⇐⇒ LO ⋅AO =MO ⋅BO MO BO

Поскольку $∠KMO = ∠KDO$ и $∠KLO = ∠KCO,$ треугольники $MCO$ и $DLO$ подобны, откуда

∘ ∘ ∠AOL = ∠AOM +∠LOM = 180 − ∠COM +∠LOM = 180 − ∠DOL + ∠LOM =

= ∠BOL +∠LOM = ∠BOM

Таким образом,

S = 1⋅LO ⋅AO ⋅sin∠AOL = 1⋅MO ⋅BO ⋅sin∠BOM = S AOL 2 2 BOM

Ответ: 1

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

Задача 4#70478

Натуральное число $x$ в системе счисления с основанием $r(r≤ 36)$ имеет вид $ppqq,$ причем $2q =5p.$ Оказалось, что $r$ -ичная запись числа $2 x$ представляет собой семизначный палиндром с нулевой средней цифрой. (Палиндромом называется число, которое читается одинаково слева направо и справа налево). Найдите сумму $r$ -ичных цифр числа $2 x.$

Источники: СПБГУ-22, 11.4 (см. olympiada.spbu.ru)

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

Подсказка 1

Давайте потихоньку "причёсывать" задачу. Что даёт равенство из условия на числа p и q? Это значит, что мы можем записать p = 2s, а q = 5s, где s какое-то целое число. Попробуйте теперь записать x и x² в явном виде, учитывая условие с палиндромом. Получается ли там что-то относительно хорошее? Удобно ещё палиндром как-то обозначить.

Подсказка 2

Ага, получается, что после всех преобразований x= s (2r² + 5) (r + 1). Давайте обозначим палиндром abc0cba, где a, b, c соответственно какие-то цифры r - ичной системы. Тогда сгруппировав слагаемые в x² получится a(1 + r⁶) + b(r + r⁵) + c(r² + r⁴). Выходит нам нужно узнать сумму цифр, то есть 2(a+b+c). Давайте теперь приравняем два представления числа x². Учитывая, что у нас r - ичная система счисления, делимость на какое выражение тогда можно рассмотреть? Можете рассмотреть разные варианты и со временем придёте к нужному.

Подсказка 3

Верно, давайте рассмотрим делимость на (r + 1)², так как x² будет делиться на него, но нам интересна другая часть неравенства. Но появляется вопрос, как же находить остаток при делении степеней r на (r + 1)²? Попробуйте это понять, записав r^n = (1 + r -1)^n и раскрыв по биному Ньютона.

Подсказка 4

Ага, аккуратными вычислениями понимаем, что степень числа r даёт остаток (-1)^n (1-n (r+1)). Ничего страшного, если не получилось вывести, можете просто проверить по индукции, что это правда. Теперь попробуйте применить это к нашему выражению. Какой факт тогда можно понять про числа a, b, c?

Подсказка 5

Ага, из-за ограничения на a, b, c(они в r - ичной системе счисления) можно понять, что b = a + c. И раз мы узнали факт про b, то хорошо было бы тогда оценить именно его, чтобы потом сумму цифр легко найти. Поэтому попробуйте по аналогии посмотреть остаток при делении x² на 1 + r², а точнее сравнение. Там будет хорошо пописать неравенства для r и s, учитывая все ограничения, связанные с делимостью, системой счисления и количеством цифр.

Подсказка 6

Ага, для начала получаем, что r⩾6, и из сравнения, записав двойное неравенство для (9s² − b), будет следовать, что b = 9s². Далее останется только получить из верхнего ограничения для r, что s=1, а значит, b=9. Теперь осталось только посчитать правильно сумму цифр, и победа!

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

Договоримся писать $u≡ v (modw ),$ если $.. (u− v) . w.$ Пусть $p= 2s,q = 5s.$ Тогда

( ) ( ) x= ppqqr = pr2+ q (r+ 1)= s2r2+ 5 (r+ 1)

Из условия на $2 x$ вытекает равенство

( )( ) ( ) ( ) ( ) s22r2+ 52 r2+ 2r+1 = a 1+ r6 + b r+r5 + cr2+ r4 ,

(1)

где $a,b,c$ — некоторые $r$ -ичные цифры. Сделаем два наблюдения.

1) При любом натуральном $n$

rn =(1+ r− 1)n ≡ (−1)n(1− n(1 +r)) (mod(1+ r)2)

Левая часть $(1)$ кратна $(1+ r)2,$ откуда

0≡a(2− 6(1+ r))− b(2− 6(1+r))+c(2− 6(1+ r))=

= 2(1− 3(1 +r))(a− b+c) (mod (1+ r)2)

Поскольку $1− 3(1+ r)$ взаимно просто с $(1+ r)2,$ на $(1+ r)2$ делится $2(a− b+ c).$ Но это число лежит в интервале $( ) (−2r,4r)⊂ − (1 +r)2,(1+r)2 ,$ откуда $b =a+ c.$

2) Приравняем остатки левой и правой частей $(1)$ от деления на $1+ r2 :$

18s2r≡ br(1+ r4)≡2br (mod (1+r2))

Поскольку $r$ взаимно просто с $1+ r2,$ на $1+r2$ делится $( ) 2 9s2− b .$ Заметим, что $4s2 ≤ r− 1$ , иначе число $x2$ будет восьмизначным. Кроме того, $r ≥5s+ 1≥ 6$ . Поэтому

2(9s2− b)< 18s2 ≤ 9(r− 1)< 6r< 1+ r2 2

2(9s2− b)≥− 2b >− 2r >− 1− r2

Таким образом, $b= 9s2.$

Поскольку $b$ — $r$ -ичная цифра, из 2) вытекает, что $9s2 < r≤ 36$ , откуда $s2 < 4.$ Так как $s> 0,$ мы получаем $s= 1$ и $b= 9.$ В силу 1) сумма цифр $x2$ равна $2(a +b+ c)=4b= 36.$

Замечание.

Прямым вычислением проверяется, что $2255221 = 495059421$ . Таким образом, описанная в условии ситуация реализуется.

Ответ: 36

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

Задача 5#70479

При каких $n$ клетчатую доску $n ×n$ можно разбить по клеточкам на один квадрат $2× 2$ и некоторое количество полосок из пяти клеток так, что квадрат будет примыкать к стороне доски?

Источники: СПБГУ-22, 11.5 (см. olympiada.spbu.ru)

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

Подсказка 1

Если так вышло, что мы смогли разрезать на квадрат 2*2 и полоски из 5 клеток, то что можно сказать про n? А если рассмотреть его по модулю 5? Тут неопытный читатель может спросить, почему именно 5? Это связано с тем, что мы как бы от нашего квадрата отрезаем полоски длины 5, значит, вычитаем каждый раз 5, и еще 5, и т.д. Значит, остаток mod 5 инвариантен. Поэтому именно по этому модулю надо рассматривать n.

Подсказка 2

Верно, что n² = 2² (mod 5), так как кол - во клеток с одной стороны это n² , с другой стороны - это сумма клеток квадрата и полосок по 5. Значит, либо n = 5k - 3, либо n = 5k + 3. Если верно последнее, то нужно еще проверить, что квадрат 2*2 примыкает к границе. Теперь, попробуйте как-то зафиксировать квадрат, то есть быть может как-то раскрасить и/или заполнить числами таблицу, чтобы числа в квадрате(цвета) были фиксированы. Иными словами, почему мы хотим так делать? Потому что у нас нет явного параметра, который сказал бы, что квадрат примыкает к таблице и мы хотим такой сделать. Что - то типа аналога координат.

Подсказка 3

Действительно, заполним первую строку единицами, вторую - двойками и т.д. Теперь нам надо посчитать по модулю 5 с двух сторон сумму чисел в таблице. Попробуйте это сделать и прийти к противоречию.

Подсказка 4

С одной стороны, так как сумма 5 подряд идущих строк кратна 5(просто потому что у нас в каждом столбце будут все остатки mod 5, а значит их сумма будет кратна 5, и таких столбцов n), а значит останутся только 3 первые строки, а сумма чисел в остальной таблице будет кратна 5. Значит, с одной стороны сумма чисел в таблице по модулю 5 - это n + 2n + 3n = n = 3 (mod 5). C другой стороны, если мы разрезаем на полоски длины 5 и квадрат, сумма в котором 1 + 1 + 2 + 2(так как он находится в первых двух строках. Ровно для этого мы и расставляли числа, чтобы зафиксировать наш квадрат где нужно) и равна 1 по модулю 5. Значит, пришли к противоречию, так как одинаковая величина имеет разный остаток при делении на 5. Значит, случай с n = 3 (mod 5) неразрешим. Остался n = 2 (mod 5). Тут уже вряд ли тоже ответ «нет», так как тогда вообще таких квадратов не бывает, но кажется такой квадрат можно подобрать, как минимум n = 2. Попробуйте для общего вида n = 2 (mod 5) привести пример.

Подсказка 5

Да, мы можем просто поставить квадрат 2*2 в левый верхний угол. Тогда, у нас оставшиеся две части первых двух строк и первых двух столбцов, по длине будут делиться на 5, а значит мы их можем разделить на полоски по 5. А с оставшейся частью таблицы что делать?

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

Если доску $n× n$ удалось разрезать на один квадрат $2 ×2$ и некоторое количество полосок из пяти клеток, то $n2 =22+ 5m$ , откуда $n$ дает остаток 2 или 3 от деления на 5. Предположим, что $n = 5k +3$ и доску удалось разрезать требуемым образом. Развернем ее так, чтобы квадрат примыкал к верхней стороне доски. Запишем в клетках верхней строки единицы, в клетках следующей за ней строки — двойки, и так далее. Заметим, что сумма чисел в пяти последовательных строках кратна 5, поскольку

. ni+ n(i+ 1)+n(i+2)+ n(i+ 3)+n(i+4)= 5n(i+ 2)..5

Поэтому остаток от деления на 5 суммы всех расставленных чисел равен

(n+ 2n+ 3n)≡ 6(5k +3)≡ 3 (mod 5 )

С другой стороны, в каждой полоске сумма чисел кратна пяти, а в квадрате сумма чисел равна $1+ 1+2 +2= 6.$ Значит, остаток от деления на 5 суммы всех расставленных чисел равен 1 , и мы получаем противоречие.

Если $n= 5k+2,$ то можно вырезать угловой квадрат $2× 2,$ верхнюю полоску $2× 5k$ разрезать на горизонтальные полоски из пяти клеток, а прямоугольник $5k ×(5k+2)$ разрезать на вертикальные полоски из пяти клеток.

Ответ:

при $n = 5k − 3,k∈ ℕ$

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

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