Всего: 826 1–20 | 21–40 | 41–60 | 61–80 …
Добавить в вариант
В этой задаче запись 
где x — целое а n — натуральное, обозначает такое целое число y от 0 до n – 1, что x – y делится на n. Существует ли такая функция f, определенная для целых значений аргумента и принимающая целые значения, что при любом целом x верно
Стандартным ходом при решении задач на функциональные уравнения является подставить какое-то значение переменной, при котором два часто возникающих и не равных друг-другу тождественно выражения оказываются равны, и посмотреть, какие следствия из этого удастся вывести. Применительно к данной задаче на роль такой подстановки простится значение x0, для которого выполнялось бы 
Задумаемся, а существует ли такое x0? Условие равносильно квадратному уравнению в остатках: 
(в этом абзаце все сравнимости по модулю 7), эквивалентно
Или можно было просто перебором остатков, благо их всего 7, убедиться, что любой из 3 и 5 подходят.
Что же нам дает равенство 
Просится от обоих частей взять функцию f, а затем воспользоваться условием задачи. Имеем:
Чтобы подчеркнуть полученное, обозначим 
и выбросим среднюю часть: 
Отсюда следует 
(в этом абзаце все сравнимости по модулю 11), отметим что это именно следствие а не равносильность. Выясним, имеет ли сравнимость решения, действуя стандартно 
А извлекается ли квадратный корень из −3 по модулю 11? Заметим что
Мы перебрали все остатки, среди квадратов не нашлось −3, значит, корень не извлекается, значит, уравнение не имеет решений. Итак, требуемой функции f не существует.
Ответ: нет.
А0 Правильный ответ без доказательства −. и 0 баллов
A9 Есть все, кроме доказательства того, что нужный остаток не является квадратичным вычетом по модулю 11, или любое эквивалентное утверждение (данный квадратный трехчлен не имеет корней по модулю 11), про которое указан способ проверить его конечной последовательностью вычислений: +. и полный балл.
Обратите внимание: под данный критерий не попадают утверждения, не имеющия явной отсылки к модулю, по которому могут быть доказаны конечным перебором. Типичный пример — утверждение «число вида 44k − 3 при целом k не может быть квадратом целого числа» не подпадает под данный критерий.
В треугольнике ABC точки A1, B1, C1 — середины сторон BC, AC, AB соответственно. Точки A2, B2, C2 — середины ломанных BAC, ABC, ACB соответственно (точка называется серединой ломанной если принадлежит ломанной и делит ее на две ломанных равной длины). Докажите, что прямые A1A2, B1B2, C1C2 проходят через одну точку.
Общая преамбула ко всем трем решениям. Пусть стороны треугольника 
Не умаляя общности, 
Тогда A2 лежит на отрезке AB, причём 
Точка B2 лежит на отрезке AB, причём 
Точка C2 лежит на отрезке AC, причём 
Решение 1. Заметим, что условие задачи не симметрично. Исправим это. Найдем, где на прямой CA лежит точка A3 пересечение с прямых CA и A1A2. Обозначим отрезок AA3 = x, положительное направление в сторону, противоположную точке C. Тогда т. Менелая для точек A1, A2, A3 в треугольнике ABC гласит:
После стандартных преобразований получаем 
Поскольку 
прямая A3A2 перпендикулярная внешней биссектрисе угла, то есть параллельна внутренней. Следовательно, она является биссектрисой угла B1A1C1. Аналогично, прямые B1B2 и C1C2 — биссектрисы углов треугольника B1A1C1 и, значит, все три прямые пересекаются в центре вписанной окружности треугольника B1A1C1.
Решение 2. Назовём вневписанные окружности, касающиеся отрезков BC, CA, и AB, WA, WB, WC соответственно. Заметим, что точка A2 — середина отрезка между точками касания WC с отрезком AB и WB с продолжением луча BA за точку A. Точка A1 — середина отрезка между точками касания WC с продолжением луча за и WB с продолжением луча BC за C.
Значит, A1A2 — радикальная ось окружностей WB и WC. Аналогично, получаем, что прямые B1B2 — радикальная ось WA, WC, C1C2 — радикальная ось WA, WB. Значит, прямые A1A2, B1B2, C1C2 пересекаются в одной точке — радикальном центре окружностей WA, WB, WC.
Решение 3. Посчитаем, в каком отношении отрезки A1A2 и C1C2 делят отрезок B1B2. Применим теорему Менелая для треугольника AB1B2 и секущей C1C2. Получим
где X — точка пересечения B1B2 и C1C2, здесь и далее длины всех отрезков на прямых AB, BC, AC считаются комбинированием формул из преамбулы. Итак,
Теперь пусть X' — точка пересечения B1B2 и A1A2. Треугольники A1B1X' и A2B2X' подобны (A1B1 — средняя линия в треугольнике ABC),
Значит, 
ч. т. д.
A0 Решение задачи в частном случае (например, если ABC — равнобедренный): — 0 баллов.
Недоведенный счет в координатах (или любым другим стандартным методом) — 0 баллов.
Вася пришел в казино, имея один вшэ-коин (единственную в мире виртуальную валюту, которую можно делить на любые части; например, можно поставить на кон 
вшэкоина). В казино игрокам предлагается делать ставки на цвет шара, который будет вытащен из ящика. Фиксировано число p, причем 
Если цвет вытащенного шара совпадает с тем, на который игрок поставил x денег — игрок получит назад px денег, если не совпадает — не получит ничего. Для ставок в каждом раунде можно использовать не только деньги, имевшиеся к началу игры, но и выигрыши прошлых раундов. Перед началом игры Вася смог подсмотреть, что в ящик положили 2 черных и 3 красных шара (других шаров нет), сыгранные шары обратно в ящик не возвращаются, игра происходит пока ящик не опустеет. Какую максимальную сумму Вася может гарантированно иметь к концу розыгрыша?
Заполним табличку: в клетке (i, j) запишем, на какое максимальное число Вася может гарантированно к концу игры умножить имеющуюся у него сейчас сумму, если сейчас в ящике осталось i черных и j красных шаров. Легко понять, что стоит с краю: если уже не осталось черных шаров, то Вася может смело ставить все деньги на красный шар, соответственно увеличивая капитал в p раз за каждый из оставшихся красных шаров. Аналогично если не осталось красных. Это и отмечено в таблице ниже.
Теперь поймем, что должно стоять в клетке (i, j) если мы уже знаем, что в клетках 
и 
стоят числа x и y соответственно. Пусть для определенности 
Во-первых, в оптимальной стратегии Вася не должен делать положительные ставки на оба исхода. В самом деле, пусть по своей стратегии он должен сейчас поставить суммы a и b, причем 
Тогда пусть вместо этого он поставит 
денег на тот исход, на который должен был ставить a, и на 2b больше денег оставит не поставленными. Тогда при любом исходе он будет иметь на 
денег больше, чем имел бы, если бы ставил a и b.
Теперь поймем, сколько же Вася должен ставить. Ставить он должен на тот цвет, выпадание которого приводит в клетку с числом x (напомним, 
в противном случае если этот цвет выпадет, Вася не сможет увеличить свой капитал более чем в x раз, а мы строим стратегию лучше. Для определенности обозначим количество Васиных денег через D и пусть он поставит 
денег на цвет, выпадение которого приводит в клетку с числом x. Тогда если выпал этот цвет Вася оказался в этой клетке имея 
денег, соответственно закончит игру, имея не менее 
денег (и не может гарантированно иметь больше). Если же выпал цвет, приводящий в клетку с числом y, Вася попал туда, имея 
денег, значит, закончит игру, имея не меньше 
денег (и не может гарантированно иметь больше). Итак, гарантированный минимум при этой стратегии есть
Поскольку первая из функций под минимумом возрастающая по ϵ, а вторая — убывающая, максимум минимума достигается при значении 
для которого функции принимают одно значение. Имеем
откуда 
То есть
Иными словами, в интересующей нас клетке должно стоять число 
Пользуясь этой формулой и значениями в клетках на краях, заполним всю табличку:
Ответ: см. табл.
A0 Правильный ответ без доказательства — 0 баллов.
Любые стратегии без доказательства оптимальности (или с неверным доказательством оптимальности) — 0 баллов.
Верно доказанная лемма, что не выгодно ставить одновременно на оба цвета — 0 баллов (однако и решение, полное за исключением отсутствия объяснения, что не надо ставить на оба цвета одновременно, приравнивается к полному).
A3 Верно разобрана стратегия от момента, когда остались два шара одного цвета и один другого: ±8 баллов.
A7 При верной логике решения на последнем шаге допущена арифметическая ошибка, приведшая к неверному ответу: ±14 баллов.
A8 Решение, полное за исключением отсутствия объяснения, что не надо ставить на оба цвета одновременно: 17 баллов.
Напомним, что запись числа n в
где 
причем ak — не ноль. Назовем четырехзначное число 
интересным если 
Найдите количество упорядоченных пар интересных чисел, сумма которых — тоже интересное число (как функцию от t в замкнутой форме).
На протяжении этого решения число сочетаний из n по k обозначается 
читателей, более привыкших к нотации 
просим обращать внимание на «перевернутый» порядок индексов: 
Итак, нам требуется найти число пар 
и 
таких что 
причем выполняются три соотношения 
при 
Наше решение задачи состоит из двух этапов:
Утверждение 1. Пары 
объективно соответствуют четверкам 
таким что 
и 
Комментарий 1. Говоря более развернуто, в Утверждении 1 сказано следующее: у каждой удовлетворяющей условию задачи пары (N1, N2) их цифры (b1, c1, b2, c2) таковы, как сказано в Утверждении 1, и обратно, каждая четверка (b1, c1, b2, c2), удовлетворяющая условию Утверждения 1, ровно одним способом достраивается до пары 
удовлетворяющей условию задачи.
Утверждение 2. Количество четверок (b1, c1, b2, c2). Удовлетворяющих условиям первого утверждения, есть в точности 
План решения намечен, осталось его осуществить.
Лемма 1. Всякое интересное число имеет вид:
где 
и 
И обратно, всякая запись такого вида является корректной записью в
Доказательство. Условие, что число 
является интересным есть 
или эквивалентно
Значит, по заданному значению 
пара (a, d) восстанавливается не более чем одним способом, иначе число 
имело бы больше одной записи в 
равенство верно тождественно, кроме того, 
(за это отвечает условие 
неравенства 
и 
очевидно следуют из 
Доказательство утверждения 1. Пусть и 
—
же может и не быть правильной 
и 
Посмотрим, что происходит, когда мы «вспоминаем», что надо сделать перенос. Если перенос из разряда единиц, то d уменьшается на t, а c увеличивается на 1 , значит, всего левая часть (*) увеличивается на 1. Аналогично если перенос из разряда t — то c уменьшается на t и b увеличивается на 1, всего левая часть (*) увеличивается на 
Аналогично при переносе из разряда 
левая часть (*) уменьшается на 
Заметим, что из одного разряда не может быть сделано больше одного переноса: то что стоит в разряде есть сумма двух цифр, плюс возможно единичка, пришедшая из переноса — это точно меньше 2t. Значит, если соотношение (*) выполнялось до всех переносов и выполняется после всех — то либо не было сделано ни одного переноса, либо были сделаны все три. Докажем, что первый вариант невозможен.
В самом деле, 
по Лемме 1, аналогично 
Но если из разряда единиц не было переносов, из разряда 
его тоже не было (число осталось четырехзначным), тогда сумма цифр в этих разрядах сейчас равна
Но такую сумму двумя цифрами можно набрать единственным образом: 
То есть 
По Лемме 1 это означает
то есть 
—
Итак, должны осуществиться ровно три переноса. Докажем, что это эквивалентно условию 
В разряде единиц стоит
при 
перенос есть; в разряде t стоит 
(единичка пришла от переноса) — перенос есть тогда и только тогда, когда 
в разряде стоит
при перенос есть, наконец из разряда переноса нет когда он есть из разряда единиц.
Для Утверждения 2 мы приведем комбинаторное доказательство.
Комбинаторное доказательство Утверждения 2 с наводящими соображениями. Напомним, что выражение 
считает способы расставить в ряд n белых и k черных шаров. Научимся через такие функции выражать ответы в задачах типа нашей, начнем с более простой.
Поучительный пример 1. Пусть мы хотим перечислить пары (c1, c2), такие что 
и Построим для этого биекцию между такими парами, и расстановками в ряд двух черных и 
белого шарика следующим образом: для расстановки посчитаем число белых шариков, стоящих правее левого черного шарика (не важно до или после правого черного) — назовем это число c1; аналогично посчитаем число белых шаров, стоящих левее правого черного — назовем это число c2. Очевидно, оба числа лежат в заказанных пределах, притом — каждый белый шарик посчитан хотя бы один раз, те что стоят между черными посчитаны дважды. Оставляем читателю додумать, почему построена именно биекция, то есть по паре (c1, c2) можно построить расстановку шариков в ряд, притом ровно одну. Итак, количество таких пар (c1, c2) есть в точности 
Поучительный пример 2. Отлично, усложним задачу. Пусть мы ищем число четверок (b1, c1, b2, c2), таких что
и наконец Давайте смотреть на расстановки в ряд четырех черных шаров и белого. Первый черный шар будет отвечать за b1, второй за c1, для каждого из них соответствующими числами мы будем называть число белых шаров вправо от них, тогда автоматически получится, что 
(всякий белый шар, который правее второго слева черного, также правее и первого слева черного). Аналогично третий и четвертый черные шары отвечают за числа c1 и b2 соответственно, причем числа равны Количеству белых шаров левее соответствующего черного. Аналогично имеем 
а также полностью аналогично прошлому примеру. Итак, количество таких четверок (b1, c1, b2, c2) есть в точности 
A теперь собственно то, что нам нужно. Напомним: мы ищем число таких четверок b1, c1, b2, c2, что
и наконец Чтобы действовать как в примере 2 нам нужно было бы пересчитать расстановки в ряд 4 черных и белого шара, такие что между первым и вторым черными стоят хотя бы два белых, и между третьим и четвертым черными стоят хотя бы два белых. Сделаем это так: перечислим все расстановки в ряд четырех черных и t − 5 белых, таких расстановок ровно
Теперь в каждую из расстановок добавим два белых шара между первым и вторым черными, и два белых между третьим и четвертым черными. Оставляем читателю доказать, что построена биекция между множеством всех расстановок четырех черных и t − 5 белых, и множеством расстановок с приведенным выше дополнительным условием четырех черных и t − 1 белого.
Заметим, что возможно и чисто алгебраическое доказательство утверждения 2, которое мы не приводим по двум причинам: во-первых, оно ничем не хорошо по сравнению с комбинаторным, но технически существенно сложнее. Во-вторых, никто из участников, пытавшихся пройти этим путем, к завершению не подошел даже близко.
Ответ: 
А0 Попытка для частных значений t решить задачу перебором: 0 баллов.
Найдено количество интересных чисел вместо того, что спрашивалось в задаче: 0 баллов (но на этом пути могут быть получены промежуточные результаты, подпадающие под действие критерия А3 и оцениваемые по нему).
A3 Доказано, что интересное число задается двумя своими цифрами, получено выражение через эти цифры двух оставшихся и выписаны неравенства, которым должны удовлетворять генерирующие цифры. Например:
— для a и b выражаются как 
причем 
— для b и c выражаются как 
причем 
— для b и d выражаются как 
причем 
8 баллов. Подчеркнем, что выражения двух оставшихся цифр без неравенства на две генерирующие не стоят ничего.
B3 Доказано, что при если сложении двух интересных чисел получается интересное, то есть переносы хотя бы в двух разрядах: 8 баллов (аддитивно с А3, итого АЗ + В3 = 16). Что в этом случае есть все три переноса — не приносит дополнительных баллов.
Точка M — середина стороны BC треугольника ABC. Касательные, проведённые из M к вписанной окружности треугольника ABC, касаются этой окружности в точках P, Q. Касательные из M к вневписанной окружности ABC, касающейся стороны BC, касаются этой окружности в точках R, S. Прямые PQ, RS пересекаются в точке X. Оказалось, что 
Найдите угол 
План решения: мы докажем два ключевых факта: что биссектриса AL угла BAC также является биссектрисой угла XAM; и что AX перпендикулярна BC. Тогда в треугольнике ABC медиана AM и высота AX симметричны относительно биссектрисы AL — отсюда мы выведем, что угол A прямой.
Через Ω1 и Ω2 обозначим вписанную и вневписанную окружность из условия соответственно, через I1 и I2 — их центры. Пусть P — та из точек касания P, Q, что лежит на стороне BC, аналогично пусть R лежит на BC. Введя обозначения для длин сторон треугольника и явным образом выразив отрезки, на которые точки касания вписанной и вневписанной окружности делят стороны треугольника, можно показать что 
(оставляется читателю). Значит, все четыре точки P, Q, R, S лежат на окружности Г с центром M и радиусом PM.
Точка X лежит на радикальной оси (для пересекающихся окружностей — просто прямой через общие точки) окружностей Ω1 и Г; аналогично X лежит на радикальной оси окружностей Ω2 и Г; значит, X лежит и на радикальной оси Ω1 и Ω2. Но M тоже лежит на этой радикальной оси, поскольку касательные из M равны. Значит, XM — радикальная ось Ω1 и Ω2, тогда она перпендикулярна биссектрисе AL угла BAC. Поскольку 
в равнобедренном треугольнике высота AL является биссектрисой. Первый ключевой факт доказан.
Заметим что прямая QR перпендикулярна PQ (это ясно, если вспомнить определение окружности Г, значит, QR проходит через точку P', симметричную точке P относительно I1.
Лемма 1. Пусть в треугольнике вписанная окружность W с центром I и вневписанная окружность WA с центром IA касаются стороны в точках P, R соответственно. Точка P' симметрична P относительно I. Точка R' симметрична R относительно IA. Тогда точки A, P, R' лежат на одной прямой, а также точки A, P', R лежат на одной прямой.
Доказательство. Но другое описание точки P' таково: если рассмотреть гомотетию с центром в A, переводящую Ω2 в Ω1, то образом точки R будет точка P'. Значит, при этой гомотетии прямая QR (она же P'R) остается на месте, значит, эта прямая проходит через точку A.
Итак, PQ — высота треугольника APR. Аналогично и RS — высота треугольника APR, значит — его ортоцентр, то есть прямая AX перпендикулярна прямой PR, она же BC. Второй ключевой факт доказан.
Итак, в треугольнике ABC высота и медиана из вершины A симметричны относительно биссектрисы из этой вершины. Тогда угол A прямой. Это следует из
Лемма 2. В произвольном треугольнике ABC с центром описанной окружности O прямая, содержащая высоту AH и прямая AO симметричны относительно биссектрисы угла A.
Доказательство оставляем читателю в качестве полезного упражнения. Указание: посчитайте углы через дуги.
А0 Недоведенный счет в координатах, решение задачи при дополнительных предположениях: 0 баллов.
A1 Отмечено, что четырехугольник PQRS — вписанный: 2 балла.
A2 K предыдущему добавлено, что точка X — радикальный центр трех одружностей: вписанной, вневписанной и описанной около PQRS: 5 баллов.
А3 
— ортоцентр APR: 10 баллов.
A5 Доказано, что биссектриса угла BAC также является биссектрисой угла XAM: 15 баллов.
Баллы за разные пункты не скалдывается, меньшие уже включены в большие.
Рассматриваются всевозможные наборы действительных чисел
Докажем что 
Рассмотрим набор из 1010 чисел −1, и 1011 чисел 
Ясно что при любой расстановке по кругу два положительных окажутся рядом, значит, найдется дуга с суммой 
Покажем, что при любом количестве чисел n верна оценка
Доказывать это будем, как ни странно, индукцией по n. База при 
проверяется непосредственно. Так же заметим, что для расстановки чисел по кругу условие, что сумма на любой дуге по модулю не больше C, эквивалентно условию, что для произвольной позиции на круге множество сумм по всем дугам, имеющим левый конец в этой позиции, умещается на отрезке длины C. Этой переформулировкой мы и будем пользоваться в дальнейшем.
Лемма. Определим операцию преобразования набора: заменим в наборе два числа разных знаков a и −b (пусть 
на одно число a − b. Тогда если полученный набор допускает расстановку для некоторого числа C и выполняется 
то исходный допускал расстановку для C.
Доказательство. Расставим по кругу преобразованный набор, и воспользуемся переформулированным условием, начиная от позиции, на которой стоит добавленное число a − b. Тогда по переформулированному условию все суммы дуг, начинающихся в этой позиции (включая сумму, равную нулю) покрываются отрезком длины C. Тогда в этот отрезок попало и одно из чисел a и −b, поскольку они не могут лежать с разных сторон от отрезка — расстоянии между ними равно a + b, то есть не превосходит длинны отрезка. Если попало число a — заменим a − b на числа a, −b (в таком порядке), у полученной расстановки те же суммы, что у исходной, и еще сумма a, лежащая где нужно. Аналогично заменим на числа −b, a если попало −b.
Теперь докажем индукционный переход. Рассмотрим набор из n чисел не больших 1 по модулю с суммой 0. Рассмотрим наименьшие по модулю положительное и отрицательное число. Если их сумма модулей не больше
то можно воспользоваться Леммой. Пусть их сумма больше.
Тогда это возможно при четном n только если положительных и отрицательных поровну. Тогда разобьем их на пары, как при доказательстве Леммы. Тогда сумма чисел в каждой паре (то есть «новое» число) по модулю не превосходит
Наша задача расположить их по кругу так, чтобы для некоторой позиции A сумма по любой дуге с левым концом в A лежала бы на отрезке
это очевидно можно сделать. Теперь вспомним, что каждое новое число это на самом деле два старых, и расположим эти старые в порядке положительное отрицательное. Добавились суммы, получающиеся из старых добавлением одного из первых чисел пары, то есть не более чем единицы. Поскольку все старые суммы лежали на отрезке длины
теперь все суммы лежат на отрезке длины
что и требовалось. Пусть 
тогда сумма модулей наименьших по модулю положительного и отрицательного чисел может быть слишком большой только если количество положительных и отрицательных чисел отличается на единицу. Без ограничения общности пусть положительных k. Каждое положительное число, кроме самого маленького, объединим в пару с отрицательным. Получили набор из k чисел (оставшееся положительное и k − 1 сумм в парах, суммы в парах по модулю не больше 
оставшееся положительное обозначим x, естественно
Мы хотим эти числа расставить по кругу с началом отсчета так, чтобы последним стояло x, а все суммы кроме суммы k − 1 пары лежали на отрезке 
Для этого сначала выберем пару, которая встанет 
−й
а такая найдется из среднего значения. Затем все остальные пары расставить как угодно, чтобы их сумма не выходила из коридора — это возможно, потому что модуль чисел маленький.
Теперь перейдем от расстановки пар к расстановки исходных чисел, поставив числа в каждой паре в порядке отрицательное-положительное. Поскольку до этого все суммы лежали на отрезке 
значит, и на отрезке 
теперь они лежат на отрезке 
— победа.
Ответ: 
A B направлении примера (т. е. доказательства, что 
Пример, показывающий что для меньшего C не работает — ±3 баллов.
Любые меньшие значения C: 0 баллов.
B Продвижения в направлении оценки.
B0 Любая оценка не сильнее чем 
где a — максимальное из положительных чисел, а b — минимальное (т. е. максимальное по модулю) из отрицательных: 0 баллов.
Любой алгоритм расстановки, обеспечивающий лишь что, что сумма на дугах с одним фиксированным концом не больше C: 0 баллов.
Гипотенуза AB прямоугольного треугольника ABC касается вписанной и соответствующей вневписанной окружностей в точках T1, T2 соответственно. Окружность, проходящая через середины сторон, касается этих же окружностей в точках S1, S2 соответственно. Докажите, что 
.
Введем обозначения для длин сторон: 
и Сделаем инверсию с центром и радиусом 
с симметрией относительно биссектрисы угла C. Гипотенуза и окружность Эйлера треугольника переходят друг в друга. В самом деле, середины сторон прямоугольного треугольника и вершина его прямого угла образуют лежат в вершинах прямоугольника, значит, все четыре на одной окружности. Значит, при инверсии образ окружности — прямая, легко посчитать, что эта прямая отсекает от лучей CA и CB отрезки длины a и b соответственно, то есть симметрична AB относительно биссектрисы угла A.
Лемма. Вписанная и вневписанная окружности треугольника АВС переходят друг в друга.
Доказательство. Действительно, касательная из к вписанной окружности равна её радиусу r, а касательная из к вневписанной окружности равна полупериметру p. Таким образом, их произведение 
—
Следовательно 
переходит в S2, а T2 переходит в S1. Угол 
переходит в угол 
значит, они равны.
A7 полное решение за исключением доказательства, что при инверсимметрии вписанная окружность переходит во вневписанную: ±18 баллов.
Найдите все действительные числа d, для которых существуют многочлены от одной переменной P и Q, такие что равенство
выполняется при всех значениях x кроме конечного числа.
Первое решение. Сразу заметим, что при 
равенство из условия невозможно, так что далее мы везде считаем, что 
даже когда не напоминаем об этом явно (это тривиальное замечание, но если его не сделать — можно потерять немного баллов).
Предположим, что такие многочлены P и Q нашлись. Тогда можно считать, что они взаимнопросты (иначе поделим оба на общий множитель — новая пара тоже удовлетворяет условию), и у Q старший коэффициент равен 1 (домножим P и Q на константу, чтобы старший коэффициент стал равен 1). Введем обозначение для разложения Q на линейные множители (естественно, воспользовавшись существованием такого разложения в комплексных числах):
Далее нам потребуется известное утверждение о разложении рациональной функции в сумму простейших дробей.
Лемма (о разложении на простейшие дроби). Существует и единственно представление вида
где степень Pi(x) меньше ni при 
причем 
Это стандартный факт, доказательство которого можно прочесть во многих учебниках, и даже в Википедии в статье «Разложение рациональной дроби на простейшие».
Для комплексного числа α множество чисел вида 
где 
—
Ключевое утверждение: если
Доказательство. Пусть 
и 
такие минимальное и максимальное значения m, при которых 
является корнем Q. Заметим, что и определены корректно: множество значений m не пусто (поскольку 0 подходит) и конечно, поскольку у Q конечное число корней (первое место, в котором важно, что ). Тогда пусть не оба числа 0 и 1 лежат в цепи α. Тогда одно из двух чисел 
и 
не является ни 0, ни 1 (второе место: нам важно, что и 
—
—
и разложим левую часть на простейшие дроби. Поскольку αi — корень Q, в разложение 
входит член со знаменателем 
и ненулевым числителем. Но 
—
иначе 
было бы корнем Q(x), что противоречило бы максимальности 
Тогда член со знаменателем не входит в разложение 
значит, члену с таким знаменателем слева не с чем сократиться — но он не входит в правую часть — противоречие. Аналогично пусть 
—
и разложим левую часть на простейшие дроби. Поскольку 
— в разложение 
входит член со знаменателем 
и ненулевым числителем. Но
не корень Q(x), обратное противоречило бы минимальности 
Тогда член со знаменателем не входит в разложение 
значит, члену с таким знаменателем слева не с чем сократиться — но он не входит в правую часть — противоречие.
Итак, мы доказали, что если у многочлена Q есть комплексные корни, то в цепь этого корня входят числа 0 и 1, то есть выполняется равенство 
для какого-то целого m. Если же у Q нет комплексных корней, то он — ненулевая константа, то есть и —
(это еще одно почти тривиальное замечание, не сделав которое можно потерять немного баллов).
Осталось показать, что все значения вида где 
подходят. Для 
достаточно взять функцию
и привести сумму к общему знаменателю, числитель взять в качестве P а знаменатель — Q. Для 
то же самое сделать с суммой
Ответ: 
А — здесь оцениваются продвижения в построении примеров для подходящих d.
A0 Примеры только для значений 1 и −1 стоят 0 баллов.
A7 Явным образом указано Q, на коэффициенты P выписана система линейных уравнений. Сказано, что она верхнетреугольная, но нет упоминания (тем более — доказательства), что на диагонали коэффициенты не нулевые — 7 баллов.
А9 Пример при всех возможных значениях d — ±10 баллов.
B — здесь оцениваются продвижения в доказательстве, что не подходят все не подходящие значения d. Все пункты с этой литерой аддитивны с серией А.
B3 При альтернативном пути решения доказано, что существует некоторый многочлен R(x) (степень которого не зависит от d), такой что R(x)Q(x) делится на 
—
B4 Доказано, что 
делится на —
В6 В лемме о разложении на простейшие нет упоминания, что числитель у любого корня ненулевой — 11 баллов.
B8 Лемма о разложении на простейшие дроби сформулирована но не доказывалась или доказывалась неверно — то же, что в В9
В9 Полное доказательство, что подходят только эти значения d: 22 балла (в сумме с А9 дает максимальный балл по задаче).
Через X (α) будем обозначать точку с координатами 
(все такие лежат на окружности радиуса 1 c центром в начале координат). Выбрали произвольный угол 
и провели хорды
(на шаге номер n проводится хорда 
Если хорда уже была проведена — она не проводится второй раз. Оказалось, что все проведенные хорды не пересекаются иначе чем по концам. Докажите, что всего проведено конечное число хорд.
Нам будет полезен аналог целой части 
выражающий для двух чисел с разностью x расстояние по окружности между образами этих чисел, если намотать числовую прямую на единичную окружность: будем говорить, что 
при 
и 
при 
(здесь {x} обозначает обычную целую часть числа x). Тогда, например, если длинна дуги между точками α и β равна 
то длинна дуги между 2022α и 2022β равна 
Предположим противное: что проведено бесконечное число хорд, но все они не пересекаются. Нам будет удобно представлять, что мы последовательно добавляем новые точки в порядке их номеров и рисуем получающиеся хорды.
Для краткости точку 
будем обозначать просто Pn. Заметим, что точки не повторяются: если бы оказалось, что 
при 
то выполнялось бы 
и т. д., тогда число хорд было бы конечным. Итак, каждая новая точка попадает строго между ранее поставленными.
Определим по индукции понятие активной дуги n-го шага. Для натурального 
будем ей считать ту из двух дуг P0P1, на которую попадает P2. Заметим, что тогда все точки Pn лежат на активной дуге первого шага. В самом деле, пусть все точки от 2-й до m-й лежат на активной дуге 1-го шага, а 
-я
пересекаются.
Теперь предположим, что мы уже индукцией по n доказали, что все точки Pm попадают на активную дугу n-го шага при 
Определим активную дугу 
-го шага. 
лежит на n-й активной дуге, значит, делит ее на две части. На одну из этих частей попадает точка 
— -го
Понятно, что концы дуги — это какие-то из предыдущих точек P, значит, есть фрагмент ломанной, соединяющий их. Значит, если Pm еще лежит на дуге, а —
не совпадает ни с одной из предыдущих точек P (что упоминалось ранее) — значит, пересекается с указанным фрагментом ломанной.
Как легко видеть, каждая следующая активная дуга является подмножеством предыдущей. Более того, обозначим через 
длину активной дуги, а через 
—
( той из двух, которая лежит внутри активной). Тогда или 
или 
Поскольку 
—
Если предел равен нулю, то нулю же равен и предел последовательности 
поскольку 
Но заметим, что 
То есть если 
то 
Кроме того, всегда не равно нулю (иначе две точки совпали). Значит, для 
в последовательности встречаются члены большие 
со сколь угодно большими номерами — ноль не является пределом.
Пусть предел равен положительному числу a. Тогда по (*) последовательность разбилась на две подпоследовательности, предел одной равен нулю, предел другой — a, причем по доказанному выше вторая содержит бесконечное число членов. Заметим, что 
Тогда аналогично
если 
Выберем 
будем говорить о числах 0 и a как о двух пределах. Начиная с какого-то номера все должны попадать в — к 
расстояние до предела будет расти в 2022 раза — рано или поздно выскочит из -окрестности — окрестности другого предела.
Комментарии. Многие участники пытались доказывать факт, что при фиксированных α и φ углы вида 
(при всех натуральных n) всюду плотны на окружности. По-видимому, перепутав его с фактом, что для не соизмеримого с π угла α углы вида na всюду плотны на окружности. Второй факт верен, первый нет.
А0 Утверждения вида «если 
рационально, то различных точек конечное число», если точка повторилась то повторятся и все последующие, если точек конечное число то и хорд конечное число: 0 баллов.
A3 Четкая формулировка и доказательство леммы, что последовательность длин хорд не может иметь предел — 16 баллов.
A4 В большей общности: что последовательность длин хорд не может разбиваться на две, каждая из которых имеет предел (причем одна — нулевой) — 24 балла.
Либо аналогичное утверждение про последовательность точек, а не длин хорд между последовательными точками.
В3 Четкая структура решения, сводящая задачу к лемме из критерия А4, но без доказательства этой леммы — 18 баллов.
Фокусник и его Ассистент готовятся показать следующий фокус. Фокуснику завяжут глаза, после чего один из зрителей напишет на доске 60-битное слово (последовательность из 60 нулей и единиц). Ассистент уверен, что сможет незаметно передать фокуснику записку, содержащую 44 бита (не обязательно биты загаданного слова, может написать какие хочет). После чего Фокусник должен будет назвать слово. Для какого наибольшего числа C Фокусник и Ассистент могут придумать стратегию, позволяющую всегда назвать слово, совпавшее хотя бы в C битах с написанным зрителем.
Докажем оценку 
Пусть существует стратегия, позволяющая ошибаться не более чем в k битах (т. е. 
Тогда заметим, что Наблюдатель, знающий стратегию Фокусника, сообщенное Ассистентом слово, и набор бит, в которых ошибся Фокусник, может восстановить написанное Зрителем слово. В самом деле, Наблюдатель берет слово, которое должен был написать Фокусник, и меняет его в тех местах, где Фокусник ошибся. Значит, количество различных пар вида «слово сообщенное Ассистентом и набор мест, в которых фокусник ошибся» не меньше, чем различных слов, которые мог написать зритель. То есть
Перепишем в виде
и заметим, что при 
неравенство неверно: 
но
Теперь попробуем показать, из каких соображений строится пример. Для начала напомним конструкцию, известную как математикам так и программистам: двоичный код длины 15, позволяющий передать 11 бит полезной информации и исправить ошибку не более чем в одном бите (также известен как
Для начала заметим, что есть ровно 11 слов длины 4 из нулей и единиц, содержащих хотя бы две единицы (всего слов 
минус одно из одних нулей, минус четыре с одной единицей). Припишем такие слова номерам от 1 до 11 как угодно, например как в таблице:
| №1 | №2 | №3 | №4 | №5 | №6 | №7 | №8 | №9 | №10 | №11 |
| 0011 | 0101 | 1001 | 0110 | 1010 | 1100 | 0111 | 1011 | 1101 | 1110 | 1111 |
Теперь построим код таким образом: в первые 11 бит запишем те биты, которые хотим передать (первые 11 позиций будем называть информационными). В последние 4 бита запишем следующие контрольные суммы. В 12-й запишем сумму по модулю два тех из первых 11 бит, приписанное 4-значное число которых имеет 1 в первом разряде, то есть биты №№ 3, 5, 6, 8, 9, 10, 11. В 13-й — сумму тех из первых 11 бит, приписанное 4-значное число которых имеет 1 во втором разряде, в
Пусть Получатель получил кодовое слово, возможно искаженное в одном бите. Получатель точно так же по первым 11 битам посчитает 4 контрольные суммы, и сравнит их с четырьмя полученными. Если совпали все четыре — то слово дошло без искажений. В самом деле, если бы исказился контрольный бит — в нем было бы расхождение, а если информационный — то расхождения были бы во всех контрольных, в которые он входит. Аналогично, если расхождение есть ровно в одном контрольном бите, то исказился именно он. В самом деле, если исказился другой контрольный — то все информационные дошли правильно, тогда в этом контрольном расхождения бы не было; а если исказился информационный, то все контрольные дошли правильно, и тогда расхождения были бы во всех контрольных, в которые входит искаженный информационный, а таких контрольных хотя бы два (именно за этим мы приписывали комбинации нулей и единиц, содержащие хотя бы две единицы). По аналогичным соображениям если получатель видит не менее двух расхождений с контрольными битами, то искажен точно информационный. Тогда достаточно из 11 информационных позиций выбрать ту, в приписанном
Теперь подумаем в других терминах, что же мы построили. У нас есть код из 211 кодовых слов. Каждое из этих слов можно исказить 16 способами (ничего не менять, или изменить один из 15 бит). Все 
полученных в результате слов будут разными. В самом деле, если бы какое-то слово w получалось двумя разными способами: искажением кодового слова u1 и искажением кодового слова u2 (в обоих случаях — не более чем в одном бите), то код бы не исправлял одну ошибку — Получатель может получить слово w, но в этом случае не может понять, посылали ему u1 или u2. Итак, все слов разные, но это означает что вообще любое из слов длины 15 получается искажением какого-то из кодовых слов не более чем в одном бите.
На этом и построим стратегию Фокусника и Ассистента. Ассистент видит написанное зрителем
Ответ: 
A: эти критерии оценивают прогресс в доказательстве оценки
А0 Голый ответ −. и 0 баллов. Доказательство, что 
: также 0 баллов.
A7 Получено ключевое утверждение, что если можно ошибиться не более k раз (т. е. 
то
но не указано правильное значение k, для которого неравенство становится верным: ± и 18 баллов.
А9 Корректно доказанная оценка 干 и 20 баллов.
Баллы за разные литеры складываются
В0 Построени любых алгоритмов, доказывающих 
баллов.
В3 Мечты в духе «нас бы устроил Хэминговский код с такими-то свойствами», если требуется исправлять больше одной ошибки, и нет соображений, как его строить — 10 баллов.
B8 Пример чистый по модулю существования совершенного кода Хэминга, исправляющего одну ошибку, которое постулировано но не доказано — то же, что В9.
В9 Пример 
и 30 баллов (таким образом A9 + B9 дает полную цену задачи).
Решите уравнение:
Данное уравнение равносильно уравнению 
из которого и находится единственный действительный корень.
Ответ: 
| Критерии | Оценка | Баллы |
|---|---|---|
| Задача решена полностью. | + | 10 |
| Решение задачи, содержит верную общую схему решения, но в результате описки или арифметической ошибки получен неверный ответ. | ± | 7 |
| Решение содержит значительное продвижение в верном направлении. | + / 2 | 5 |
| Решение в целом неверное или незаконченное, но содержит определенное содержательное продвижение в верном направлении. | ∓ | 2 |
| Задача не решена, содержательных продвижений нет. | − | 0 |
| Задача не решалась. | 0 | 0 |
Два прямоугольника ABCD и AEFG имеют общую вершину А и расположены на плоскости так, что точки B, E, D и G лежат на одной прямой (в указанном порядке). Пусть прямые ВС и GF пересекаются в точке Т, а прямые СD и EF — в точке H. Докажите, что точки А, Н и T лежат на одной прямой.
Пусть прямые CD и FG пересекаются в точке M, а прямые BC и EF —в точке N. Четырехугольники DHEA и FHCT вписанные (у каждого из них два противоположных угла равны 90°), следовательно,
и 
Так как
то четырехугольник ADGM также вписанный. Поэтому 
значит,
Аналогично, 
следовательно, точки M, A и N лежат на одной прямой. Тогда H — ортоцентр треугольника TMN, а точки T, H и A лежат на его высоте.
| Критерии | Оценка | Баллы |
|---|---|---|
| Задача решена полностью. | + | 12 |
| Решение задачи, содержит верную общую схему решения, но в результате описки или арифметической ошибки получен неверный ответ. | ± | 8 |
| Решение содержит значительное продвижение в верном направлении. | ±2 | 6 |
| Решение в целом неверное или незаконченное, но содержит определенное содержательное продвижение в верном направлении. | ± | 2 |
| Задача не решена, содержательных продвижений нет. | − | 0 |
| Задача не решалась. | 0 | 0 |
Пусть m и n — натуральные числа. Докажите, что число 
можно представить в виде суммы двух точных квадратов тогда и только тогда, когда число 
чётное.
Если m и n оба четны, то 
и
Если m и n оба нечетны, то 
и
Если m и n имеют разную четность, то
Но остатки точных квадратов по модулю 8 могут принимать лишь значения 0, 1 и 4 и остаток их суммы по модулю 8 не может быть равен 6.
| Критерии | Оценка | Баллы |
|---|---|---|
| Задача решена полностью. | + | 12 |
| Решение задачи, содержит верную общую схему решения, но в результате описки или арифметической ошибки получен неверный ответ. | ± | 8 |
| Решение содержит значительное продвижение в верном направлении. | ±2 | 6 |
| Решение в целом неверное или незаконченное, но содержит определенное содержательное продвижение в верном направлении. | ± | 2 |
| Задача не решена, содержательных продвижений нет. | − | 0 |
| Задача не решалась. | 0 | 0 |
Две окружности C1(O1) и C2(O2) с различными радиусами пересекаются в точках A и B. Касательная из точки A к C1 пересекает касательную из точки B к C2 в точке M. Докажите, что окружности из точки M видны под одинаковыми углами. (Говорят, что окружность видна из точки вне ее под углом α, если касательные, проведенные из этой точки к окружности, образуют угол α).
Достаточно доказать, что
что равносильно
откуда
вне зависимости от того, какая из дуг AB выбирается — большая или меньшая. Аналогично, 
следовательно,
По теореме синусов из треугольника
Из двух последних равенств вытекает доказываемое равенство.
| Критерии | Оценка | Баллы |
|---|---|---|
| Задача решена полностью. | + | 12 |
| Решение задачи, содержит верную общую схему решения, но в результате описки или арифметической ошибки получен неверный ответ. | ± | 8 |
| Решение содержит значительное продвижение в верном направлении. | ±2 | 6 |
| Решение в целом неверное или незаконченное, но содержит определенное содержательное продвижение в верном направлении. | ± | 2 |
| Задача не решена, содержательных продвижений нет. | − | 0 |
| Задача не решалась. | 0 | 0 |
Пусть xk — положительный корень уравнения 
Докажите, что
Так как 
то 
следовательно, 
и 
то есть 
Поэтому
то есть 
или 
Значит,
| Критерии | Оценка | Баллы |
|---|---|---|
| Задача решена полностью. | + | 14 |
| Решение задачи, содержит верную общую схему решения, но в результате описки или арифметической ошибки получен неверный ответ. | ± | 10 |
| Решение содержит значительное продвижение в верном направлении. | ±2 | 7 |
| Решение в целом неверное или незаконченное, но содержит определенное содержательное продвижение в верном направлении. | ± | 3 |
| Задача не решена, содержательных продвижений нет. | − | 0 |
| Задача не решалась. | 0 | 0 |
В комнате стоят два ящика. В первом лежат n белых и m черных шаров, во втором — достаточно много черных. Из первого ящика наугад вынимают два шара. Если они одного цвета, то черный шар из второго ящика перекладывают в первый, если шары разного цвета, то белый шар возвращают в первый ящик. Так поступают до тех пор, пока в первом ящике не останется один шар. С какой вероятностью он будет белым?
Четность числа шаров белого цвета в первом ящике не меняется, следовательно, последний шар будет белым тогда и только тогда, когда n нечетно.
Ответ: если n нечетно, то 1, а если n четно, то 0.
| Критерии | Оценка | Баллы |
|---|---|---|
| Задача решена полностью. | + | 14 |
| Решение задачи, содержит верную общую схему решения, но в результате описки или арифметической ошибки получен неверный ответ. | ± | 10 |
| Решение содержит значительное продвижение в верном направлении. | ±2 | 7 |
| Решение в целом неверное или незаконченное, но содержит определенное содержательное продвижение в верном направлении. | ± | 3 |
| Задача не решена, содержательных продвижений нет. | − | 0 |
| Задача не решалась. | 0 | 0 |
Клетки шахматной доски 
раскрашены в 72 цвета так, что в каждый цвет покрашены ровно две клетки. Докажите, что на этой доске можно расставить 12 ладей так, чтобы они стояли на клетках разного цвета и никакие две из них не били друг друга. Две ладьи бьют друг друга, если они стоят в одной горизонтали или в одной вертикали доски.
На доске 
можно расставить m небьющих друг друга ладей 
на последней — единственным способом). Пусть доказываемое утверждение неверно. Тогда, если доска раскрашена так, как в условии, то для всякой расстановки не бьющих друг друга ладей какие-то две стоят на клетках одного цвета. Следовательно, число 
(где 
) таких расстановок не больше, чем 
так как пару ладей можно расставить на клетках одного цвета не более, чем 
способами, а остальные 
ладьи — 
способами. Итак, 
откуда 
то есть 
что противоречит условию.
| Критерии | Оценка | Баллы |
|---|---|---|
| Задача решена полностью. | + | 16 |
| Решение задачи, содержит верную общую схему решения, но в результате описки или арифметической ошибки получен неверный ответ. | ± | 12 |
| Решение содержит значительное продвижение в верном направлении. | ±2 | 8 |
| Решение в целом неверное или незаконченное, но содержит определенное содержательное продвижение в верном направлении. | ± | 4 |
| Задача не решена, содержательных продвижений нет. | − | 0 |
| Задача не решалась. | 0 | 0 |
Пусть xk — положительный корень уравнения Докажите, что
Так как то следовательно, и т. е. Поэтому
то есть
Значит,
| Критерии | Оценка | Баллы |
|---|---|---|
| Задача решена полностью. | + | 14 |
| Решение задачи, содержит верную общую схему решения, но в результате описки или арифметической ошибки получен неверный ответ. | ± | 10 |
| Решение содержит значительное продвижение в верном направлении. | + / 2 | 7 |
| Решение в целом неверное или незаконченное, но содержит определенное содержательное продвижение в верном направлении. | ∓ | 3 |
| Задача не решена, содержательных продвижений нет. | − | 0 |
| Задача не решалась. | 0 | 0 |
Клетки шахматной доски 
раскрашены в 50 цветов так, что в каждый цвет покрашены ровно две клетки. Докажите, что на этой доске можно расставить 10 ладей так, чтобы они стояли на клетках разного цвета и никакие две из них не били друг друга. Две ладьи бьют друг друга, если они стоят в одной горизонтали или в одной вертикали доски.
На доске можно расставить m небьющих друг друга ладей на последней — единственным способом). Пусть доказываемое утверждение неверно. Тогда, если доска раскрашена так, как в условии, то для всякой расстановки не бьющих друг друга ладей какие-то две стоят на клетках одного цвета. Следовательно, число (где 
) таких расстановок не больше, чем так как пару ладей можно расставить на клетках одного цвета не более, чем способами, а остальные ладьи — способами.
Итак, откуда т. е. что противоречит условию.
| Критерии | Оценка | Баллы |
|---|---|---|
| Задача решена полностью. | + | 16 |
| Решение задачи, содержит верную общую схему решения, но в результате описки или арифметической ошибки получен неверный ответ. | ± | 12 |
| Решение содержит значительное продвижение в верном направлении. | ±2 | 8 |
| Решение в целом неверное или незаконченное, но содержит определенное содержательное продвижение в верном направлении. | ± | 4 |
| Задача не решена, содержательных продвижений нет. | − | 0 |
| Задача не решалась. | 0 | 0 |
В фирме работало 150 сотрудников, в том числе 73 женщины. Затем произошло объединение с другой фирмой, где женщины составляли 40%. В результате доля женщин среди сотрудников стала равна p%. Найдите все возможные целые значения p.
В фирме, с которой произошло объединение, отношение числа женщин к числу мужчин равнялось 
Поэтому можно полагать, что там было 2n женщин и 3n мужчин, где 
сотрудников которой, ровно 
женщин. Поскольку
то число 
делит 260 и может быть равным 260, 130, 65 или 52. Соответствующие значения p равны 41, 42, 44 и 45.
Ответ: 41, 42, 44, 45.
| Критерии | Оценка | Баллы |
|---|---|---|
| Задача решена полностью. | + | 10 |
| Задача решалась по верному плану, но перебор проведён не до конца: не доказано, что других значений p нет. | ± | 7 |
| Составлены верные соотношения, связывающие p и n, но дальше продвижений нет. | +/2 | 3 |
| Решение в целом не верное, но содержит все или часть искомых значений p (и не содержит других). | ± | 2, если все; 1, если не все |
Наверх