Версия для печати
Убрать все задачи

---

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.

   Решение

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

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 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]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями