Често срещани грешки в решенията на изпита-задачи
В няколко работи имаше следната грешка в решението на задача 4. Трудната посока е да се докаже, че всяка положителна монотонно растяща редица със сума 2n-2 е редица от степените на дърво с n върха. Има доказателства, които казват нещо от рода на "нека имаме такава редица с дължина n-1. Добавяме елемент единица в началото, увеличаваме някой елемент с единица и получаваме редица-от-нашите с дължина n". Проблемът е, че няма д-во, че всяка редица-от-нашите с дължина n > 2 се получава от някоя с дължина n-1 по този начин. То е вярно, но, докато не се докаже, това д-во не върви. Това д-во би било със структурна индукция.. Д-вото в решенията на домашно 2 е с обикновена (числена) индукция, при която в индуктивната стъпка тръгваме от произволна редица-от-нашите с дължина n, трием единица (доказали сме, че единица има), намаляваме с единица първата стойност >1 (доказали сме, че такава има) и "влизаме" в индуктивното предположение.
Някои решения на задача 3 (с релациите) са толкова лаконични, че стават неразбираеми за читател, който се формализира и иска всичко да е ясно. На лекции се каза, че отговорите трябва да са с пълни изречения на български.
Нещо подобно има и в отговори на задача 6 за броя на неименуваните дървета със 7 върха. Те са 11 на брой, но не е достатъчно да бъдат нарисувани. Трябва някаква аргументация, че това са всички и други няма.
Някои решения на задача 3 стигат до извода, че "за всяко a \in A : a R a". Това не е вярно. Ако беше вярно, R щеше задължително да е рефлексивна. А тя може и да е. Тази грешка е груба и нулира точките на зад 3.
В задачата с Червената Шапчица целта е да се провери владеенето на принципа на вкл/изкл. Ограниченията обаче са неудачни---мой пропуск---поради което има решение с просто умножение 8*5*8 = 320. Студентите, които са забелязали това и са се възползвали, получават 30 т. на зад 2. Един вид, 10 т. бонус.
В няколко решения на зад 4, в посоката
ако \alpha = (a1 .. an) е редица-от-нашите, то има дърво T, чията редица от степените е \alpha
се дава не решение по индукция като в домашното, а конструктивно решение. Това е алгоритъм, който построява T. За съжаление, всички такива алгоритмични решения, които видях досега, са грешни. Този алгоритъм
Свързваме an със следващите an на брой върхове
После an-1 със следващите an-1 върхове, и т.н
не работи, ако се изпълнява буквално. Помислете за (1,1,1,1,1,3,4). Правейки четворката съсед на следващите четири, "остатъчните степени" стават (1,1,0,0,0,2,0), и сега бившата тройка, която вече е двойка, трябва да стане съсед на двете единици в началото, а не на нулите след себе си.
Алгоритъмът би трябвало да казва: отдясно наляво, всеки връх ai с положителна остатъчна степен се прави съсед на следващите ai върхове, КОИТО ИМАТ ПОЛОЖИТЕЛНА ОСТАТЪЧНА СТЕПЕН. И след това трябва да се докаже коректността на алгоритъма -- че винаги има достатъчно върхове вляво с положителна остатъчна степен. Едва ли ще имате време за това. Така че този подход не е удачен.
В много решения на задача 5 се пише за s(n,k) като за биномен коефициент ен-над-ка. Няма такова нещо. Това не са биномни коефициенти.
Пак в задача 5, някои решения говорят за разделители и позиции. Това е пренесено от лекцията за комбинаторни конфигурации без наредба, с повторения. Това е съвсем друго нещо и води до биномни коефициенти, каквито в задача 5 не се появяват. Следните са различни като редици от два вида елементи:
* | * * | * * *
* | * * * | * *
но са едно и също целочислено разбиване на шестицата, а именно 1 + 2 + 3
Пак за зад 5: няколко отговора казват, че въпросните суми са съизброими с решенията на уравнението
a1 + a2 + ... + ak = n
Това не е вярно. Променливите a1 .. an имат идентичности, а събираемите в задача 5 нямат. С други думи, ако n = 6, тези две решения на уравнението
a1 = 1, a2 = 2, a3 = 3
a1 = 2, a2 = 1, a3 = 3
са РАЗЛИЧНИ. Докато сумите 1+2+3 и 2+1+3 са неразличими. Прочее, това е причината s(n,k) да растат много по-бавно от биномни коефициенти.