Задача от математически турнир Harvard-MIT

[Knowledge Greedy]

Четирима студенти от Харвард, сред които е Джейн и петима студенти от Масачузетс, сред които е Джил, възнамерявали да отидат на мач на Бостън Селтикс. За беда на приятелите, те успели да намерят само 5 билета и затова 4-ма от тях трябвало да се върнат. Да предположим, че от всеки университет поне един студент трябва да посети мача, а също така поне едно от двете момичета Джейн или Джил трябва да гледа мача. По колко начина може да бъде направен изборът на петима студенти измежду всичките, които да наблюдават мача?

[Davids]

В първия случай приемаме, че първия билет отива при Джейн от Харвард. Знаем, че още един от Масачузетс трябва да отиде. И вече останалите 3 билета ги разпределяме на случаен принцип измежду останалите студенти. Тоест начините са общо:
[tex]N_1 = 1.5.C^3_7 = 5.\frac{7.6.5}{3.2.1} = 25.7 = 175[/tex] начина за разпределение, ако Джейн е момичето, което ще отиде.
Във втория случай че искаме Джил да е момичето. За нея отново отива един билет. Още един от Харвард трябва да отиде, но вече сме включили всички възможни комбинации, в които Джил и Джейн отиват заедно, следователно този път трябва да пропуснем Джейн от състава на Харвардците. Тоест ще включим само един от другите трима, а останалите три билета ще разпределим сред останалите. Или:
[tex]N_2 = 1.3.C^3_6 = 3.\frac{6.5.4}{3.2.1} = 3.5.4 = 60[/tex]
И, ако не се бъркам, получаваме общо [tex]N = 235[/tex] начина, по които може да стане групирането

[pal702004]

1. Отиват и Джейн и Джил:
Останалите трима може да са всякакви $C_7^3=35$

2. Отива Джейн, Джил НЕ отива:
Останалите четирима може да са всякакви $C_7^4=35$

3. Отива Джил, Джейн НЕ отива
Аналогично на горното с изключение на случая, когато и петимата са от Масачузетс. $C_7^4-1=34$

начи, $104$ начина.

[Davids]

Мерси, намерих си грешката

[pal702004]

Davids, грешчицата е там, че (в първият случай) маркираш един от Масачузетс (напр. Джон) и останалите трима избираш свободно (сред които и Джим от Масачузетс). След това маркираш Джим и останалите трима избираш свободно (а сред тях - и Джон). Тоест, дублират се решения.

Правилно би било $N_1=C_8^4$

$N_2=C_7^4-1$

Всъщност, условието "от всеки универсистет поне един студент трябва да посети мача" е почти излишно, тъй като изключва само един вариант - и петимата да са от Масачузетс. И можем да работим без него.

От всички възможни комбинации махаме тези, в които няма каки. И, разбира се, особенния случай:

$C_9^5-C_7^5-1$

[Davids]

Именно, но не се бях замислил... И не го улових като пропуск съответно