Дискретни структури, КН2, зимен семестър 2017/2018

Задача 1.  Функция, дефинирана върху множеството  { 1;  2; . . . ;  n },
всъщност е крайна редица с n члена. Така че в задачата се търси
броят на редиците с n члена, всеки от които е 1 или 2, . . . , или n.
     Нека x_i е броят на срещанията на числото i като член на редицата,
където i приема всяка цяла стойност от 1 до n включително.
Тогава x₁ , x₂ ,  . . .  , x_n  са цели неотрицателни числа и
                                         x₁ + x₂ +  . . .  + x_n  = n.
Броят на решенията на това уравнение в цели неотрицателни числа
е равен на броя на комбинациите с повторение на n елемента от клас n.
Този брой съвпада с биномните коефициенти 2n–1 над n–1 и 2n–1 над n.

Задача 2.  Оцветяваме квадратчетата шахматно по стандартния начин:
бяло поле в долния десен ъгъл. Тогава двете изрязани полета —
долното дясно и горното ляво — имат бял цвят. След изрязването им
на дъската остават общо 62 полета, от които 30 бели и 32 черни.
За покриването на 62 полета са нужни 31 плочки от домино.
Всяка плочка покрива едно бяло и едно черно поле,
следователно 31 плочки ще покрият 31 бели и 31 черни полета,
а не 30 бели и 32 черни полета. Ето защо дадените 62 квадратчета
не могат да бъдат покрити с плочки от домино по искания начин.

Задача 3  може да се реши по различни начини, например чрез индукция.
Тук ще разгледаме едно решение по метода на екстремалния елемент.
     Нека  u  е онзи връх на графа, от който излизат най-много ребра.
(Ако има няколко такива върха, няма значение кой от тях ще изберем.)
Ще покажем, че върхът  u  има желаното свойство. Допускаме противното:
че съществува връх v, до който не можем да стигнем от u  нито за една,
нито за две стъпки.
     Щом от u  не може да се стигне до  v  за две стъпки, то за всеки връх  w,
за който има ребро от u  към w, не може да има ребро от w към v, тъй като
ще се получи път  u –> w –> v  от  u  до v  с дължина 2, а такъв няма.
Понеже графът е пълен, то за всеки връх  w,  за който има ребро от u  към w,
трябва да има ребро и от v  към w.  Следователно броят на ребрата,
излизащи от v, е поне колкото броя на ребрата, излизащи от u.
     От u  не можем да стигнем до v за една стъпка, тоест реброто между тях
сочи от v към u.  Следователно броят на ребрата, излизащи от v,
е поне с 1 повече от броя на ребрата, излизащи от u.
Това противоречи на максималността на u.
     Полученото противоречие показва, че направеното допускане не е вярно.
Следователно вярно е твърдението на задачата.

Задача 4.  Сумата в лявата страна на тъждеството представлява
броят на сюрекциите от вида  f : X –> Y, където | X | = m,  | Y | = n.
Ако  m < n,  то не е възможно с m стойности на функцията да изчерпим
всичките n елемента на множеството Y.  Затова при  m < n
броят на сюрекциите е нула — дясната страна на тъждеството.