Колко са четирицифрените числа, чийто сбор от цифрите е 9

[ivan129]

зад.1
Група от 10 души трябва да бъде разделена на две непразни подгрупи А и В. Колко са начините, по които това може да се направи?
зад.2
Група от 24 студента (12 момичета и 12 момчета) се разделя на две равни подгрупи, така че във всяка подгрупа да има равен брой момчета и момичета. По колко начина може да се направи това?
зад.3
Колко са четирицифрените числа, чийто сбор от цифрите е равен на 9?
зад.4
Линия на подземният влак на метрото има 16 спирки, на които пътниците слизат. По колко начина могат 100 пътника, които са влезли във влака на началната спирка, да слязат на тези спирки?
зад.5
Асансьор с 9 пътници може да спре на 10 етажа. На един етаж слизат 2 човека, на друг етаж слизат 3 и на трети слизат 4. По колко начина пътниците могат да излязат от асансьора?

[peyo]

зад.1
Група от 10 души трябва да бъде разделена на две непразни подгрупи А и В. Колко са начините, по които това може да се направи?

Много интересна и както ще видим трудна задача!

Логично е, че реда на хората вътре в групата не е важен, но имената им са важни.

Ако групите са от:
1 - 9, то за първата група имаме 10 възможности, за втората 9!/9! = 1, значи общо 10
2 - 8, то за първата група имаме 10*9/2! възможности, за втората 9!/9! = 1, значи общо 10

По-нататък става по-сложно, затова да сменим подхода.

За да се изредят всички възможности, всеки човек трябва да бъде част от група от 1 до група от 9.
За да може ески да бъде група от:
1 - имаме 10 възможности.
2 - имаме 10*9/2
3 - имаме 10*9*8/(3*2*1)
4 - имаме [tex]{10 \choose 4}[/tex]
5 - имаме [tex]{10 \choose 5}[/tex]
6 - имаме [tex]{10 \choose 6}[/tex] ok, да ама другата група е 4, а ние вече имаме група от 4 малко по-горе. Тогава тази група да я броим ли или не? Хмм... От предишната група 4 по-горе всички 10 човека са част, значи всички 10 човека са част и от групата 6. Значи тази група 6 няма да я броим и всички останали по-големи също. И така крайния отговор е:

[tex]\sum_{k=1}^{5 }{10 \choose k}[/tex]

In [37]: sum( [ scipy.special.binom(10,k) for k in range(1, 5+1)])
Out[37]: 637.0

Добре обаче какво правим с група 5?
In [36]: scipy.special.binom(10,5)
Out[36]: 252.0

Това е по-колко начина можем да разделим 10 човека в 2 групи от по 5 човека? Обаче реда на групите не е важен! Значи вссяко разпределение се повтаря. Значи всъщност отговора е 2-пъти по-малък!
In [39]: 252/2
Out[39]: 126.0

Тогава правилния отговор на задачата е:

[tex]\sum_{k=1}^{4 }{10 \choose k} + {10 \choose 5}/2[/tex]

In [40]: sum( scipy.special.binom(10,k) for k in range(1, 4+1)) + scipy.special.binom(10,5)/2
Out[40]: 511.0

[peyo]

зад.2
Група от 24 студента (12 момичета и 12 момчета) се разделя на две равни подгрупи, така че във всяка подгрупа да има равен брой момчета и момичета. По колко начина може да се направи това?

С малко чудене се сещаме, че двете подгрупи може да бъдат от различен брой хора. Например
mmmfff, mmmmmmmmmfffffffff

Така възможните групи са от хора на брой:
2:22
4:20
6:18
8:16
10:14
12:12

И сега във всяка група трябва да имаме равен брой момичета и момчета. За всички възможности, всяко момче и момиче трябва да бъде част от всички групи.
2:22 -> (1m,1f),(11m,11f) -> група от (1m,1f) можем да направим по 12*12 = 144 начина. И сега за всеки от тези 144 начина група от (11m,11f) може да направим само по 1 начин, значи общо 144
4:20 -> (2m,2f),(10m,10f) -> група от (2m,2f) можем да направим по (12*11/2)*(12*11/2) = 4356 начина. И сега за всеки от тези 4356 начина група от (10m,10f) може да направим само по 1 начин, значи общо 4356.
6:18 -> (3m,3f),(9m,9f) -> група от (3m,3f) можем да направим по (12*11*10/(3*2*1))**2 = 48400 начина
8:16 -> (4m,4f),(8m,8f) -> [tex]{12 \choose 4}^2[/tex]
...
Или отговора става накрая:
[tex]\sum_{k=1}^{6 }{12 \choose 4}^2[/tex]

Да ама последната група ${12 \choose 6}^2$ се повтаря, значи след корекцията:
[tex]\sum_{k=1}^{5 }{12 \choose 4}^2 + {12 \choose 4}^2/2[/tex]

In [45]: sum( scipy.special.binom(12,k)**2 for k in range(1, 5+1) ) + scipy.special.binom(12,2)**2/2
Out[45]: 927367.0

[peyo]

зад.3
Колко са четирицифрените числа, чийто сбор от цифрите е равен на 9?

Много интересно!

Първата цифра трябва да е от 1 до 9, другите от 1-10.
Ако първата е 9, то другите 3 трябва да са 0, значи 1
Ако първата е 8, то другите 3 трябва да са 100,010 или 001, значи 3
Ако първата е 7, то другите 3 трябва да са уникални пермутации от 110 или 200 ,значи 3*2/2 + 3 = 6
Ако първата е 6, то другите 3 трябва да са уникални пермутации от 111, 120, 300 ,значи 1 + 3*2 + 3 = 10
Ако първата е 5, то другите 3 трябва сбора им да е 4 и да са уникални пермутации от 211, 220, 310, 400 ,значи 3*2/2 + 3*2/2 + 3*2 + 3 = 15
Ако първата е 4, то другите 3 трябва сбора им да е 5 и да са уникални пермутации от 221 ...
Задачата по-нататък става сложна за ръчно преброяване май. Да помислим малко повече ... Хмм...

[Гост]

..Хммм...

Или пък да преброим колко са числата, като започнем от 1008, сетне 1017, 1026 и т.н. Абе, всяко следващо да е с 9 повече от предното. И така, докато стигнем чааак до 9999.
Чудя се...,колко ли може да са тези числа ?!?

[Гост]

..Хммм...

Май няма да стане така. То пък трябвало сборът на цифрите да е точно 9.

[peyo]

зад.3
Колко са четирицифрените числа, чийто сбор от цифрите е равен на 9?

Много интересно!

Първата цифра трябва да е от 1 до 9, другите от 1-10.
Ако първата е 9, то другите 3 трябва да са 0, значи 1
Ако първата е 8, то другите 3 трябва да са 100,010 или 001, значи 3
Ако първата е 7, то другите 3 трябва да са уникални пермутации от 110 или 200 ,значи 3*2/2 + 3 = 6
Ако първата е 6, то другите 3 трябва да са уникални пермутации от 111, 120, 300 ,значи 1 + 3*2 + 3 = 10
Ако първата е 5, то другите 3 трябва сбора им да е 4 и да са уникални пермутации от 211, 220, 310, 400 ,значи 3*2/2 + 3*2/2 + 3*2 + 3 = 15
Ако първата е 4, то другите 3 трябва сбора им да е 5 и да са уникални пермутации от 221 ...
Задачата по-нататък става сложна за ръчно преброяване май. Да помислим малко повече ... Хмм...

Нека да предположим, че водещите цифри могат да бъдат 0. Така няма ограничение за цифрите и всяка може да е от 0-10.

Нека $n$ е колко цифри има числото, а $x$ нека бъде колко е сбора от цифрите. Тогава търсим следната функция:
f(n, x) = ?


$f(1, x) = 1$
$f(2, x) = (x+1) = \sum_{k=0}^{x } f(1,x-k)$
[tex]f(3, x) = \sum_{k=0}^{x } f(2,x-k)[/tex]
[tex]f(4, x) = \sum_{k=0}^{x } f(3,x-k)[/tex]

И така намерихме общата рекурсивна формула:
[tex]f(n, x) = \sum_{k=0}^{x } f(n-1,x-k)[/tex]

Или на Python:

Код: Избери целия код

def f(n,x):
   if n==1:
      return 1
   return sum( [f(n-1, x-k) for k in range(0, x+1) ])

Добре обаче в нашия случай позволяваме числото да започва с 0, което не е добре и трябва да изхвърлим тези числа. Значи трябва да изхвърлим всички 4 цифрени числа, които започват с 0 и сбора им е 9. Това са $f(3,9)$ Значи крайния отговор е:

$f(4,9) - f(3,9)$

Да видим колко е това:

In [63]: f(4,9) - f(3,9)
Out[63]: 165

Ок, да направим проверка дали сме смятали правилно:

Код: Избери целия код

from itertools import product
c=0
for a in product(range(10), repeat=4):
   if sum(a) == 9 and a[0]!=0:
      c+=1
print(c)

Резултата е 165, значи всичко е ок и задачата е решена.

И някой ще каже, да ама тази формула защо е рекурсивна, аз искам нерекурсивна формула! Ок, може да помислим малко повече тогава ...

[pal702004]

Колко са четирицифрените числа, чийто сбор от цифрите е равен на 9?

Колкото са решенията в цели неотрицателни числа на уравнението $x_1+x_2+x_3+x_4=8$ (към $x_1$ винаги трябва да добавим 1). Това още се нарича слаба композиция на числото 8 с дължина 4. И е равна на

$C_{8+4-1}^{4-1}=C_{11}^3=165$

[peyo]

Колко са четирицифрените числа, чийто сбор от цифрите е равен на 9?

Колкото са решенията в цели неотрицателни числа на уравнението $x_1+x_2+x_3+x_4=8$ (към $x_1$ винаги трябва да добавим 1). Това още се нарича слаба композиция на числото 8 с дължина 4. И е равна на

$C_{8+4-1}^{4-1}=C_{11}^3=165$

Ха! Вярно, че отговора е еднакъв с $f(4,8)$ !
In [65]: f(4,8)
Out[65]: 165

Значи:

$f(4,9) - f(3,9) = f(4,8)$

Изгкежда е вярна и по-общата формула, но доказателството ще е трудно:

$f(a,b) - f(a-1,b) = f(a,b-1)$

Имаме много интересно функционално уравнение, решенията на което както изглежда са с биноми на Нютон.

[pal702004]

А колко са четирицифрените числа със сбор на цифрите 18? Приветства се комбинаторно решение.