Често срещани грешки в решенията на задачите от изпита
След като съм проверил повече от половината работи (на око), мога да кажа, че тези грешки се срещат повече от веднъж
А) В зад.1, НЕ Е решение да развиете "до долу" и да напишете формула за сумата. Тази формула не е кой знае колко по-бърз алгоритъм за пресмятане на T(n) от рекурсивния алг., който е самото рек. уравнение. В контраст на това, решението n/(2n+1) е изключително бърз алгоритъм.
Б) В зад. 3 (въпреки че става дума за само 1 точка), това, че |Bn| = n! не може да се докаже с просто "има биекция от An в Bn". Да, има биекция, и то много такива, но първо трябва да се докаже съществуването на биекция и чак оттам по принципа на биекция ще следва, че |Bn| = n!.
Пак в зад. 3, An и Bn не са едно и също множество! Ако n=3, то (3,2,1) е една от пермутациите, но тя не е елемент на Bn, понеже на първа позиция има 3. От друга страна, (1,1,1) е един от елементите на Bn, но това не е пермутация на 1,2,3.
В) Зад. 4 е разглеждана на лекции, макар и в общ вид, а не с конкретно 101 и 51. Това е директно прилагане на формулата за броя на сюрекциите. На лекции забелязахме, че следното НЕ Е решение "първо раздаваме 51 билета биективно по 51! начина, за да не остане човек без билет, и после останалите по произволен начин". Това е overcounting, понеже брои едно и също раздаване по няколко пъти.
Г) Зад. 5 е може би най-трудната. П(M) е множеството от всички разбивания, на всякакъв възможен брой дялове от 1 до n. Всяко разбиване е множество ОТ МНОЖЕСТВА, такива че всеки протоелемент е в точно едно от тях. П'(M) тогава е подмножеството на П(M), състоящо се от точно тези разбивания z, за които всеки дял w (w е множество от протоелементи, т.е., върхове) e антиклика, ако мислим за R като за граф. Тогава k е минималният брой дялове на разбиване от П'(M). Тоест, хроматичното число. Ерго, всички решения, казващи, че k е кликовото число на графа или числото на независимост, са грешни.
Д) Зад. 6 е решавана на лекции, но в леко различна формулировка: само с композиция на ф-ята сума-по-модул-2 не може да се направи константа нула или константа единица, ако няма унификация на променливи. Формулировката със съждителна логика не променя нищо по същество. f(\phi) е множеството от простите съждения, съдържащи се в съждението \phi. Ограничението f(\phi) \cap f(\psi) = \emptyset "казва", че \phi и \psi нямат общи прости съждения, което отговаря на "няма унификация на променливи", ако мислим за нещото като за булева функция; или няма "крачета накъсо", ако мислим за нещото като за схема от функц. елементи.
-- ММ