Probu1

Introduction

1. Извадка без връщане, с наредба: k от n. Брой възможности:

(1)
\begin{align} P_{n,k} = n(n-1)(n-2) \dots (n-k+1) &=& \frac{n!}{(n-k)!} \end{align}

В частност $P_{n,n} = n!$
Пример: По колко начина могат да се наредят 6 книги на рафт? По колко начина могат да се наредчт 4 книги от 6-те?

2. Извадка без връщане, без наредба: k от n. Брой възможности:

(2)
\begin{align} C_{n,k} = \binom{n}{k} = \frac{n!}{k!(n-k)!} \end{align}

Пример: По колко начина могат да се наредят в редица m мъже и n жени?

3. Извадка с връщане, с наредба: k от n. Брой възможности: $n^k$.
Пример: В група от k човека, каква е вероятноста двама да имат общ рожден ден?

Биномиална теорема:

(5)
\begin{align} (x + y)^n = \sum_{k=0}^N \binom{n}{k} x^k y^{n-k} \end{align}

Задача 1

Основният елемент на едно цифрово изображение се нарича пиксел. Всеки пискел се кодира двоично в съответната степен на скала на сивото. Например с два бита може да се кодира пиксел в четиристепенна скала на сивото с нива 00, 01, 10 и 11. Колко нива на сивото може да се кодират с четирибитов код? Колко бита са необходими за 32-степенна скала? Отг.: 16; 5.
Решение:
В случая имаме извадка с връшане и с наредба.
При $4$ битов код имаме $2^4$ наредби на $1$ и $0$. Това онзачава, че имаме $16$ цвята.
За да имаме 32 цвята кодирани с $1$ и $0$ ни трябват $x$ бита, тоест такава степен на двойката която да дава 32
$2^x = 32$ което означава $x = 5$.

Задача 2

Пет вида обвивки за оптичен кабел ще бъдат подложени на тест при много ниски температури. Редът на тестване е случаен. Колко наредби за реда на тестване на различните материали има? Ако два вида обвивки имат един и същ производител, колко начина има те да се окажат една след друга при теста. Каква е вероятността да се случи това?

Решение:

Зa наредбите имаме стандартно разпределение с наредба без връщане на 5 елемента, следователно
за първа позиция имаме $5$ за втора $4$… до $1$ и така броя наредби са $5!$

Ако две обвкивки има един и същ производител - имаме 4 прозиводителя да наредим с наредба без връщане тогава имаме $4!$ наредби.
Но единия производител има два кабела - тях можем да разместим по $2!$ начина за всяка наредба на производителите, тогава броя наредби стават $4!2!$

Отг.: 5!; 2!4!.

Задача 3

Изследва се ефективността на три вида полимери. Всеки от тях трябва да се тества при четири различни температури и три нива на радиация. Колко различни експериментални условия се определят по този начин? Ако при всяко експериментално условие трябва да се проведат по пет повторения на теста, колко общо експеримента ще бъдат проведени?

Отг.: 12; 180.

Решение:

Имаме две множества - едното с 3 експеримента другото с 4 експеримента и искаме да разберем по колко начина можем да изберем от тях двойка без наредба. Прилагаме принцип на умножението и получаваме 12.
За следващото отново прилагаме принципа на умножението но този пъ 3 множества с 3, 4 и 3 елемента и умножаваме по 5 защото искаме да проведем всеки експеримент по 5 пъти.
Да малоумно е, но е важно да разберете че тук се прилага 'принцип на умножението' а не просто инутитивно досещане.

Задача 4

Провежда се тест за скоростта на пет различни компилатора на един и същ език за програмиране. Колко сравнения могат да бъдат направени, ако компилаторите се сравняват два по два?
Отг.: 10.

Решение:
Имаме едно множество от 5 елемента и искаме да разберем по колко начина можем да изберем два от тях без да има значение наредбата:

$\binom{5}{2} = 10$

Задача 5

Във фирма работят 10 програмиста, 8 тестера, 4 компютърни инженера и 3 статистика. Избира се екип за дългосрочен проект, в който трянва да се включат 3 програмиста, 2 тестера, 2 компютърни инженера и 1 статистик. По колко начина може да се избере такъв екип? Ако клиентът настоява в проекта да работи определен инженер, с който са работили и преди, по колко начина може да се избере екипът?

Отг.: 60480; 30240.

Решение:

Използваме принципа за умножение и избиране на елемнти от множество без връщане:
и получаваме
по колко начина можем да изберем 3 програмиста от 10
… същото е за другите избори
математичекски
$\binom{10}{3}\binom{8}{2}\binom{4}{2}\binom{3}{1} = \frac{10!}{3!7!}\frac{8!}{2!6!}\frac{4!}{2!2!}\frac{3!}{1!2!} =$
$= \frac{4*3*10}{1}\frac{7*4}{1}\frac{2*3}{1}\frac{3}{1} = 60 480$
За втория въпрос, просто единия човек вече е избран и го махаме от избора и от множеството:
$\binom{10}{3}\binom{8}{2}\binom{3}{1}\binom{3}{1} = \frac{10!}{3!7!}\frac{8!}{2!6!}\frac{3!}{1!2!}\frac{3!}{1!2!} =$
$= \frac{4*3*10}{1}\frac{7*4}{1}\frac{3}{1}\frac{3}{1} = 30 240$

Задача 6

Колко възможни 128-битови съобщения с точно две грешки (смяна на бита) има? Колко са съобщенията с до две грешки? Каква е вероятността да се получи съобщение с не повече от две грешки?

Отг.: 8128; 8257; $\frac{ 8257}{2^{128}}$ .

Решение:
Имаме $128$ бита, въпроса е по колко начина можем да си изберем два от тях, който да са грешни
$\binom{128}{2} = 8128$
Имаме 128 бита, искаме да намерим по колко начина можем да изберем 2 да са грешни и по колко 1 да е грешен и по колко нитое един грешен

$\binom{128}{2} + \binom{128}{1} + 1 = 8128 + 128 + 1 = 8257$

И последното е горе долу очевидно имаме боря на съобщенията, които търсим, а общия брой съобщения е $2^{128}$
$\frac{ 8257}{2^{128}}$

Задача 7

Фирма предлага на клиентите си да получат при покупката на компютър безплатно 10 софтуерни пакета, като могат да избират от 25 налични. По колко начина може да се направи такъв избор? Пет от наличните пакети са игри. Ако три от избраните са игри, колко са начините, по които може да бъде направен такъв избор?
Отг.: 3268760; 775200.

Решение:
Първото е очевисно по колко начина можем да изберем 10 от 25
$\binom{25}{10} = 3268760$
При второто имаме избиране от две множества и след това е принципът за умножението.
$\binom{20}{7}\binom{5}{3} = 775200$

Задача 8

Компютърна система има парола, която е съставена от пет латински букви, последвани от една цифра. Колко възможни пароли има? Колко пароли съдържат три пъти A и два пъти B и завършват на четна цифра? Ако сте забравили паролата си, но знаете, че отговаря на горното условие, каква е вероятността от първия път
да я улучите? Отг.: 118813760; 50; 1/50.

Решение:
Имаме 26 латински букви, явно паролите не са case sensitive. И 5 позиции за латински букви. Имаме и 10 числа и една позиция за число.
Следователно използваме наредба с връщане и принципа за събиране и получаваме
$26^5*10 = 118 813 760$

Втората час е по-интересна.
Три пъти $A$ и два пъти $B$ са 5 символа. И така обръщаме задачата така, че от 5-те позиции за символи избираме 3 за да сложим А в тях. B-тата директно попадат на останалите.
$\binom{5}{2} = 10$ по принципа за събираме умножаваме с броя на четните цифри - 5 и получаваме $50$ пароли. Вероятността да я уцелим от първия път е 1 на 50.

Задача 9

Фенерче работи с две батерии. Ако разполагате с 8 батерии, три от
които са изтощени, но вие не знаете кои точно и опитвате случайно,
2
в колко от случаите фенерчето ще работи и в колко - не? Каква е
вероятността фенерчето да проработи с първите две батерии, които
вземете? Отг.: 10/28.

Задача 10

Колко са начините да се разпределят k неразличими обекта в n
кутии? А ако обектите са различими?

Решение:
стандатна задача - http://en.wikipedia.org/wiki/Stars_and_bars_(probability)

Идеята е че нареждаме к-те неразличними обекта на една линия и след това между всеки два можем да слагаме преграда. Така имаме $k-1$ места за прегради и искаме да изберем $n$ от тях. Но ние можем да имаме и празни чекмеджета тогава имаме $k-1+n$ места за слагане на прегради и от тях искаме да изберем $n$.

Ако предметите са различими - тогава за всеки предмет имаме по $n$ възможности да го сложим което прави $n^k$.

Задача 11

Колко са всички частни производни от $n$-ти ред на функция на $к$ променливи.
отг. : ${n +k - 1 \choose k}$

Задача 12

Докажете принципа за събиране и изваждане..

Задача 13

Резултатът от обработката на данни от проведена анкета с 1000
лица е следният: английски език владеят 811 души, френски - 752,
руски - 418, английски и руски - 356, английски и френски - 570,
френски и руски - 348, английски, френски и руски - 297. Верен ли
е резултатът? Отг.: не.

Решение:
Прилагаме принципа за събиране и изваждане, показваме че равенството не е изпълнено.

Задача 14

Докажете:

${n \choose 0} - {n \choose 1} + {n \choose 2} - {n \choose 3} + ... + (-1)^n {n \choose n} = 0$
${n \choose 0} + {n \choose 1} + {n \choose 2} + {n \choose 3} + ... + {n \choose n} = 2^n$

Решение:
За пътвото използваме, че ${n \choose k} = {n \choose n-k}$
За второто използвам, че $2^n = (1+1)^n$ и развиваме по биномиалната теорема.

Задача 15

Докажете:

${n \choose k} = {n \choose n-k}$
${n \choose k} = {n - 1 \choose k - 1} + {n-1 \choose k}$
$\sum_{0 \leq k \leq n} {k \choose m} = {0 \choose m} + {1 \choose m} + {2 \choose m} + {3 \choose m} + ... + {n \choose m} = {n + 1 \choose m + 1}$
$sum_{0 \leq k \leq n} {r \choose k}{s \choose n-k} = {r+s \choose n}$

Задача 16

16. Имаме $n$ обекта, от които $n_1$ са от тип $t_1$, $n_2$ от тип $t_2 , . . . n_k$ от тип
$t_k$. Ако обектите от всеки тип се считат за неазличими, колко са
начините за наедба на всичките n обекта?

Решение:
Това е стандартна задача, ще се опитам да я обясня максимално ясно. Идеята използвана в нея се прилага на много места.

Ако обектите бяха различими всички наредби са $n!$. Но ние имаме неразличими обекти.

Всяка група от тези неразличими обекти има по $n_k$ обекта - тези обекти можем да наредим по $n_k!$ начина.
И така искаме от всички наредби да махнем възможните размествяния, които не променят наредбата тогава отговора става

$\frac{n!}{n_1!...n_k!}$.

Ако имаме една наредба елементите от $t_k$ могат да бъдат разместени по $n_k!$ начина и наредбата да си остане същата.
При $n!$ сме преброили $n_k!$ пъти тази наредба, за това делим на $n_k!$ и получаваме $1$ за тази наредба.

Отг.: $\frac{n!}{n1!n2!...nk! }$

Задача 17

Експеримент се състои в следното: избира се случайно цифра от 0
до 9, като всяка цифра има еднакъв шанс да бъде избрана, присвояваме
стойността на избраната цифра на променливата A и изпълняваме
следния код:

IF A < 2 THEN B = 12; ELSE B = 17;
IF B = 12 THEN C = A - 1; ELSE C = 0;

Каква е вероятността A да бъде четно число? Каква е вероятността
C да бъде отрицателно? Каква е вероятността C = 0? Каква е
вероятността C 1? Отг.: 1/2; 1/10; 9/10; 1.

Задача 18

Колко плочки за игра на домино могат да се образуват от числата
от 1 до n, ако на всяка плочка има по две числа и плочките са
симетрични? Отг.: n(n + 1)/2.

Задача 19

Ако n различни топки с поставт в n кутии, каква е вероятността
да остане точно една пазна кутя?

Отг.: ${n \choose 2} n! / n^n$

Задача 20

Телефонът ви звъни по 12 пъти на седмица, като позвъняванията
попадат случайно в кой да е ден от седмицата. Каква е вероятността
да звъни поне веднъж на ден? Отг.: 0:2285.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License