Тема СПБГУ

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

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

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

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

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

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

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

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

СПБГУ 2016

СПБГУ 2017

СПБГУ 2018

СПБГУ 2019

СПБГУ 2020

СПБГУ 2021

СПБГУ 2022

СПБГУ 2023

СПБГУ 2024

СПБГУ 2025

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

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

Задача 1#41248

При каком наибольшем $n$ на шахматной доске можно расставить $n$ королей и $n$ ладей так, чтобы никакая фигура не была под боем?

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

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

Подсказка 1!

Давайте посмотрим, если мы будем расставлять только ладей. Всего сколько небьющих ладей можно поставить на доске?

Подсказка 2!

Верно, всего 8, так как у нас всего 8 столбиков, а они все стоят в различных столбиках. Давайте попробуем теперь доказать, что n не 7. Сколько в таком случае можно поставить на доску королей?

Подсказка 3!

Осталось понять что-то со случаем, когда n это 6. И не забыть построить пример на верную оценку)

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

Если $n ≥6,$ то ладьи стоят в различных строках и столбцах, потому для королей, чтобы их не били остаётся не более $2$ строк и не более $2$ столбцов. То есть на хотя бы $6$ королей не более $4$ клеток, что невозможно. Значит, $n ≤5.$

Для $n =5$ сначала расставим короли в клетках $A1,A3,C1,C3,E1,$ то есть как можно ближе к углу $A1,$ но так, чтоб друг друга они не били и занимали не более трёх строк и столбцов. Осталось расставить ладьи. Например, можно выбрать для них клетки $B5,D6,F4,G7,H8.$

Ответ:

$5$

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

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

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

Задача 2#72030

Какое наибольшее количество фишек можно расставить на клетчатой доске $12×12$ так, чтобы на каждой диагонали располагалось не более пяти фишек?

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

Подсказка 1

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

Подсказка 2

Конечно, можно просто попробовать разбить нашу доску на 23 диагонали (сделать это можно двумя способами) и таким образом, может, получится оценить общее число фишек. Понятно, что на каждой диагонали их не более 5, но с помощью такого разбиения нам хочется увидеть ещё какие-то ограничения!

Подсказка 3

Если среди 23 диагоналей одного направления рассмотреть 10 самых "коротких", можно заметить, что фишки не могут занимать все 30 клеток, составляющих эти диагонали. Из этого и получается оценка.

Подсказка 4

Не забудьте построить пример! После того, как оценка получена и учитывая то, каким образом она получена, построение примера становится совсем несложным:)

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

Пусть $D+$ — диагональ, соединяющая левый нижний угол с правым верхним, а $D −$ — диагональ, соединяющая правый нижний угол с левым верхним. Упорядочим диагонали, параллельные $+ D ,$ сверху вниз. Пять первых и пять последних диагоналей содержат в общей сложности $30$ клеток, из которых $6$ лежат на $− D .$ Значит, на этих десяти диагоналях может располагаться не более $29$ фишек. Остальные $13$ диагоналей содержат не более чем по $5$ фишек. Поэтому общее число фишек не превосходит $29+ 5⋅13= 94.$

Пример на $94$ фишки:

$PIC$

Ответ:

$94$

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

Задача 3#72036

Имеется один черный ферзь и $n$ белых. При каком наибольшем $n$ эти фигуры можно расставить на шахматной доске так, чтобы белые ферзи не били друг друга? Ферзь не бьет насквозь через другую фигуру.

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

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

Подсказка 1

Рассмотрите строку, в которой стоит черный ферзь.

Подсказка 2

Что можно сказать об остальных строках?

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

В строке, где стоит чёрный ферзь, может быть не более двух белых ферзей , не бьющих друг друга. В остальных строках не может быть более одного ферзя. Таким образом, общее число белых ферзей не превосходит $9.$

Пример для $n= 9$ показан на рисунке.

$PIC$

Ответ:

$9$

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

Задача 4#74740

Имеется $8$ черных ладей и $n$ белых. При каком наибольшем $n$ их можно расставить на шахматной доске так, чтобы одноцветные ладьи не били друг друга? Ладья не бьет насквозь через другую фигуру.

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

Подсказка 1

Давайте попробуем понять, когда же выполняется условие задачи. Если, например, в строчке стоит 2 чёрные ладьи, то белых ладей можно поставить максимум 3. Просто между ними будут чёрные ладьи. Как в таком случае лучше всего сделать оценку в общем виде?

Подсказка 2

Да, давайте посмотрим на конкретную строчку. Пусть в ней x чёрных ладей. Тогда максимум в ней может стоять x+1 белая ладья. Но если сложить по каждой строчке так, то оценка уже появляется. Осталось только придумать пример, где почти во всех строках ладьи будут чередоваться. Победа!

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

Пусть в $i$ -й строке доски стоит $n i$ чёрных ладей. Тогда в этой строке можно расположить не более $n +1 i$ белых ладей, не бьющих друг друга. Поэтому

n≤ (n1 +1)+ (n2+ 1)+...+(n8+ 1) =(n1+ n2+...+n8)+ 8= 16

Расстановка для $16$ белых ладей показана на рисунке:

$PIC$

Ответ:

$16$

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

Задача 5#74905

Даны положительные числа $a$ , $b$ , $c$ , $d$ . Найдите минимальное значение выражения

( a+b)4 ( b+c)4 ( c+d)4 ( d+ a)4 -c-- + -d-- + -a-- + -b--

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

Подсказка 1

Для начала хочется избавиться от сумм в числителях и заменить на какое-то произведение, ведь если мы потом снова применим нер-во о средних к всем этим слагаемым, то все переменные могут сократится и останется число) Как это можно сделать?

Подсказка 2

Применим обычное нер-во о средних для a+b: a+b ≥ 2√(ab). Тогда каждое слагаемое будет вида 16a²b²/c⁴. Примените теперь еще раз неравенство о средних и получится оценка) Главное вспомнить что она достигается когда все переменные, к которым применялось неравенство равны!

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

Применим неравенство о средних:

( a+b)4 ( b+c)4 ( c+d )4 ( d+ a)4 a+ b b+ c c+ d d +a -c-- + -d-- + -a-- + -b-- ≥ 4⋅-c--⋅--d-⋅--a-⋅--b-.

Далее оценим отдельно числитель каждой дроби в последнем выражении:

√-- √ -- √-- √-- 4⋅ a+-b⋅ b+-c⋅ c+-d⋅ d+-a≥ 4⋅ 2-ab ⋅ 2-bc-⋅ 2-cd⋅ 2-da =64. c d a b c d a b

Осталось заметить, что равенство реализуется при $a= b= c= d$ .

Ответ: 64

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

Задача 6#80505

Дано натуральное число $x$ , десятичная запись которого состоит из $n$ цифр и не содержит нулей. Числа $x$ и $x2$ в десятичной системе одинаково читаются слева направо и справа налево. Найдите все $n,$ при которых такое $x$ существует.

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

Подсказка 1

Попробуйте придумать пример таких чисел.

Подсказка 2

Например, 11² = 121.

Подсказка 3

Все хорошо, пока количество единиц не превосходит 9. Докажите, что при n ≥ 10 такое x не найдется.

Подсказка 4

Запишите x² в общем виде и воспользуйтесь методом математической индукции.

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

Заметим, что

2 1 = 1

112 = 121

1112 = 12321

...

2 111111111 = 12345678987654321

Значит, $n$ от 1 до 9 подходит. Осталось доказать, что $n≥ 10$ не походит. Пусть $x= an=1...a0$ . Тогда $x2 = b0+ 10b1 +...102n−2b2n$ , где $bk = a0ak +a1ak−1+...+aka0$ для $k < n$ и $bk =b2n−2−k$ . Докажем, что $bk ≤ 9$ по индукции.

База: $b0 = a20$ . Значит, нам нужно доказать, что $a0 ≤ 3$ .

Если $a0 =an =4$ , то $5 ⋅5n−1 >x >4⋅10n−1$ и $25 ⋅52n−2 > x2 > 16⋅102n−2$ . Тогда последняя цифра у $x2$ будет 6, так как у $x$ последняя цифра 4, а первая цифра у $x2$ будет 1 или 2?! Аналогично для $an = 5,6,...,9$ .

Переход: Мы доказали, что $b0,...bk− 1 ≤9$ . Теперь докажем, что $bk ≤9$ . Мы знаем, последние $k$ цифр в $x2$ . Значит мы знаем и первые $k$ цифр. Заметим, что $x2 < 42⋅102n−2$ . Если $x2 ≥ 102n−2$ , то первая цифра у $x2$ может быть только 1, с другой стороны для этого $x≥ 3⋅10n−1$ , то есть у $x$ должна быть последняя цифра 3 и тогда у $x2$ последняя цифра 9?! Значит $102n− 1 > x2 >102n−2$ .

2n−2−k 2n−2−k bk10 =b2n−2−k10 ≤

≤x2− b 102n−2− b 102n− 3− ...b 102n−1−k <102n−1− k 2n−2 2n−3 2n−2−k+1

Отсюда $bk < 10.$

С другой стороны, $bk ≥ k+1$ для $k≤ n− 1$ . Значит, при $n ≥10$ число $b9≥ 10$ ?!

Курсы

Всё необходимое для достижения цели

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

Задача 7#80506

В однокруговом турнире по настольному теннису приняло участие 35 человек. По итогам турнира оказалось, что нет такой четверки игроков $A,B,C,D$ , что $A$ выиграл у $B,B$ — у $C,C$ — у $D$ , а $D$ — у $A.$ Каково наибольшее количество троек участников, одержавших во всех трех встречах между собой ровно по одной победе? Ничьих в теннисе не бывает.

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

Подсказка 1

Как из двух троек можно получить четвёрку?

Подсказка 2

У них должны быть 2 общих участника. Что тогда можно сказать о полученной четвёрке?

Подсказка 3

Докажите, что тройки не пересекаются, и получите оценку на их количество.

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

Пусть есть $2$ тройки, которые пересекаются по ребру. Назовем их $A,B,C$ и $A,B,D.$ Тогда не умаляя общности $A$ выиграл у $B$ и $C$ выиграл у $D,$ $B$ выиграл у $C$ и $D,$ а $A$ проиграл $C$ и $D$ . Тогда $A$ выиграл у $B,$ $B$ выиграл у $C,$ $C$ выиграл у $D,$ а $D$ выиграл у $A$ ?!

Пусть есть 2 тройки, которые пересекаются по вершине. Назовем их $A,B,C$ и $C,D,E$ . Тогда без ограничения общности $C$ выиграл у $A$ и $D$ и $D$ выиграл у $A,$ $A$ выиграл у $B,$ $B$ выиграл у $C$ , $D$ выиграл у $E$ и $E$ выиграл у $C.$ Тогда $A$ выиграл у $B,$ $B$ выиграл у $C,$ $C$ выиграл у $D,$ а $D$ выиграл у $A$ ?!

Значит, тройки не пересекаются и их не более 11. Осталось показать, что 11 троек может быть. Давайте выделим 11 непересекающихся троек и еще двойку и пронумеруем их от 1 до 14. В каждой тройке у нас будет цикл, в двойке победа будет у любого, а между группами $i$ и $j$ (где $i⁄= j)$ победа будет у группы с большим номером. Тогда если появится запретная четверка, то заметим, что если обходить ее по кругу от проигравшего к победителю, то номер группы может только расти или не изменяться. Раз мы вернемся в конце в начальную вершину, то номер группы должен все время не изменяться, и значит, все 4 вершины лежат в одной группе?! Значит, запретных четверок в таком турнире не будет.

Ответ: 11

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

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