Мастерская ограничений: собери и опровергниЛогика / Строить взаимно однозначное назначение Пробное занятие
Логика · шаг 38 из 64

Хватит ли каждому своего места?

Строить взаимно однозначное назначение · Находить нехватку мест у группы

Около 19 минут 5 задач Подсказки рядом

В этом занятии

  • Строить взаимно однозначное назначение
  • Находить нехватку мест у группы
  • Отличать общий слот от отдельных подходящих слотов

Пригодится: Рекомендуем сначала пройти «Не угадывай: сокращай варианты».

Ваш путь начинается с личного кабинета

Взрослый создаёт аккаунт для себя и отдельные кабинеты для школьников. У каждого — свой прогресс. Общие 48 часов знакомства начинаются с регистрации взрослого; школьники получают оставшееся время.

Войти или начать бесплатно
Учебное время начнёт считаться после нажатия
Понять — интереснее, чем запомнить.
Разберёмся перед практикой+

Хватит ли каждому своего места?

Задача соответствия назначает каждому участнику одно подходящее место, причём места нельзя повторять. У каждого могут быть разрешённые варианты, но наличие хотя бы одного варианта у каждого ещё не гарантирует назначения для всех. Два участника могут претендовать только на одно место.

Конкретное назначение служит свидетельством существования: проверяем все допуски и отсутствие повторов. Для невозможности полезен другой свидетель — группа участников, у которой суммарно меньше доступных мест, чем участников. Такая группа обязательно создаёт конфликт независимо от порядка выбора.

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

Различайте требования «каждому своё место» и «один общий слот для всех». Первое допускает разные значения, второе требует пересечения всех списков. Это разные порядки кванторов и разные практические вопросы; успех одного не доказывает успех другого.

НА ПРИМЕРЕ

Ане подходят места 1 и 2, Борису только 1. Можно ли назначить каждому отдельное место?

  1. Сначала учитываем вынужденное место Бориса: 1.
  2. Ане остаётся подходящее место 2.
  3. Получаем назначение Аня → 2, Борис → 1 без повторов.

Попробуйте самостоятельно

Запишите рассуждения в черновик или сделайте построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.

  1. Нарисуй связь трёх участников с тремя местами; найди два разных назначения.
  2. Построй конфликт, где всем доступно какое-то место, но двум участникам вместе мест не хватает.

Читайте и разбирайте пример в своём темпе. К практике можно перейти, когда будете готовы.