Всего: 71 1–20 | 21–40 | 41–60 | 61–71
Добавить в вариант
В последовательности из букв a и b в любом наборе подряд идущих символов длины больше 3 количество букв a не меньше, чем количество букв b.
Докажите, что это условие эквивалентно тому, что в любом наборе из 5 или 7 подряд идущих символов количество букв a больше, чем количество букв b.
Замечение: эта формулировка содержит неточность. Указанная эквивалентность имеет место для последовательностей хотя бы из 5 символов.
Постройте граф, удовлетворяющий следующим условиям:
1) Из каждой вершины выходит ровно 4 ребра
2) В графе нет четырёх вершин, каждые две из которых были бы соединены между собой
3) Граф нельзя покрасить в три цвета "правильно", то есть так, чтобы любые две вершины одного цвета были не соединены.
Напишите логическую формулу, описывающую свойство, которым обладает комбинация фишек на левой картинке, но не обладает комбинация на правой.
В формуле используются следующие обозначения:
Фишки обозначаются переменными x, y, z. Простые свойства описываются такими выражениями как «x синяя», «y красная», «x сосед y» (последнее означает, что фишки стоят на различных клетках, у которых есть общая сторона или угол). Для записи более сложных свойств используются логические связки, которые соединяют простые свойства: И, ИЛИ, НЕ ВЕРНО ЧТО, СЛЕДОВАТЕЛЬНО, ТОГДА И ТОЛЬКО ТОГДА, ДЛЯ ВСЕХ x, СУЩЕСТВУЕТ x ТАКОЙ, ЧТО (вместо x можно использовать y или z). Для упорядочения связок используются круглые скобки.
Логический элемент ЭКВИ-3 работает так: на вход подаются нули или единицы; на выходе оказывается единица тогда и только тогда, когда значения входов совпадают.
С помощью логического элемента ЭКВИ-3 постройте логическую схему с четырьмя входами и одним выходом, реализующую элемент ЭКВИ-4: на выходе оказывается единица тогда и только тогда, когда значения всех четырёх входов совпадают.
Логический элемент ЭКВИ-3 работает так: на вход подаются нули или единицы; на выходе оказывается единица тогда и только тогда, когда значения входов совпадают.
а) Докажите, что при помощи элемента ЭКВИ-3 можно построить схему с одним выходом и любым количеством входов, выдающую аналогичный результат: на выходе оказывается единица тогда и только тогда, когда значения всех входов совпадают.
б) Докажите, что такую схему с n входами можно построить, использовав не более n элементов ЭКВИ-3.
предпоследний элемент имеет вид 
или 
в зависимости от чётности n. Последний элемент в любом случае будет иметь вид 
Их количество в любом случае равно целой части 
которую мы обозначим за 
Введём ещё одно обозначение: 
Это обозначение кажется странным на первый взгляд, но оно упростит нам вычисления. Итак, теперь 
—
элементов и нам надо убедиться, что они всегда истинны. Аналогичным образом построим для них ещё 
элемента получим 
новых. Будем продолжать так, пока на одном из шагов мы не получим 
элемент. Общее количество построенных элементов составит 
То есть, общее количество построенных элементов строго меньше 
то есть не больше 
Графом называется рисунок, состоящий из точек (вершин), соединённых отрезками (рёбрами). При этом нам не важно, как именно нарисован граф, важно только, какие вершины с какими соединены.
а) Учитель нарисовал на доске граф. Три ученика перерисовали его в тетрадки (возможно, не сохранив расположение вершин), при этом каждый из них потерял по одной вершине (каждый — свою) и все выходящие из неё рёбра.
Оказалось, что по рисункам ребят нельзя восстановить нарисованный учителем граф. Как такое могло быть? Постройте пример трёх рисунков учеников и двух возможных рисунков учителя.
б) Верно ли, что для любого n можно придумать набор из n таких рисунков, по которым исходный граф восстанавливается неоднозначно (то есть существует два и более варианта)?
копии левого и второй граф, состоящий, наоборот, из k копий левого графа и 
Графом называется рисунок, состоящий из точек (вершин), соединённых отрезками (рёбрами). При этом нам не важно, как именно нарисован граф, важно только, какие вершины как соединены.
Подграф, который получается из графа удалением одной вершины, назовём картой, а набор всех карт графа — колодой.
В задаче отборочного тура мы уже доказывали, что по колоде можно восстановить общее количество рёбер графа. Также легко доказать, что можно установить степени всех вершин (количество выходящих из неё рёбер): степень вершины, которой не хватает на карте — это в точности количество отсутствующих на ней рёбер.
Докажите, что граф, степени всех вершин которого чётны, однозначно восстанавливается по своей колоде.
Постройте машину Тьюринга, распознающую все слова в алфавите {a, b, c}, содержащие все три буквы алфавита.
Распознавание происходит следующим образом: если слово распознано, к нему справа дописывается буква a, в противном случае — буква b.