някои грешки в решенията на изпита
1) В бонуса се иска да се докаже, че има Хамилтонов цикъл. А не Ойлеров! В общия случай няма (не е известно...) просто НДУ за Х. цикъл. Но ако мин. степен >= ceil(n/2), има Х. цикъл. Това е теорема на Дирак. Има я в лекционните записки по графи. Не е тривиално твърдение и затова е бонус 33%.
2) Има няколко ad hoc решения на зад 6, обосновани с диаграми на Вен. Това не е формално решение. За пълен брой точки трябва да е ясно, че владеете принципа на вкл/изкл по принцип.
3) Някои решения на зад 5 казват, че щом g : B --> C не е инекция, задължително |B| > |C|. Няма такова нещо. Измислете сами контрапример.
4) Едно решение на зад 5 се основава на контрапример. Това не е валидно решение. **Щеше** да е валидно, ако твърдението беше
за всяка f, за всяка g : g o f е инекция
Но не това се твърди в условието. Условието не е записано с квантори, но, ако беше записано с квантори, щеше да е
съществува f, съществува g : g o f е инекция
Негацията му е
за всяка f, за всяка g : g o f не е инекция
Това не се доказва с пример.
5) Пак задача 5. Това, че f не е инекция, означава, че **съществуват** различни елементи на B, които се изобразяват в един и същи елемент на C. А не че всеки два различни елемента от B имат това свойство. Поради това доказателството трябва да започне от различни елементи на B с това свойство. Грешка е да се започва от a1, a2 \in A, такива че f(a1) \not= f(a2), и после да се твърди, че g(f(a1)) \not= g(f(a2)), понеже g не е инекция; възможно е g(f(a1)) = g(f(a2)).
6) Пак задача 6. Доста решения казват, че
|S4 \cap S6 \cap S15| = floor( 1000 / 360 )
Не е вярно. В знаменателя е НОК(4,6,15) = 60, а не произведението 4*6*15. Аналогично и за други събираеми в израза на вкл/изкл.
Това не е техническа грешка. Това е сериозна грешка, която нулира точките.
7) Няколко решения на зад 1-Б неправилно представят нехом. част като
.. 2^n + ..2^n
като 2^n може да се изнесе пред скоби и да стане ясно, че в нехом. част има само едно събираемо. Тази слабост в записа води до сериозната грешка, че от нехом. част идват три двойки, което напълно разваля решението.
8) В задача 1-А е грешка да се прави инд. предположение за n > 1. По този начин м-вото, от което взема ст-сти n, не съдържа базата като елемент. Има невалидни д-ва по индукция, в която грешката е именно тази. Предположението трябва да е за n >= 1.
9) Няколко решения на задача 5 казват
g o f = g(f(x))
Формално, това е груба грешка. Ако x не е под квантор, това е безсмислица. Ако x е конкретна стойност, пак не става: g o f е множество от наредени двойки, а g(f(x)) е елемент на C. Вярно е, че
\forall x \in A : g o f (x) = g(f(x))
но това е друго нещо.