Тема СПБГУ

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

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

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

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

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

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

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

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

СПБГУ 2016

СПБГУ 2017

СПБГУ 2018

СПБГУ 2019

СПБГУ 2020

СПБГУ 2021

СПБГУ 2022

СПБГУ 2023

СПБГУ 2024

СПБГУ 2025

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

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

Задача 1#39876

По краю круглого стола стоят $n$ пустых стаканов $(n≥ 3).$ Петя и Вася по очереди (начиная с Пети) наливают в них квас. Петя в свой ход наливает квас в выбранный им пустой стакан, у которого оба соседних с ним стакана либо пустые, либо полные. Вася в свой ход наливает квас в выбранный им пустой стакан, у которого один соседний с ним стакан пустой, другой — полный. Проигрывает игрок, не имеющий хода. При каких $n$ Петя выигрывает вне зависимости от действий Васи?

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

Подсказка 0!

Проанализируем и формализуем происходящее, чтобы было проще разбираться!

Подсказка 1!

Попробуем для наглядности задачи рассмотреть простые примеры. Вот если n=3, 4, то что получится? Отлично, с примерами разобрались, пусть n больше 4..

Подсказка 2!

Давайте попробуем рассмотреть "полоски" из заполненных стаканов, идущих подряд. Тогда как игроки могут на них влиять. Вася может увеличивать ее длину, а петя может только создавать новую или соединять две старые. Попробуем создать для Пети выигрышную стратегию, как-то у него явно больше полномочий!

Подсказка 3!

Петя выиграет, если останутся на столе только полоски, идущие с промежутком в один стакан! (Тогда Вася не сможет сделать ход). Так, игру мы проанализировали, осталось придумать Пете подходящую стратегию, чтобы игра свелась к такой ситуации!

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

Если стакана $3,$ то побеждает Петя за один ход. Если $4,$ то Вася ставит стакан рядом с Петей и сам побеждает за один ход, пусть далее $n >4.$

Назовём “закваской” набор из подряд идущих заполненных стаканов. Тогда Вася может увеличить размер закваски, но не может добавить новую. В то же время Петя может либо объединить две закваски, либо создать новую из одной кружки. Первым ходом Петя заполняет произвольную кружку, получая одну закваску. Назовём “застольем” набор идущих подряд по кругу заквасок. Далее пусть каждым своим ходом Петя добавляет новую закваску, пропуская один стакан после текущего конца застолья, то есть после последней закваски в нём. Пусть Петя спустя $k$ добавленных Петей заквасок не может сделать ход. Тогда всего на столе $2k$ полных стаканов и не более $k+ 1$ пустых (по одному между заквасками и максимум два после конца застолья). То есть $3k +1≥ n> 4 =⇒ k≥ 2.$ То есть найдётся хотя бы одно междузаквасье длиной один, где Петя может заполнить стакан, а Вася нет (заквасок хотя бы $2$ ). Если после застолья идёт один пустой стакан, то Вася не может сделать ход и уже проиграл (если $0,$ аналогично), иначе их два. Вася заполнит один из них и второй следующим ходом сможет заполнить Петя, то есть у него есть уже два дополнительных хода, а у Васи их не осталось, потому на следующем ходу он проиграет.

Ответ:

при $n = 3$ и при $n≥ 5$

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

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

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

Задача 2#41249

Каждая клетка таблицы $5× 6$ окрашена в один из трех цветов: синий, красный или желтый. При этом в каждой строке таблицы число красных клеток не меньше числа синих клеток и не меньше числа желтых клеток, а в каждом столбце таблицы число синих клеток не меньше числа красных клеток и не меньше желтых клеток. Сколько желтых клеток может быть в такой таблице? Приведите пример соответствующей раскраски.

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

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

Подсказка 1!

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

Подсказка 2!

2) Да, мы поняли, что во-первых красных не меньше синих во всей таблице, а синих не меньше красных. Что же это значит.........

Подсказка 3!

3) В точности, значит, что их одинаково! А одинаково ли их в каждой строке.... Попробуйте разобраться!

Подсказка 4!

4) А теперь попробуйте доразбираться с точным количеством клеток каждого цвета!

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

Применяя первое условие для каждой строки, получаем, что красного цвета не меньше, чем синего, и не меньше, чем жёлтого. С другой стороны, из второго условия число синих клеток не меньше, чем желтых и красных. Отсюда число красных равно числу синих.

Пусть в каком-то столбце синих строго больше, чем красных. Тогда во всей таблице их также больше, что невозможно, значит, равенство числа синих и красных выполнено в каждой строке и каждом столбце.

Итак, в каждом столбце по $2$ синих и красных (и $1$ жёлтая, иначе жёлтых станет больше, чем других цветов). Отсюда следует, что жёлтых может быть только $6⋅12⋅3 =6.$ При этом в каждой строке либо по $3$ синих и красных клетки, либо всех цветов поровну, откуда нетрудно построить пример.


Ж	Ж	К	К	С	С

С	С	Ж	Ж	К	К

К	К	С	С	Ж	Ж

С	С	К	К	К	С

К	К	С	С	С	К

Ответ:

$6$

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

Задача 3#41254

В таблице $3× 3$ расставлены $9$ чисел так, что все шесть произведений этих чисел в строках и в столбцах таблицы различны. Какое наибольшее количество чисел в этой таблице может равняться единице?

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

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

Подсказка 1!

Решаем методом "сначала попробовать, потом подумать". Попытацтесь сначала расставить максимально, сколько сможете. Давайте посмотрим, если все элементы это 1, то ничего хорошего не будет, все произведения одинаковы. Тогда в каком-то столбике есть хоть одно неединичное.

Подсказка 2!

Да, но с ним вместе либо в столбике, либо в строке, тоже должно быть неединичное, иначе в этой строчке и столбце мы получим одинаковые значения.

Подсказка 3!

То есть мы поняли, что неединичные числа встречаются парами. Тогда попробуем оценить, сколько должно быть пар, и, следовательно, чисел!

Подсказка 4!

дааа, пар всего пять. Тогда сколько вообще может быть неединичных чисел-то в итоге? Попробуйте использовать количество пар и строк, и столбцов, которые они занимают.

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

Очевидно, что в таблице есть неединичное число. В одной строке или в одном столбце с ним есть ещё одно неединичное, потому что иначе произведения по строке и столбцу будут равны этому числу, что противоречит их различности.

Значит, неединичные элементы встречаются парами. Одна пара влияет на три произведения — строку и два столбца или наоборот. Неединичных произведений хотя бы $5,$ поэтому пары хотя бы две. Если пар хотя бы три, то неединичных чисел хотя бы $4$ (если элементов $3,$ то все они лежат в одной строке, тогда произведения в других строках единичные и равны, аналогично со столбцами). Если же пары ровно две, то в случае их пересечения по одному элементу ими покрыты всего $4$ строки и столбца, откуда хотя бы в двух произведение единичное. Итак, неединичных элемента хотя бы $4.$

Осталось привести пример


1	1	1

1	2	3

5	7	1

Замечание. Поиск примера проще осуществлять, используя только простые числа и единицы, что здесь и реализуется.

Ответ:

$5$

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

Задача 4#80507

На доске написано произведение чисел $ИКС-$ и $КСИ,$ где буквы соответствуют различным ненулевым десятичным цифрам. Это произведение шестизначное и оканчивается на C. Вася стёр с доски все нули, после чего там осталось $---- ИК С.$ Что было написано на доске?

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

Подсказка 1

Давайте посмотрим на произведение ИКС и КСИ по модулю 10. Да, очевидно, что ИКС * КСИ ≡ С * И. Из этого несложно вывести, что C = 5; а также либо И = 1, либо И = 6.

Подсказка 2

Давайте посмотрим на сумму цифр числа по модулю 9. Да-да, для неё не так много вариантов. Несложно получить, что сумма цифр числа может принимать только 4 разных значения.

Подсказка 3

Задача конечно красивая, но без перебора здесь не обойдётся. Да, глаза боятся, а руки делают, начинаем перебирать все возможные значения букв И, К, С, стараясь сделать перебор оптимальным и быстро отбрасывать все неподходящие варианты.

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

Заметим, что $ИКС-⋅К-СИ ≡C ⋅И (mod 10).$ Значит И $⋅$ С - С = С(И - 1) $..10. .$ Тогда либо $C$ делится на 5 и С = 5, либо И - 1 делится на 5 и тогда И = 1 или 6.

Так же заметим, что $---- ---- 2 ИКС ⋅КСИ ≡(И + К + С) (mod 9),$ а с другой стороны сумма цифр произведения это И + К + С. Значит $2 (И + К + С)$ - И - К - С делится на 9. Значит, И + К + С дает остаток 1 или 0 при делении на 9. Так же

6 =1 +2+ 3≤ И + К + С ≤9 +8+ 7= 24

и значит И + К + С = 9, 10, 18 или 19.

Пусть И = 1. Тогда последние 2 цифры произведения такие же как у

2 2 10К ⋅И+ 10С +С ⋅И= 10(К + С )+С

Заметим, что последние 2 цифры или КС или 0C. Если

10(К +С2)+ С ≡ КС 10

то $С2...10,$ но C не 0?! Значит,

10(К+ С2)+ С≡10 C

К + С2...10

Если С = 2, то К = 6 и тогда $---- ---- ИК С⋅КСИ = 100602$ нам подходит.

Если С = 3, то К = 1?!

Если С = 4, то К = 4?!

Если С = 5, то К = 5?!

Если С = 6, то К = 4 и С + К + И = 11?!

Если С = 7, то К = 1?!

Если С = 8, то К = 6 и С + К + И = 15?!

Если С = 9, то К = 9 и С + К + И = 11?!

Пусть И = 6. Тогда С нечетное. Так как

ИК-С⋅КСИ-≥ 612⋅126> 70000

и у произведения первая цифра должна быть И = 6, то $-------- ИКС ⋅К СИ≥ 600000.$ Понятно, что $---- И КС ≤698$ и поэтому $---- КСИ ≥ 859$ и $К ≥ 8.$ Если К = 8, то И + К + С = С + 14 = 9, 10, 18 или 19 и из-за того, что С четное, то оно равно 4, но такие И, К и С нам не подходят (проверяется подстановкой). Если К = 9, то И + К + С = С + 15 = 9, 10, 18 или 19 и из-за того, что С четное, то оно равно 4, но такие И, К и С нам не подходят (проверяется подстановкой).

Если С = 5, то И нечетное, не 1 и не 5. Если И = 3, то И + К + С = K + 8 = 9, 10, 18 или 19 и К = 1 или 2, но ни один из этих вариантов не подходит (проверяется подстановкой). Если И = 7, то И + К + С = K + 12 = 9, 10, 18 или 19 и К = 6 или 7, но ни один из этих вариантов не подходит (проверяется подстановкой). Если И = 9, то И + К + С = K + 14 = 9, 10, 18 или 19 и К = 4 или 5, но ни один из этих вариантов не подходит (проверяется подстановкой).

Ответ:

$И-КС⋅КСИ-= 162 ⋅621$

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

Задача 5#90108

Какое наименьшее количество клеток нужно отметить в таблице $7× 7$ так, чтобы в каждой вертикальной или горизонтальной полоске $1× 4$ была хотя бы одна отмеченная клетка?

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

Подсказка 1

Как бы нам оценить количество отмеченных клеток? Например, в прямоугольнике 2x4 хотя бы 2 отмеченных клетки, так как можно склеить две полоски 1x4 и в каждой должна быть отмеченная. Может попробовать применить к общей таблице похожую идею?

Подсказка 2

7x7/4 = 12.25. Как бы нам "запихнуть" эти 12 полосок в нашу таблицу?

Подсказка 3

Уверены, вы самостоятельно сможете это сделать. Что же дальше? 12 непересекающихся полосок 1x4, значит оценка: хотя бы 12 отмеченных клеток. Что-с? Осталось построить пример... Попробуйте подумать самостоятельно.

Подсказка 4

А вот крайняя подсказка. Уж больно аппетитны средняя строка и столбец. На этом всё, успехов!

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

Разделим таблицу на 12 прямоугольников $1 ×4$ и еще одну клетку.

$PIC$

Тогда в каждом прямоугольнике должна быть отмечена хотя бы 1 клетка и всего отмечено хотя бы 12 клеток.

_________________________________________________________________________________________________________________________________________________________________________________

Отметим центральный крест без середины.

$PIC$

Тогда отмечено будет 12 клеток и в каждой вертикальной или горизонтальной в полоске $1× 4$ будет хотя бы одна отмеченная клетка.

Ответ: 12

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

Задача 6#90315

На клетчатой доске $5×7$ отмечено 9 клеток. Назовем пару клеток с общей стороной интересной, если хотя бы одна клетка из пары отмечена. Какое наибольшее количество интересных пар может быть?

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

Подсказка 1

Попробуйте прикинуть, сколько интересных пар может давать отмеченная клетка? А если эта клетка граничная? Сколько пар будет, если отмечено две соседних клетки?

Подсказка 2

Ну что же, самая первая оценка сверху у нас есть! Но достижимо ли это значение?

Подсказка 3

Чтобы понять, можно ли отметить 9 клеток так, чтобы среди них не было граничных, удобно отрезать эти самые границы нашего прямоугольника и посмотреть на оставшуюся фигуру.

Подсказка 4

Раз уж самая максимальная оценка недостижима, рассмотрим чуть-чуть меньшее число. Осталось лишь придумать удачный пример!

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

Назовем соседними две клетки с общей стороной. Число интересных пар, содержащих заданную отмеченную клетку, не больше 4, а для граничной клетки — не больше 3 . Тогда общее число интересных пар не превосходит $9⋅4= 36$ . При этом если среди отмеченных клеток есть две соседние, то содержащая их интересная пара считается дважды. Заметим, что среди 9 клеток из прямоугольника $3× 5$ обязательно есть две соседних. Поэтому среди отмеченных клеток имеется либо граничная, либо две соседних. Таким образом, общее число интересных пар не превосходит 35. Пример разметки с 35 интересными парами приведен ниже.

$PIC$

Ответ:

Курсы

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

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

Задача 7#99087

Произведение положительных чисел $a,b,c$ и $d$ равно $1.$ Докажите неравенство

a4+-b4- b4+-c4 c4+d4- d4+-a4 a2+ b2 +b2+ c2 + c2+d2 +d2+ a2 ≥ 4.

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Верно, их можно оценить между собой следующим образом: 2(a^4+ b^4) ≥ (a²+b²)²(для других дробей аналогично). Ещё это можно было понять из неравенства между средним арифметическим и средним квадратическим, возведённым в квадрат, там как раз в таком случае участвуют четвёртые степени и скобка в квадрате. Тогда после сокращения у нас останутся слагаемые вида (a² + b²)/2, что в итоге равно a² + b² + c² + d². Как же добить это неравенство? Мы ещё не всем воспользовались из условия.

Подсказка 4

Да, осталось вспомнить про неравенство о средних, и победа!

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

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

Поскольку $( 4 4) (2 2)2 2 a +b ≥ a +b ,$ справедливо неравенство

4 4 1(a2+ b2)2 2 2 aa2++-bb2 ≥ 2-a2+-b2- = a-+2b

Сложив его с тремя аналогичными неравенствами, получим, что левая часть доказываемого неравенства не меньше, чем

a2+b2+ c2+d2 ≥ 2ab+2cd≥ 4√abcd-=4

_________________________________________________________________________________________________________________________________________________________________________________

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

Заметим, что $4 4 aa2++bb2 ≥ab.$ Действительно, это неравенство после домножения на знаменатель превращается в неравенство

(a3− b3)(a− b)= a4+ b4 − a3b− ab3 ≥ 0

Но в таком виде оно очевидно, поскольку скобки в левой части имеют одинаковый знак, и их произведение неотрицательно.

Следовательно,

4 4 4 4 4 4 4 4 a2+-b2-+ b2+-c2 + c2+d2-+ d2-+a2 ≥ ab+ bc+ cd+ da ≥4 a + b b+ c c +d d +a

В последнем неравенстве мы дважды воспользовались неравенством о средних для двух чисел: $ab+cd≥ 2√ab⋅cd-=2$ и $bc+ da ≥2√bc⋅da= 2.$

Интенсивы

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

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

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


Ж	Ж	К	К	С	С

С	С	Ж	Ж	К	К

К	К	С	С	Ж	Ж

С	С	К	К	К	С

К	К	С	С	С	К


Ж	Ж	К	К	С	С

С	С	Ж	Ж	К	К

К	К	С	С	Ж	Ж

С	С	К	К	К	С

К	К	С	С	С	К


Ж	Ж	К	К	С	С

С	С	Ж	Ж	К	К

К	К	С	С	Ж	Ж

С	С	К	К	К	С

К	К	С	С	С	К