1. Главная
  2. Библиотека
  3. Теория вероятностей
  4. Однажды один рассеянный профессор дал задание студентам...
Разбор задачи

Однажды один рассеянный профессор дал задание студентам: произвести выборку без повторений случайного непустого подмножества объектов из набора данных. Результат выполнения задания — список номеров объектов. Он собрал эти списки у студентов и нечаянно

  • Предмет: Теория вероятностей
  • Автор: Кэмп
  • #Теория вероятностей и математическая статистика
  • #Выборочные методы
Однажды один рассеянный профессор дал задание студентам: произвести выборку без повторений случайного непустого подмножества объектов из набора данных. Результат выполнения задания — список номеров объектов. Он собрал эти списки у студентов и нечаянно

Условие:

Однажды один рассеянный профессор дал задание студентам: произвести выборку без повторений случайного непустого подмножества объектов из набора данных. Результат выполнения задания — список номеров объектов. Он собрал эти списки у студентов и нечаянно объединил их в один большой список.
Теперь профессор не может проверить отдельно список каждого студента. Тогда он решает, что просто попробует подобрать такие списки, которые в итоге дадут один большой полученный список. Если такие списки существуют, всем студентам зачтётся выполнение задания. Если нет — не зачтётся никому. Помогите профессору определить, существуют ли такие списки?

Решение:

Рассмотрим условие задачи. Каждый студент должен был выбрать некоторое непустое подмножество объектов (то есть, список номеров объектов без повторений) из фиксированного набора. Получается, что в каждом отдельном списке все номера встречаются не более одного раза. Затем профессор ошибочно склеил все списки в один длинный список, потеряв информацию о том, какие номера относятся к какому студенту.

Нужно понять, существует ли такое разбиение большого списка на несколько подряд идущих частей, что в каждой части все номера уникальны. Если такое разбиение можно построить, то профессо...

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какое условие должно выполняться для каждого списка, сданного студентом, чтобы задание считалось выполненным?

Что нужно знать по теме:

Что нужно знать по теме

Алгоритм решения

Топ 3 ошибок

Что спросит препод

Выбери предмет