Каталог по темам

Задачи

Страница: << 4 5 6 7 8 9 10 [Всего задач: 50]

Задача 109965

Темы:	[	Математическая логика (прочее)	]
	[	Теория алгоритмов (прочее)	]
	[	Примеры и контрпримеры. Конструкции	]
	[	Объединение, пересечение и разность множеств	]

Сложность: 5-
Классы: 8,9,10

Автор: Разборов А.

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

Прислать комментарий Решение

Задача 73685

Темы:	[	Задачи с ограничениями	]
	[	Целочисленные решетки	]
	[	Индукция (прочее)	]
	[	Объединение, пересечение и разность множеств	]

Сложность: 5
Классы: 10,11

Автор: Алексеев В.Б.

P и Q – подмножества множества выражений вида (a₁, a₂, ..., a_n), где a_i – натуральные числа, не превосходящие данного натурального числа k (таких выражений всего kⁿ). Для каждого элемента (p₁, ..., p_n) множества P и каждого элемента (q₁, ..., q_n) множества Q существует хотя бы один такой номер m, что p_m = q_m. Докажите, что хотя бы одно из множеств P и Q состоит не более чем из k^n–1 элементов для
а) k = 2 и любого натурального n;
б) n = 2 и любого натурального k > 1;
в) произвольного натурального n и произвольного натурального k > 1.

Прислать комментарий

Решение

Задача 116695

Темы:	[	Теория графов (прочее)	]
	[	Сочетания и размещения	]
	[	Принцип Дирихле	]
	[	Объединение, пересечение и разность множеств	]
	[	Примеры и контрпримеры. Конструкции	]
	[	Оценка + пример	]

Сложность: 5+
Классы: 10

Автор: Райгородский А. М.

Рассмотрим граф, у которого вершины соответствуют всевозможным трёхэлементным подмножествам множества {1, 2, 3, ..., 2^k}, а рёбра проводятся между вершинами, которые соответствуют подмножествам, пересекающимся ровно по одному элементу. Найдите минимальное количество цветов, в которые можно раскрасить вершины графа так, чтобы любые две вершины, соединённые ребром, были разного цвета.

Прислать комментарий

Решение

Задача 78718

Темы:	[	Числовые таблицы и их свойства	]
	[	Задачи с ограничениями	]
	[	Разбиения на пары и группы; биекции	]
	[	Правило произведения	]
	[	Объединение, пересечение и разность множеств	]

Сложность: 4
Классы: 10

Одна под другой выписаны 2^n–1 различных последовательностей из нулей и единиц длины n. Известно, что для любых трёх из выписанных последовательностей найдётся такой номер p, что в p-м разряде у всех трёх стоит 1. Доказать, что в некотором разряде у всех выписанных последовательностей стоит 1 и такой разряд только один.

Прислать комментарий

Решение

Задача 109859

Темы:	[	Индукция в геометрии	]
	[	Выпуклая оболочка и опорные прямые (плоскости)	]
	[	Разбиения на пары и группы; биекции	]
	[	Комбинаторная геометрия (прочее)	]
	[	Объединение, пересечение и разность множеств	]

Сложность: 5
Классы: 10,11

Автор: Дольников В.Л.

На плоскости рассматривается конечное множество равных, параллельно расположенных квадратов, причем среди любых k+1 квадратов найдутся два пересекающихся. Докажите, что это множество можно разбить не более чем на 2k-1 непустых подмножеств так, что в каждом подмножестве все квадраты будут иметь общую точку.

Прислать комментарий Решение

Страница: << 4 5 6 7 8 9 10 [Всего задач: 50]