Ошибка.
Попробуйте повторить позже
Даны натуральные числа и такие, что Существует ли многочлен степени больше с коэффициентами из множества такой, что делится на
Легко видеть, что если то всякий многочлен с коэффициентами от 0 до является нулевым.
Пусть Представим в -ичной записи (иными словами, в системе счисления с основанием ): где Поскольку в этой записи
Покажем, что удовлетворяет условию. Действительно, по теореме Безу, для любого многочлена с целыми коэффициентами делится на Значит, делится на Но тогда и делится на
Существует при
Ошибка.
Попробуйте повторить позже
На стороне параллелограмма отмечены точки и , причём лежит между и Диагонали и пересекаются в точке Прямые и касаются окружности, описанной около треугольника Докажите, что они касаются и окружности, описанной около треугольника
Будем обозначать окружность, описанную около треугольника .
Из касания окружности и прямой имеем , а из параллельности имеем . Таким образом, , следовательно, четырехугольник вписанный. Аналогично вписанный.
Отсюда, с использованием параллельности , получаем: . Но из равенства следует касание окружности и прямой . Аналогично доказываем касание окружности и прямой .
Ошибка.
Попробуйте повторить позже
В стране городов. Некоторые пары городов связаны двусторонними авиалиниями, каждая пара не более, чем одной. Каждая авиалиния принадлежит одной из компаний. Оказалось, что из любого города можно попасть в любой другой (возможно, с пересадками), но при закрытии всех авиалиний любой из компаний это свойство нарушается. Какое наибольшее количество авиалиний (при произвольных и ) могло быть в этой стране?
Первое решение. Рассмотрим граф, в котором вершины это города, ребра — авиалинии, причем ребра, соответствующие авиалиниям -ой компании, покрашены в -й цвет.
Пример. Пусть в графе вершины не смежны друг с другом, и из вершины ведут ребра цвета во все вершины с номерами, большими Все ребра между вершинами с номерами, большими присутствуют и покрашены произвольным образом. Очевидно, что при удалении ребер цвета из вершины нельзя добраться до остальных вершин графа, а изначальный граф связен.
Оценка. Докажем индукцией по что в графе отсутствует хотя бы ребер; из этого следует, что ибо иначе ребер бы не было, и графе был бы связным. База при очевидна.
Переход: Рассмотрим все компоненты связности -го цвета. Их хотя бы иначе можно, добавляя цвета, каждый раз уменьшать количество компонент хотя бы на (если при добавлении цвета количество компонент не уменьшилось, то при удалении из исходного графа ребер этого цвета граф остается связным). Тогда -й цвет уже сделает граф связным.
Стянем каждую компоненту -го цвета в вершину (то есть сопоставим каждой компоненте вершину нового графа, проведя ребра между вершинами тогда и только тогда, когда какие-то вершины соответствующих компонент были связаны ребром; если между двумя компонентами были ребра нескольких цветов, оставим один). Полученный граф удовлетворяет индукционному предположению, поэтому в нем отсутствует хотя бы peбер, соответствующих хотя бы тому же количеству в исходном графе.
С другой стороны, если выкинуть все ребра -го цвета, хотя бы одна из его компонент, пусть , должна разбиться на две. Это значит, что в любую другую компоненту нет ребер хотя бы от одной из частей Докажем, что тогда в графе отсутствуют ещё хотя бы рёбер, не учтённых ранее. Если от компоненты нет рёбер в обе части то это означает отсутствие хотя бы двух рёбер, а до этого мы учли только одно. Если от компоненты есть ребро к одной из частей то в графе из стянутых вершин-компонент соответствующие компоненты были соединены, но на самом деле одного ребра в исходном графе нет. Итак, за счёт каждой компоненты, отличной от мы должны учесть отсутствие ещё хотя бы одного ребра. Значит, ещё минимум ребро отсутствует, и всего отсутствующих ребер хотя бы что и требовалось.
Второе решение. Приведём другой способ доказать оценку; мы используем терминологию, введённую в начале первого решения.
Сначала докажем, что для каждой пары компаний найдутся две вершины любой путь между которыми содержит ребра обеих компаний и Пусть при удалении компании вершины распадаются на два непустых множества и между которыми нет ребер, а при удалении компании — на множества и Если множества и оба непустые, то можно взять и Иначе, множества и оба непустые, и можно взять и Ясно, что и подходят и что между ними нет ребра.
Для каждой пары компаний выберем и так, что расстояние между ними (то есть длина пути по ребрам исходного графа) минимально возможное. Если мы докажем, что разным парам компаний соответствуют разные пары то мы получим, что отсутствующих ребер не меньше, чем пар компаний, что и даст требуемую оценку.
Предположим, что пара соответствует двум разным парам компаний — и еще одной (без ограничения общности, либо либо ). Пусть — один из кратчайших путей между и Если ребро принадлежит не компаниям или то любой путь между и содержит ребра компаний и что противоречит минимальности расстояния для пары Аналогично, ребро принадлежит одной из компаний или Значит, пара не может соответствовать паре компаний Таким образом, пара соответствует паре компаний и ребра и оба принадлежат компании 1. Тогда любой путь между и любой путь между и и любой путь между и содержат ребра обеих компаний и Из минимальности расстояния для пары следует, что между и между и а также между и существуют пути, не содержащие ребер компании Соединяя эти пути, получаем путь (возможно, с повторяющимися вершинами) от до не содержащий ребер компании Противоречие.
Конструкция возможна только при и тогда наибольшее количество ребер равно
Ошибка.
Попробуйте повторить позже
В межгалактической гостинице есть комнат вместимостью человек. В этих комнатах суммарно живёт человек. В гостиницу приехал VIP-гость, для которого нужно освободить целую комнату. Для этого директор гостиницы выбирает одну комнату и переселяет всех её жителей в одну и ту же другую комнату. При каком наибольшем директор гостиницы всегда может таким образом освободить комнату независимо от текущего расселения?
Источники:
Предположим, что при 8824 постояльцах директор не может осуществить переселение. Разобъём комнаты на пары по вместимости: . Отметим, что для каждой пары комнат суммарное количество человек, живущих в двух комнатах, больше, чем вместимость большей комнаты из пары, иначе всех человек из этой пары можно было бы собрать в комнате с большей вместимостью. Таким образом, общее количество человек не меншше . Поэтому при 8824 постояльцах директор может освободить комнату.
Теперь приведём пример, доказывающий, что при 8825 и более постояльцах существует расселение, в котором освободить комнату указанньм образом не удастся.
Упорядочим комнаты по возрастанию вместимости. Пусть в первых пятидесяти комнатах живёт по 76, а в комнате вместимости при живёт человек. Посчитаем количество человек, живущих в гостинице:
Рассмотрим две произвольные комнаты вместимости . Заметим, что в комнате вместимости живёт не меньше человек, а в комнате - не меньше 76 человек. Таким образом, переселить людей из одной комнаты в другую ни для какой пары комнат не удастся, поэтому пример подходит. Если , то достаточно селить оставшихся людей поочерёдно в любые комнаты, где ещё остаются свободные места.
Ошибка.
Попробуйте повторить позже
Даны непостоянный многочлен с целыми коэффициентами и натуральное число Положим при всех натуральных Оказалось, что для любого натурального в последовательности есть число, являющееся -й степенью натурального числа, большего Докажите, что многочлен — линейный.
Заметим сразу, что при каждом натуральном в последовательности встретится бесконечно много -х степеней натуральных чисел, больших единицы. Действительно, если их количество конечно, и наибольшая из них—это то в последовательности не встретится ни одной -й степени, что невозможно.
Положим тогда Поскольку все коэффициенты многочлена целые, из следует Отсюда непосредственной индукцией по получаем, что то есть при всех
Лемма. делится на
Доказательство. Пусть —максимальная степень простого числа делящая достаточно показать, что делится на Положим согласно замечанию выше, найдётся такой индекс что при натуральном при этом
Если не делится на то по теореме Эйлера откуда Если же делится на то делится на а значит, и тоже. В любом случае делится на что и требовалось.
Согласно лемме, для любого число делится на при этом по условию среди целых чисел бесконечно много различных. В частности,
при бесконечном количестве целых значений (где ).
Предположим теперь, что степень многочлена (и, как следствие, многочлена ) больше Тогда неравенство выше может выполняться для бесконечно многих целых лишь тогда, когда —квадратный трёхчлен со старшим коэффициентом то есть В этом последнем случае значения многочлена делятся на для бесконечного количества целых это может быть лишь если то есть или
В первом случае то есть не может быть нечётной степенью натурального числа, если не является таковой степенью. Во втором случае при всех то есть не может быть степенью натурального числа, большего В обоих случаях условие задачи не выполнено; значит, линеен.
Ошибка.
Попробуйте повторить позже
Паша и Вова играют в следующую игру, делая ходы по очереди. Начинает Паша. Изначально перед мальчиками лежит большой кусок пластилина. За один ход Паша может разрезать любой из имеющихся кусков пластилина на три части (не обязательно равные). Вова своим ходом выбирает два куска и слепляет их вместе. Паша побеждает, если в некоторый момент среди имеющихся кусков пластилина окажется кусков одинаковой массы. Может ли Вова помешать Паше победить?
Источники:
Приведём алгоритм, позволяющий Паше победить. Пусть масса исходного куска равна кг. Паша каждым ходом будет отрезать от самого большого из имеющихся кусков два куска массой по г. Докажем, что не позже, чем через ходов Паша победит.
Предположим, что это не так. Рассмотрим последовательных ходов Паши. Всего за эти появляется кусков массой г. Если бы каждым своим ответным ходом Вова слеплял два куска массой г, то в итоге получилось бы кусков массой г, и Паша бы победил. Значит, по крайней мере один раз Вова не слепит между собой два куска массой г. Поэтому спустя ходов Паши и ходов Вовы количество кусков массой г увеличится хотя бы на
Разобьём ходов Паши на сотни последовательных. По доказанному вше, после каждой сотни последовательных ходов Паши и ответных ходов Вовы количество кусков массой г увеличится хотя бы на Поэтому Паша так или иначе победит.
Нет, не может
Ошибка.
Попробуйте повторить позже
Дан остроугольный треугольник в котором Пусть и — середины сторон и соответственно, а — основание высоты, проведенной из На отрезке нашлась точка такая, что Луч пересекает окружность описанную около треугольника в точке Докажите, что точки и лежат на одной окружности.
Рассмотрим серединный перпендикуляр к отрезку Ясно, что на нём лежит точка Отразим относительно него точку получим точку которая также лежит на Заметим, что и равнобедренные (первый из-за того, что — серединный перпендикуляр к а второй в силу симметрии). Следовательно, точка равноудалена от точек и Но для прямоугольного (потому что ) существует лишь одна точка с таким свойством, а именно середина его гипотенузы Таким образом, и коллинеарны. Отсюда Отсюда и следует нужная вписанность.
Ошибка.
Попробуйте повторить позже
Даны натуральные числа и Докажите, что существует бесконечно много натуральных таких, что число не делится на
Назовём натуральное плохим, если не делится на Наша цель — доказать, что плохих чисел бесконечно много.
Первое решение. Докажем, что при любом чётном одно из чисел и плохое; из этого, очевидно, следует требуемое. Предположим противное. Тогда и Иначе говоря, и Но отсюда следует, что это невозможно, ибо Противоречие.
Второе решение. При утверждение задачи очевидно, поэтому будем считать, что
Лемма. Пусть и — натуральные числа. Предположим, что делится на Тогда делится на
Доказательство. Пусть — остаток от деления на Тогда
то есть одно из чисел делится на Но это невозможно при ибо
Докажем, что существует бесконечно много плохих чисел вида Действительно, если делится на то по лемме должно делиться на Это невозможно, если, например, — простое число, большее Осталось заметить, что таких простых чисел бесконечно много.
Третье решение. Мы опять же исследуем лишь случай
Пусть — некоторый простой делитель числа Положим тогда при любом имеем то есть делится на
С другой стороны, покажем, что числа и не могут одновременно делиться на Действительно, иначе на делилась бы и их разность но это невозможно, ибо по малой теореме Ферма, а числа и взаимно просты с
Итак, либо не делится на (и, значит, на ), либо не делится на (и, значит, на ). Поэтому среди чисел бесконечно много плохих.
Ошибка.
Попробуйте повторить позже
Найдите количество корней уравнения
Подсказка 1
Самое лучшее, что можно делать в задачах такого вида (когда явных корней не видно или их просто долго искать) это анализировать уравнение по интервалам. Для начала давайте разложим на множители квадратный трёхчлен и поймём, какие знаки он принимает на промежутках. Что тогда можно сказать сразу, учитывая, что левая часть у нас всегда положительна?
Подсказка 2
Верно, на интервале от -2019 до 1 квадратный трёхчлен отрицательный, а правая часть всегда положительна. Значит, корней тут нет. Давайте теперь проанализируем интервалы, где правая часть положительна. Что можно сказать про эти два интервала? Попробуйте понять, как на этих промежутках раскрываются модули.
Подсказка 3
Ага, от 1 до бесконечности они все раскроются положительно, откуда найти, сколько находится корней на этом промежутке, не составляет труда. Второй промежуток можно рассмотреть аналогично или же понять, что функции слева и справа симметричны относительно одной оси. Тогда на втором промежутке столько же корней, сколько на первом.
При корней нет, так как на указанном интервале левая часть неотрицательна, а правая — отрицательна.
При все модули раскрываются со знаком “”, поэтому уравнение примет вид , где Поскольку , это квадратное уравнение имеет единственный корень на промежутке .
Поскольку графики функций в левой и правой части симметричны относительно прямой (т.е. ), то на промежутке столько же корней, сколько и на промежутке , т.е. ровно один корень. Итого, у данного уравнения два корня.
Ошибка.
Попробуйте повторить позже
Изначально на столе лежат три кучки из 100,101 и 102 камней соответственно. Илья и Костя играют в следующую игру. За один ход каждый из них может взять себе один камень из любой кучи, кроме той, из которой он брал камень на своем предыдущем ходе (на своём первом ходе каждый игрок может брать камень из любой кучки). Ходы игроки делают по очереди, начинает Илья. Проигрывает тот, кто не может сделать ход. Кто из игроков может выиграть, как бы ни играл соперник?
Источники:
Пусть Илья возьмет камень из кучки 101. Тогда если Костя возьмет камень из другой кучи, то Илья сможет просто брать камень с той же кучи, что и Костя. Почему? Если у Кости был ход (рассматриваем уже хотя бы второй Костин ход, так как с первыми ходами все работает), значит, на своем предыдущем ходе Костя брал камень из другой кучи, но Илья брал камень из той же кучи, поэтому сейчас он тоже может взять камень, откуда его взял Костя. Таким образом, в этом случае после хода Ильи во всех трех кучках камней четно, а значит, Костя проиграет.
Если же Костя своим первым ходом взял камень тоже из второй кучи, то Илья уже не может повторить за ним ход, так как он только что взял из этой кучи камень. Пусть тогда Илья делает вот что: если Костя берет камень из второй кучи, то он берет из первой, если Костя берет из первой кучи, то он берет из второй, если Костя берет из третей кучи, то он берет тоже из третьей кучи.
Почему у Ильи всегда есть ход? Если Костя берет камень из третьей кучи, то на предыдущем ходу он брал камень из первой или второй кучи, а значит, и Илья тоже, поэтому, Илья может взять камень из третьей кучи (еще важно, что в третьей куче после хода Кости камней всегда нечетно, поэтому они там не могли закончиться после его хода). Если же Костя берет камень из первой кучи, то Илье нужно взять камень из второй, но если бы он не мог, то это бы означало, что первый своим предыдущим ходом брал камень из первой кучи, противоречие, значит, Илья может взять камень из второй кучи, причем, после его хода камней в первой и второй куче равное количество, а значит, камни во второй кучи есть. Аналогично, если Костя взял камень из второй кучи.
Таким образом, выигрывает Илья.
Ошибка.
Попробуйте повторить позже
В остроугольном неравнобедренном треугольнике проведены медиана и высота На прямых и отмечены точки и соответственно так, что и Описанная окружность треугольника пересекает прямую вторично в точке Докажите, что
Пусть описанная окружность треугольника является единичной с центром в нуле. Поскольку имеем откуда С другой стороны Решая систему на и находим Аналогичное выражение получается для
Отметим на прямой точку так, что тогда откуда Вспомнив, что находим
Нам достаточно показать, что лежат на одной окружности. Для этого нужно посчитать двойное отношение. Сделаем необходимые вычисления
Аналогично Наконец, можно посчитать двойное отношение
Последнее выражение действительно вещественное, что сразу следует из подстановки
Ошибка.
Попробуйте повторить позже
K натуральному числу прибавили наибольший его делитель, меньший и получили степень десятки. Найдите все такие
Пусть — наибольший делитель числа меньший, чем Тогда где — наименьший простой делитель числа Имеем Число в правой части не делится на поэтому Отсюда следует, что нечётно, а тогда и нечётно. Поскольку делится на
Если то что невозможно, так как делится на то есть не является простым. Значит, число кратно и потому
Если то откуда и
Если же то и число делится на что невозможно.
Ошибка.
Попробуйте повторить позже
Каждые два из действительных чисел отличаются не менее чем на Оказалось, что для некоторого действительного выполнены равенства и Докажите, что
Без ограничения общности можно считать, что По условию, при всех Значит, при всех Возведём каждое из полученных неравенств в квадрат и сложим их все. Получим то есть
С другой стороны, по условию имеем
Складывая и получаем
откуда или
Ошибка.
Попробуйте повторить позже
В треугольнике проведена биссектриса (точка лежит на отрезке ). Прямая пересекает окружность описанную около треугольника в точках и Окружность построенная на отрезке как на диаметре, пересекает окружность в точках и Докажите, что прямая, симметричная прямой относительно прямой содержит медиану треугольника
Подсказка 1
Так, нужно подумать… То есть у нас есть биссектриса и середина стороны в задаче, а также есть описанная окружность. На какой факт нам это намекает?
Подсказка 2
Верно, на тот факт, что биссектриса и серпер пересекаются на описанной окружности треугольника. Тогда пусть они пересеклись в точке Е. Что интересного можно заметить если продлить отрезок EM до пересечения с описанной окружностью(пусть точка пересечения - точка Х)?
Подсказка 3
Конечно, можно заметить, что F,D,X - лежат на 1 прямой. Почему это так? Ну понятно почему, XFE - прямой, так как опирается на диаметр окружности (ABC), и DFE - прямой, так как опирается на диаметр окружности, построенной на DE как на диаметре. Хмм… А что теперь нам это дает? Какие равные углы теперь можно отметить?
Подсказка 4
Действительно, мы можем заметить равенство углов FBE и FXE, в силу того, что они опираются на одну хорду FE. Значит, нам надо доказать, что углы FXE и MBE равны! А как это можно удобно переформулировать?
Подсказка 5
Это можно переформулировать как доказательство вписанности BDMX. Осталось понять почему сумма углов EBX и XMA равна 180 градусов, и задача будет решена!
Первое решение. Пусть — медиана треугольника. Так как биссектриса и серединный перпендикуляр к проходят через одну и ту же точку (середину дуги ), то Пусть пересекается с окружностью в точке Из сказанного выше, — диаметр окружности
Надо доказать, что и симметричны относительно биссектрисы, то есть
При этом как опирающиеся на одну дугу вписанные углы.
По условию прямой, а ещё опирающийся на диаметр вписанный угол тоже прямой. Поэтому точки коллинеарны. Тогда Остаётся доказать равенство
Это равенство следует из того, четырёхугольник можно вписать в окружность. Действительно, при этом
Второе решение.
Сделаем симметрию относительно биссектрисы угла и инверсию с таким радиусом, чтобы и где звездочкой обозначаем образ точки под действием композиции преобразований. Заметим что и так как прямая переходит в дугу и наоборот, а прямая переходит сама в себя. Окружность, построенная на тем самым переходит в окружность, центр которой все лежит на а точки ее пересечения с это и То есть, эта окружность переходит в себя. Точка переходит в точку вторую точку пересечения окружности и прямой Известно, что – середина дуги а так как – диаметр окружности. Получаем, что высота в равнобедренном треугольника значит – середина Получается, что содержит медиану треугольника причем симметрична относительно биссектрисы угла Это именно то, что требовалось доказать по условию задачи.
Ошибка.
Попробуйте повторить позже
Грани куба разбиты на единичные клетки. Куб оклеен без наложений бумажными полосками (стороны полосок идут по сторонам клеток). Докажите, что число согнутых полосок нечетно.
Покрасим клетки каждой грани куба в шахматном порядке так, чтобы угловые клетки были чёрными. При этом каждая грань содержит чёрную и белых клеток. Заметим, что все согнутые полоски будут одноцветными, а все остальные — нет. Так как количество чёрных клеток на больше чем количество белых, то число чёрных согнутых полосок на больше чем число белых. Следовательно, эти числа разной чётности, и их сумма нечётна.
Ошибка.
Попробуйте повторить позже
На дугах и окружности, описанной около треугольника , выбраны соответственно точки и так, что прямые и параллельны. Докажите, что центры вписанных окружностей треугольников и равноудалены от середины дуги .
Источники:
Подсказка 1
Заметим, что наша большая окружность является центром описанной окружности для треугольников AKB и CEB, так что мы можем провести биссектрисы углов с вершиной B указанных треугольников. Как использовать параллельность?
Подсказка 2
Применив лемму о трезубце для указанных треугольников, а также осознав, что параллельные прямые отсекают равные дуги, можно найти равные отрезки на рисунке, которые связывают два центра вписанных окружностей. Теперь хочется как-то к середине дуги ABC, помним, что благодаря ей появляются равные дуги. Равенство каких треугольников полезно доказать?
Подсказка 3
Попробуем доказать равенство треугольников, в которых вершинам являются середина дуги ABC , центры вписанных окружностей и точки пересечений окружности (ABC) с биссектрисами, указанными в подсказке 1. В этом нам поможет подсчёт дуг, помним про середины, возникающие при построении!
Если , то утверждение очевидно.
Пусть для определенности
Обозначим через центры вписанных окружностей треугольников и соответственно, через - вторые точки пересечения прямых с описанной окружностью треугольника , а через - середину дуги этой окружности. Тогда как хорды, стягивающие половины равных дуг.
По лемме о трезубце и
Следовательно, .
Далее, как хорды, стягивающие равные дуги, а как углы, опирающиеся на одну дугу. Значит, треугольники и равны по двум сторонам и углу между ними, так что .
Ошибка.
Попробуйте повторить позже
Найдите наименьшее натуральное число, не представимое в виде где – натуральные числа.
Предположим, что Не уменьшая общности, положим Обозначим Получаем Так как в левой части целое нечётное число, то Понятно, что Заметим, что не подходит. Если же то и дают остаток при делении на Значит, левая и правая части дают соответственно остатки и при делении на Противоречие.
Ошибка.
Попробуйте повторить позже
Многочлен имеет три различных действительных корня, а многочлен где действительных корней не имеет. Докажите, что
По условию следовательно,
где
Пусть — дискриминанта квадратного трехчлена при Тогда Перемножив полученные неравенства получаем
Ошибка.
Попробуйте повторить позже
Существуют ли квадратные трёхчлены и с целыми коэффициентами, каждый из которых имеет по два целых корня?
Подсказка 1
Для начала давайте подумаем, что у нас есть в наличии. Во-первых, у нас есть факт, что все корни целые, во вторых, что все переменные a, b, c - целые. На какую тогда теорему нас могут натолкнуть эти два факта?
Подсказка 2
Верно, на теорему Виета! Ведь, так как корни целые, то и все коэффициенты приведенных квадратных трехчленов(то есть, когда мы поделим на главный коэффициент) должны быть целыми. А что это нам может дать?
Подсказка 3
А это дает, что числитель делится на знаменатель. Однако в этот момент надо остановиться и не выписывать все делимости, а подумать, можем ли мы обойтись каким-то более маленьким фактом, который следует из делимости? А если рассмотреть несколько случаев вида а - четный/нечетный? Как от четности а зависят четности других переменных? Подумайте над этим, и задача решится сама!
Если каждый трёхчлен имеет целые корни, то каждое из выражений , , и должно быть целым, так как каждое из них выражается через соответствующие целые корни по теореме Виета.
Пусть — нечётное, тогда чётно, равно как и и . Следовательно, и нечётные. В этом случае видно, что если чётный, то нечётно, а значит, не может равняться . Если же нечётный, то также нечётно, пришли к противоречию.
Если — чётное, то мы придём к такому же противоречию, только со вторым трёхчленом.
Ошибка.
Попробуйте повторить позже
Последовательность натуральных чисел такова, что
для всех Докажите, что для всех
Так как каждое делится на НОД НОД , то для всех Предположим, что при некотором Тогда, с одной стороны, НОД НОД (так как делится на ), а с другой стороны, поскольку делится на то НОД Противоречие.