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

Заметим, что при любых

По сути это частный случай транснеравенства, но докажем его по индукции. База очевидна, шаг:

Осталось доказать

Отсюда в силу неравенства для среднего гармонического и среднего арифметического

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

Тогда по неравенству Коши, применённому к скобкам ниже:

Равенство достигается при .

Будем говорить, что конь контролирует клетку доски, если он бьёт эту клетку или стоит на ней. Докажем вначале, что менее коней убрать не удастся. Нам достаточно проверить, что с каждой половины доски придётся снять не менее коней. Рассмотрим для определённости верхнюю половину и отметим на ней шесть коней так, как показано на рисунке:

(для удобства они выделены разным цветом). Назовём клетки, отмеченные на рисунке кружочком, кратными, а остальные клетки простыми. Разобьём рисунок на два квадрата и зафиксируем один из них. Стоящие в квадрате чёрные кони бьют ровно по три клетки. Поэтому необходимо совершить одно из трёх действий.

Убрать двух коней, стоящих на простых клетках, контролируемых чёрными клетками (ими могут быть и сами чёрные кони).

Убрать коня, стоящего на кратной клетке. В результате белый конь из этого квадрата будет бить ровно трёх других коней. Значит, придётся ещё убрать коня с простой клетки, контролируемой белым конём (возможно, самого белого коня).

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

Приведём пример, показывающий, что коней достаточно. На рисунке отмечены кони, которых нужно снять с доски.

Назовём реверсированием набора лампочек смену состояния всех лампочек этого набора на противоположное. Отметим два простых факта.

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

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

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

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

Если , то чётно и не равно нулю (в противном случае все лампочки будут выключены), откуда

Аналогичным образом рассматриваются случаи и Для дальнейшего заметим, что для Поэтому при

Осталось показать, что можно зажечь ровно лампочки. Для этого достаточно на погашенном табло нажать один раз на произвольную лампочку.

Представим исходное число в виде где — десятичная цифра, — неотрицательные целые числа, причём Стерев цифру мы получим число По условию

Заметим, что иначе и Тогда равенство примет вид В силу условия число оканчивается не на и потому не делится на Значит, и причём Поэтому возможны два случая:

Тогда а исходное число равно где

Тогда а исходное число равно

Пусть среди фанатов «Суперорлов» и среди фанатов «Суперльвов» по лжецов. Тогда всего лжецов ровно , т е. фраза «справа от меня фанат «Суперорлов»» четное число раз была ложью.

Таким образом, четное число раз правым соседом был фанат «Суперльвов». Но такое невозможно, поскольку всего их нечетное число.

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

Назовем тех лжецов, которые не ошиблись, настоящими лжецами. По условию соседи каждого настоящего лжеца из разных племен. Поэтому соседи настоящих лжецов обязательно рыцарь и лжец. Значит, цепочка ЛРЛЛРЛ...ЛРЛ повторяется до тех пор, пока не натыкается на ненастоящего лжеца. Если до него сидит рыцарь, то после него также рыцарь. Если до него сидит лжец, то и после него сидит лжец. Следовательно, рассадка с ненастоящими лжецами может быть получена из рассадки «ЛРЛЛРЛ...ЛРЛ» с помощью либо посадки ненастоящего лжеца между двумя лжецами, либо выходу из-за стола настоящего лжеца (и тогда его соседлжец превратится в ненастоящего). Первое действие увеличивает остаток от деления общего количества сидящих за столом на 1 , второе - уменьшает на 1. Поскольку в рассадке «ЛРЛЛРЛ...ЛРЛ» количество островитян делится на 3, а 2017 дает остаток 1 при делении на 3, нам надо остаток 0 дважды уменьшить на 1. Таким образом, надо из рассадки 2019 островитян убрать двоих лжецов. Стало быть, количество лжецов равно

Рассмотрим такие векторы в

Заметим, что . Значит, , где . Тогда

Из ортогональности

Такое значение достигается при и

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

С другой стороны, в столбцах стоит по две ладьи, а в остальных не более одной, поэтому всего их не более

Следовательно, всего ладей не больше, чем

Покажем далее как разместить ладей. На доске можно разместить ладьи как показано на рисунке, а затем поставить таких квадратов по диагонали.

Мы можем выбрать последовательных блоков по бусинок. Так как каждый блок содержит хотя бы одну синюю бусинку, всего на нитке не менее синих бусинок. Кроме того, мы можем сгруппировать все бусинки в последовательных блоков по бусинок. Каждый из блоков содержит хотя бы одну зеленую бусинку, поэтому всего их на нитке не менее Значит, число красных бусинок не больше

Приведем пример, когда нитка содержит ровно красных бусинок. Разместим зеленые бусинки на позициях, кратных а синие — на местах с номерами

Остальные позиции заполним красными бусинками.

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

где — десятичная цифра, — неотрицательные целые числа, причем . Заменив цифру нулем, мы получим число . По условию

Заметим, что (иначе будет отрицательным), откуда . Таким образом, нулём заменяется старшая цифра исходного числа. Кроме того, , иначе . Тогда число кратно 10 и потому оканчивается на 0. В силу условия число оканчивается не на 0. Значит, последняя цифра равна 5 и число нечётно. Поэтому не делится на 16, откуда . Рассмотрим три случая.

1) Пусть . Тогда . Так как число нечетно и меньше 1000, цифра может принимать значения , что дает нам 4 варианта.

2) Пусть . Тогда . Так как число нечетно и меньше 100, цифра равна 2 или 6. Эти значения дают нам еще 2 варианта.

3) Пусть . Тогда . Так как число нечетно и меньше 10, мы получаем .

Заметим, что в 1) получатся четырехзначные числа, во втором случае — трехзначные, в 3 случае — двузначные. Поэтому каждое число, удовлетворяющее условию задачи, входит ровно в один из наборов 1) - 3). Значит, общее количество вариантов равно .