Задача на Выборку с ограничениями

@zagruzkaaa · Регистрация: 03.06.2012

Студворк — интернет-сервис помощи студентам

В 11-м классе 19 учеников. Каждый из них помимо обязательных ЕГЭ по математике и русскому сдает дополнительные ЕГЭ по трем предметам, выбирая эти предметы из единого для всех набора из девяти предметов. Сколькими способами может быть сделан выбор предметов учениками класса, так чтобы с одной стороны никакие два учееника не сдавали одинаковый набор ЕГЭ, а с другой чтобы каждый из девяти дополнительных предметов был выбран хотя бы один раз.

Прошу помочь в решении. Спасибо

zer0mail · 30.09.2013, 16:31

Пишите, как решали - а мы поможем

iifat · 30.09.2013, 16:34

Ну, начни хоть. Забудем пока про

Сообщение от zagruzkaaa

каждый из девяти дополнительных предметов был выбран хотя бы один раз

Сколько вариантов выбора трёх предметов из девяти? Сколькими способами можно выбрать девятнадцать различных троек?

@zagruzkaaa · 30.09.2013, 16:47 **[ТС]**

Сообщение от iifat

Ну, начни хоть. Забудем пока про Сколько вариантов выбора трёх предметов из девяти? Сколькими способами можно выбрать девятнадцать различных троек?

3 предмета выбираем С(из 9 по 3) = 84
А потом для 19 человек мне кажется 84*83*82*....*66
а вот как последнее условие сделать вообще не представляю

@Том Ардер · 30.09.2013, 17:04

Сообщение от zagruzkaaa

3 предмета выбираем С(из 9 по 3) = 84

Комментарий модератора

Формулы не словами рассказывают, а пишут символами. Редактор формул
Освоить необходимо.

@zagruzkaaa · 30.09.2013, 17:06 **[ТС]**

3 предмета выбираем $https://www.cyberforum.ru/cgi-bin/latex.cgi?{C}^{3}_{9}$ = 84
А потом для 19 человек мне кажется 84*83*82*....*66
а вот как последнее условие сделать вообще не представляю

zer0mail · 30.09.2013, 20:03

Надо попробовать для меньших чисел, например: 4 человека, 3 предмета из 5, чтобы все комбинации можно было явно перебрать.

А то 84*83*..*66 = это ~4*10³⁵, многовато (особенно для ЕГЭ)

@zagruzkaaa · 30.09.2013, 20:36 **[ТС]**

Сообщение от zer0mail

Надо попробовать для меньших чисел, например: 4 человека, 3 предмета из 5, чтобы все комбинации можно было явно перебрать.

А то 84*83*..*66 = это ~4*10³⁵, многовато (особенно для ЕГЭ)

для вашего примера получается 720 вариантов, их перебрать тоже не очень то выйдет

@m-ch · 30.09.2013, 21:52

Скорее всего 10*9*8*7 = 5040

при этом, если наложить ограничение, что все предметы должны быть выбраны хоть один раз, кол-во будет меньше

как минимум комбинации
1, 2, 3
1, 2, 4
1, 3, 4
2, 3, 4
и т.п. нужно исключать

Добавлено через 12 минут
Итого результат будет 5040 - 120 = 4920

zer0mail · 30.09.2013, 22:07

Вот как раз 120 и вызывает сомнение

Как ее правильно вычислить...

@m-ch · 30.09.2013, 22:31

Сообщение от zer0mail

Вот как раз 120 и вызывает сомнение Как ее правильно вычислить...

120 вычислил перебрав все возможные комбинации, логически можно осознать, как она расчитывается - 120 = 5!
так 4 ученика теоритически могут выбрать 4 предмета, соответственно какой то один из 5 предметов не выбирается
в посте выше я привел одну из возможных выборок, соответствено все остальные комбинации получаюся перестановкой 5 предметов, не совсем логично, но как то так на подсознательном уровне.

Что делать с 19 учениками и 9 предметами - не знаю

zer0mail · 30.09.2013, 23:26

Глянуть бы на эти 120 вариантов (боюсь, там есть повторы)

iifat · 01.10.2013, 06:40

Сообщение от zagruzkaaa

84*83*82*....*66

Это называется размещениями, $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_{84}^{19}$ .
Дальше — есть такой метод включений-исключений.
Для девяти предметов $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_{C_9^3}^{19}$ вариантов; из них $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_{C_8^3}^{19}$ не включают какой-то предмет, поскольку составлены из восьми. Надо эти варианты вычесть. Если написать $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_{C_8^3}^{19}-9A_{C_8^3}^{19}$ , то $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_{C_7^3}^{19}$ вариантов с двумя отсутствующими предметами будут вычтены два раза, то бишь, это выражение надо добавить для каждой пары. Получаем формулу $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_{C_8^3}^{19}-C_9^1A_{C_8^3}^{19}+C_9^2A_{C_7^3}^{19}$ Продолжая в том же духе, получим $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_0^\infty{(-1)}^kC_{9-k}^kA_{C_{9-k}^k}^{19}$ . Сумма на самом деле конечная, поскольку уже для шестого члена ( $https://www.cyberforum.ru/cgi-bin/latex.cgi?k=5$ ) $https://www.cyberforum.ru/cgi-bin/latex.cgi?C_{9-k}^k=0$ .
А вот можно ли её упростить — вопрос...

@m-ch · 01.10.2013, 08:22

Сообщение от zer0mail

Глянуть бы на эти 120 вариантов (боюсь, там есть повторы)

Да пожалуйста (отмечены желтым)

@zagruzkaaa · 01.10.2013, 22:10 **[ТС]**

Сообщение от iifat

Получаем формулу $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_{C_8^3}^{19}-C_9^1A_{C_8^3}^{19}+C_9^2A_{C_7^3}^{19}$

тут первый элемент выборка не из 9 должеа быть?
И не понимаю почему если мы вычтем $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_{C_9^3}^{19}-9A_{C_8^3}^{19}$ то $https://www.cyberforum.ru/cgi-bin/latex.cgi?A_{C_7^3}^{19}$ вычитается 2 раза?

Добавлено через 8 минут
И конечная формула не такая должна быть?
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_0^\infty{(-1)}^kC_{9}^kA_{C_{9-k}^3}^{19}$

iifat · 02.10.2013, 07:25

Сообщение от zagruzkaaa

И конечная формула не такая должна быть?

Да. Разумеется, такая. Описался

Добавлено через 1 минуту

Сообщение от zagruzkaaa

И не понимаю почему если мы вычтем то вычитается 2 раза?

В этих, уж не знаю, как назвать, вариантах не используются два предмета. Они входят как в варианты без одного предмета, так и без другого. Поэтому вычтутся два раза.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 03.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

@zagruzkaaa 2 / 2 / 0 Регистрация: 03.06.2012 Сообщений: 56

	Задача на Выборку с ограничениями 30.09.2013, 16:19. Показов 2603. Ответов 15 Метки нет (Все метки) В 11-м классе 19 учеников. Каждый из них помимо обязательных ЕГЭ по математике и русскому сдает дополнительные ЕГЭ по трем предметам, выбирая эти предметы из единого для всех набора из девяти предметов. Сколькими способами может быть сделан выбор предметов учениками класса, так чтобы с одной стороны никакие два учееника не сдавали одинаковый набор ЕГЭ, а с другой чтобы каждый из девяти дополнительных предметов был выбран хотя бы один раз. Прошу помочь в решении. Спасибо 1

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	30.09.2013, 16:31
	Пишите, как решали - а мы поможем 1

@zagruzkaaa 2 / 2 / 0 Регистрация: 03.06.2012 Сообщений: 56
	30.09.2013, 17:06 [ТС]
	3 предмета выбираем $https://www.cyberforum.ru/cgi-bin/latex.cgi?{C}^{3}_{9}$ = 84 А потом для 19 человек мне кажется 848382....66 а вот как последнее условие сделать вообще не представляю 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	30.09.2013, 20:03
	Надо попробовать для меньших чисел, например: 4 человека, 3 предмета из 5, чтобы все комбинации можно было явно перебрать. А то 8483..66 = это ~410³⁵, многовато (особенно для ЕГЭ) 0

@m-ch 6180 / 945 / 313 Регистрация: 25.02.2011 Сообщений: 1,381 Записей в блоге: 1
	30.09.2013, 21:52
	Скорее всего 10987 = 5040 при этом, если наложить ограничение, что все предметы должны быть выбраны хоть один раз, кол-во будет меньше как минимум комбинации 1, 2, 3 1, 2, 4 1, 3, 4 2, 3, 4 и т.п. нужно исключать Добавлено через 12 минут* Итого результат будет 5040 - 120 = 4920 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	30.09.2013, 22:07
	Вот как раз 120 и вызывает сомнение Как ее правильно вычислить... 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	30.09.2013, 23:26
	Глянуть бы на эти 120 вариантов (боюсь, там есть повторы) 0