Автомобили

[Гост]

Три автомобила (№ 1, 2 и 3) трябва да доставят стоки до шест магазина. По колко
начина автомобилите могат да извършат доставката на стоките, ако
товароносимостта на всеки от тях позволява доствка на стоките за всички магазини
наведнъж и ако до всеки магазин отива точно един автомобил, ако:
а) редът на магазините при доставката не се отчита?
б) редът на магазините при доставката се отчита?
Колко варианта на маршрута (реда на доставка на стоките до магазините) са
възможни, ако се реши да бъде използван само автомобил №1?
Упътване. Решете задачата в общия случай за k автомобила и n магазина.

[peyo]

Три автомобила (№ 1, 2 и 3) трябва да доставят стоки до шест магазина. По колко
начина автомобилите могат да извършат доставката на стоките, ако
товароносимостта на всеки от тях позволява доствка на стоките за всички магазини
наведнъж и ако до всеки магазин отива точно един автомобил, ако:
а) редът на магазините при доставката не се отчита?
б) редът на магазините при доставката се отчита?
Колко варианта на маршрута (реда на доставка на стоките до магазините) са
възможни, ако се реши да бъде използван само автомобил №1?
Упътване. Решете задачата в общия случай за k автомобила и n магазина.

При задачи с толкова много думи първо да се опитаме да направим математически модел с по-малко думи:

Имаме стоки $С_1,С_2, ...С_n$, които трябва да отидат съответно до магазини: $M_1,M_2, ...M_n$.
За тази цел имаме на разположение автомобили: $А_1,А_2,... А_k$, всеки от които може да натовари всички стоки наведнъж ако иска, но до всеки магазин може да отиде само един автомобил.

И сега:

а) По колко начина можем да извършим доставките на стоките, ако редът на магазините не се отчита?

$С_1$ можем да сложим в k автомобила.
$С_2$ можем да сложим също в k автомобила, стават $k^2$.
...
$С_n$ можем да сложим в k автомобила. Стават $k^n$.

И сега всеки автомобил отива и си доставя съответната стоки до съответния магазин и понеже реда по който ще обикалят магазините не е важен има само 1 начин това да стане.
Краен отговор: $k^n$

б) По колко начина можем да извършим доставките на стоките, ако редът на магазините се отчита?

От предишната подточна знаем, че можем да разпределим стоките по камиони (защото магазините се зареждат от камиони, а не автомобили) по $k^n$ начина.

Но какво ще стане ако всички стоки са в камион 1, то има $n!$ начина по които този камион да обиколи магазините. По същия начин ако всички стоки са в някой от другите камиони. Тогава ако всички стоки са в един камион то имаме:
$q_1 = kn!$

A ако всички са в 2 камиона? Разпределението на $n$ стоки в 2 камиона може да стане по $2^n - 2$ начина.
И сега ако са разпределението е (1, n-1), имаме 1 отива по 1 начин а (n-1) по (n-1)! начина, стават 1*(n-1)! = (n-1)!
A ако са разпределението е (2, n-2), имаме 2 отиват по 2 начина а (n-2) по (n-2)! начина.
A ако са разпределението е (3, n-3), имаме 3 отиват по 3! начина а (n-3) по (n-3)! начина.
Значи за 2 камиона имаме [tex]\sum_{i=1}^{n-1 }i!(n-i)![/tex], но имаме k камиона, значи за кои да е 2 камиона (и понеже подредбата на 2-та камиона не е важна тук):
[tex](k(k-1)/2!)\sum_{i=1}^{n-1 }i!(n-i)![/tex]

Да видим за 3 камиона. Може да имаме разпределения като (1,1,n-2) или ( 2,5,n-2-5). Всяко от тях може да отиде по факториал до магазините като:
1!*1!*(n-2)! и 2!*5!*(n-2-5)!

И тук ще трябва да помислим повече каква е общата формула за 3 случая, а после за 4 и до n и тук математическия модел който ползваме може да се окаже много тромав... Хм...

To be continued...