Всего: 22 1–20 | 21–22
Добавить в вариант
При проектировании некоторого технического устройства возникла необходимость решать уравнения
где операция над двумя числами определена условием
Найдите все числовые множества X такие, что для любых a, b из X указанное уравнение имеет единственный корень x и этот корень принадлежит множеству X.
где 
так как 
Дана пара взаимно-простых многочленов с действительными коэффициентами P(x) и Q(x) степеней 2021 и 2000 соответственно (взаимно-простые означает, что не существует многочлена R(x), не равного константе, на который делятся P(x) и Q(x)). Гриша выбирает конечное множество действительных чисел c1, ..., cn (помните, в множестве элементы не повторяются, размер множества Гриша тоже выбирает сам), находит число различных кратных действительных корней у многочлена P(x) + ciQ(x) (при i от 1 до n) и складывает полученные числа. Какую наибольшую сумму Гриша может получить в результате этого процесса?
обращается в ноль, причем каждое такое α может быть посчитано максимум для одно ci.
Пусть α — кратный корень 
имеем левую из систем:
что и 
то невозможно поскольку многочлены взаимно-просты. Если же 
то деление на него является равносильным переходом, а с однозначно находится из (*). Второй переход — просто поделили на Q(x). 
и Q(x) соответственно. Тогда коэффициент 
при 
есть 
непрерывна (все корни знаменателя правее), равна нулю в концах отрезка и не равна нулю в остальных точках, значит, в какой-то точке производная принимает нулевое значение по теореме Ролля — нашли 2020 нулей производной. Теперь посмотрим на интервалы между соседними корнями Q(x), и также на открытый луч от самого правого из них до плюс бесконечности. На каждом интервале функция непрерывна, не меняет знак (поскольку не принимает нулевого значения — все корни числителя лежат левее), в концах интервалов f(x) стремиться к бесконечности (поскольку это корни числителя), при 
аналогично f(x) стремится к бесконечности, поскольку степень числителя больше степени знаменателя. Значит, на каждом из промежутков модуль достигает минимума во внутренней точке, там производная обращается в ноль (альтернативно можно воспользоваться теоремой Ролля для функции 
—
не может быть посчитан при разных значениях ci: –2 балла к итоговой сумме. Если это хотя бы упомянуто (очевидно что...) — нет претензий.
не может быть тождественно нулем: −4 балла к итоговой сумме.
и 
где операция «·» — операция умножения. Найдите корень x уравнения: 
или 
Для любой пары чисел определена некоторая операция «*», удовлетворяющая следующим свойствам: a ∗ (b ∗ c) = (a ∗ b) · c и a ∗ a = 1, где операция «·» — операция умножения. Найдите корень x уравнения: x ∗ 2 = 2021.
или 
Фишки называются соседними, если они стоят на различных клетках, у которых есть общая сторона или угол. Это отношение между ними будем обозначать словом «рядом».
Запишите при помощи данных предикатов, кванторов и логических связок формулу исчисления предикатов, которая будет верна для левой картинки и не верна для правой.
Вы можете использовать как неформальную, словесную, так и более математически продвинутую, формальную запись, использующую математические символы: кванторы и знаки операций.
В качестве начального решения введена формула, которая не верна для обоих картинок.
Постройте автомат для голосования трёх человек, используя логические элементы И и ИЛИ.
где m натуральное число. Проще всего построить такую схему из тех же соображений, из которых был построен пример №1 в предыдущей задаче: переберём все возможные наборы по m входов, объединив каждый из наборов при помощи элементов И. Затем соединим полученные части схемы при помощи элементов ИЛИ.Докажите, что из элементов И и ИЛИ можно построить автомат для голосования любого нечётного числа человек.
логическую схему, дающую на выходе истинное значение тогда и только тогда, когда хотя бы k входов принимают истинные значения; тогда эта схема может быть построена с использованием не более чем 
элементов И и ИЛИ. Докажем это утверждение по индукции. В качестве базы возьмём 
Тогда 
ИЛИ 
Требуется 1 элемент, что не превосходит 
Индукционный переход от n к 
при 
достаточно использовать n элементов ИЛИ, что меньше требуемой оценки. При 
заметим, что 
элементов, что и требовалось доказать.Докажите, что 2n элементов И и ИЛИ достаточно, чтобы построить автомат для голосования n человек (n — нечётное).
Имеется логический элемент с тремя входами, который даёт на выходе 1, если число единиц на входе больше числа нулей (реализует функцию голосования для трёх человек).
Постройте автомат для голосования пяти человек, используя только элементы голосования для трёх человек.
Имеется логический элемент с тремя входами, который даёт на выходе 1, если число единиц на входе больше числа нулей (реализует функцию голосования для трёх человек).
Докажите, что можно построить автомат для голосования любого нечётного числа человек, используя только элементы голосования для трёх человек.
содержится в условии.
к 
воспользуемся индукционным предположением. Рассмотрим следующие элементы для голосования 
человека и в это большинство входят одновременно люди с Из элементов AND (И), OR (ИЛИ) и XOR (ИСКЛЮЧАЮЩЕЕ ИЛИ) требуется построить логическую схему для сложения двоичных чисел. На вход подаются два трёхзначных двоичных числа. Первые три входа соответствуют первому слагаемому: верхний вход — первая цифра, нижний из трёх — последняя. Аналогично три нижних входа соответствуют второму слагаемому.
Выходы должны образовывать их сумму в двоичной системе счисления: верхний выход — первая цифра, нижний выход — последняя.
Например, когда мы получаем на вход 011 101, это значит, что мы складываем 011 и 101.
Получается 1000. Значит, верхний выход должен быть единицей, а остальные нулями.
Напишите логическую формулу, описывающую свойство, которым обладает комбинация фишек на левой картинке, но не обладает комбинация на правой. Постарайтесь, чтобы описание было как можно короче.
В формуле используются следующие обозначения:
Фишки обозначаются переменными x, y, z. Простые свойства описываются такими выражениями как «x синий», «y красный», «z желтый», «x сосед y» (последнее означает, что фишки стоят на различных клетках, у которых есть общая сторона или угол). Для записи более сложных свойств используются логические связки, которые соединяют простые свойства:
И, ИЛИ, НЕ ВЕРНО ЧТО, СЛЕДОВАТЕЛЬНО, ТОГДА И ТОЛЬКО ТОГДА, ДЛЯ ВСЕХ x, СУЩЕСТВУЕТ x ТАКОЙ, ЧТО (вместо x можно использовать y или z).
Для упорядочения связок используются круглые скобки. В качестве начального решения введена формула, которая не верна для обоих картинок.
На некоторых клетках квадратной клетчатой доски стоят рыцари, которые говорят только правду, а на некоторых — лжецы, которые всегда лгут. Некоторые клетки могут быть свободны; на каждой клетке стоит не более одного человека. Рыцари обозначены светлыми (голубыми) кружками, лжецы — тёмными (красными).
Составьте логическое выражение, которое истинно тогда и только тогда, когда каждый из стоящих на доске человек может произнести фразу «Все мои соседи лжецы».
На левой картинке изображён пример, удовлетворяющий условию задачи, на левой — не удовлетворяющий.
Рыцари, которые говорят только правду, и лжецы, которые всегда лгут, выстроились в ряд. (В ряду хотя бы один человек).Каждый из них произнёс фразу «Все мои соседи лжецы». Обозначим рыцаря буквой Р, а лжеца — буквой Л. Тогда каждой последовательности рыцарей и лжецов, для которой выполняется условие задачи, соответствует некоторое слово.
Опишите это слово, используя формулу, которая называется регулярным выражением. Такое выражение строится с помощью описываемых ниже операций «итерация», «умножение», «сложение».
Так для повторения блока из нескольких букв используйте операцию «звездочка» (итерация), например, (abb)* задает множество слов {пустое слово, abb, abbabb, abbabbabb, …}. Умножение множеств (эту операцию, как обычно в алгебре, изображают точкой приписыванием второго операнда вслед за первым, что мы и будем делать), описывает склейку всех слов первого множества со словами второго (третьего и т. д.), например a*cb* обозначает множество слов: {с, ac, cb, acb, aac,..., aaa...acb...b, ...}. Обратите внимание что слова, в которых нет букв a или b, получаются за счет того, что результат итерации может не содержать символов, то есть быть пустым словом.
Последней операцией, которая используется в формулах, является сложение. Сложение соответствует объединению множеств. Так, обозначение (a + b)*c + d(ac* + ) описывает множество всех последовательностей из букв a и b (обозначается (a + +b)*), к концу которых присоединена буква c, объединенного с множеством слов, начинающихся с буквы d, за которой следует буква a, а за ней любое число букв c и ещё одним однобуквенным словом (d умножить на пустое слово — это d).
Напишите логическую формулу, описывающую свойство, которым обладает комбинация фишек на левой картинке, но не обладает комбинация на правой.
В формуле используются следующие обозначения:
Фишки обозначаются переменными x, y, z. Простые свойства описываются такими выражениями как «x синяя», «y красная», «x сосед y» (последнее означает, что фишки стоят на различных клетках, у которых есть общая сторона или угол). Для записи более сложных свойств используются логические связки, которые соединяют простые свойства: И, ИЛИ, НЕ ВЕРНО ЧТО, СЛЕДОВАТЕЛЬНО, ТОГДА И ТОЛЬКО ТОГДА, ДЛЯ ВСЕХ x, СУЩЕСТВУЕТ x ТАКОЙ, ЧТО (вместо x можно использовать y или z). Для упорядочения связок используются круглые скобки.
Каждому из четырех абонентов A1, A2, A3, A4 надо выдать по два уравнения вида 
где 
Значения секретных битов w, x, y, z одинаковы для всех абонентов и им заранее неизвестны. Пусть, например, A1 получит уравнения
a A2 —
Здесь традиционно полагается, что 
Тогда, объединившись, из имеющихся в их распоряжении четырех уравнений они однозначно найдут, что 
При этом будем говорить, что пара абонентов {A1, A2} может достоверно вычислить секретные биты x, y, z. Приведите хотя бы один пример уравнений, которые надо выдать этим четырем абонентам, чтобы каждая пара {A1, A2}, {A1, A3}, {A1, A4} могла достоверно вычислить x, y, z, но чтобы при этом ни одна другая пара абонентов это сделать не смогла и ни один абонент в одиночку не смог бы найти даже один секретный бит.
выдать это уравнение Ai, а абоненту Aj — уравнение 
—
а A1 уравнение 
тогда сложив эти уравнения вместе, пара абонентов {A1, A2} найдет 
Выдадим абоненту A2 также уравнение 
тогда они найдут бит 
Очевидно, что при таком способе, если пара абонентов находит 2 бита, то она найдет и третий, так как он будет присутствовать хотя бы у одного абонента в линейной комбинации: 
A2, A3, A4: 
Каждому из четырех абонентов A1, A2, A3, A4 надо выдать по два уравнения вида 
где 
Значения секретных битов w, x, y, z одинаковы для всех абонентов и им заранее неизвестны. Приведите хотя бы один пример уравнений, которые надо выдать этим четырем абонентам, чтобы каждая пара {A1, A3}, {A1, A4}, {A2, A3} могла достоверно вычислить w, x, y, z, но чтобы при этом: 1) ни одна другая пара абонентов не могла бы достоверно вычислить более одного секретного бита; 2) ни один абонент в одиночку не был в состоянии достоверно вычислить даже один секретный бит. Например, если абонент A1 получит уравнения
a A2
Тогда, объединившись, из имеющихся в их распоряжении четырех уравнений они однозначно найдут, что 
При этом будем говорить, что пара абонентов {A1, A2} может достоверно вычислить секретные биты w, x, y, z. Здесь традиционно полагается, что
Затем в уравнениях можно будет сделать замену 
а это по условию недопустимо. Никакому абоненту нельзя выдать уравнения (2) и (5), так как из них следует, что 
Устройство принимает на вход и выдает на выход наборы из n битов (причем 
Поданный на вход набор 
преобразуется в выходной набор
где ⊕ — стандартная операция сложения битов:
Подав теперь этот набор h(x) на вход, получим на выходе набор 
который вновь подадим на вход и получим 
и т. д. Докажите, что если все наборы x, h(x), 
Поэтому претендентом на самое большое количество различных векторов является последовательность (1), начинающаяся с вектора, содержащего нечетное количество единиц и продолжающаяся всеми векторами с четным количеством единиц. Количество векторов в такой последовательности будет 
Таким образом,