Дискретни структури, Инф, пролет 2019

Задача 5 има прекалено сложно решение за задача от контролно.

Причината е, че въпросите трябваше да бъдат

|S| > 2n+2?, |S| = 2n+2?, |S| < 2n+2

При *тези* въпроси задачата е много лесна и се решава на два реда с принципа на Дирихле: общо сумите са n+n+2 = 2n+2, а възможностите за всяка от тях са само 2n+1, понеже всяка е от {-n,-n+1, .., -1,0,1,2,..., n}.  Ерго, |S| < 2n+2 е истина, другите са лъжа.

При въпроси

|S| > n+2?, |S| = n+2?, |S| < n+2

решение пак има, т.е. задачата е смислена, но става прекалено трудна.  И трите съждения са лъжа.  За > и = решението е тривиално, понеже може M да е запълнена с едно и също число и тогава |S| = 1.  Обаче < се опровергава не с принципа на Дирихле, а конструктивно.  Не виждам проста конструкция, която е подходяща за решение на задача от контролно.  Показаната конструкция работи, но е прекалено времеемка за задача на контролно.

Тази задача на практика ще е още един бонус.  Всеки/всяка, който/която е отбелязал(а), че > и = са лъжа, ще получи макс. брой точки.  Ако има смислени разсъждения за <, ще получи още 5.  Ако е доказал(а) и <, ще получи още 10.

-- ММ