Дадено е множество A съставено от n ненулеви вектора

[luboslav_p]

Дадено е множество A съставено от n ненулеви вектора. За едно множество U от вектори с d(U) ще означаваме дължината на вектора, който е сума на всички вектори в U. Едно подмножество B на A наричаме максимално, когато d(B)≥d(C) за всяко C подмножество на A.
1) За n= 4,5 да се покаже, че броят максимални подмножества може да бъде равен съответно на 8 и 10.
2) Да се докаже, че за всяко n този брой не надминава 2n.

[Реклама]

[krassi_holmz]

1.
n=4
Разглеждаме равностранен триъгълник ABC. Нека D е втората пресечна точка на височината от C и описаната около триъгълника окръжност. Тогава векторите AC, CB, BD и DA имат 8 максимални подмножества (фиг. 1). Това е така, защото всяка от зелените отсечки е максимална и маже да се получи по два начина като сума от някои вектори.

n=5
Oтново разглеждаме равностранен триъгълник ABC и две точки, разделящи дъгата AB от описаната около триъгълника окръжност на 3 равни части. Така получаваме конфигурация от 5 вектора с 10 максимални подмножества (зелените отсечки могат да се получат по два начина) (фиг. 2). Аналогична конструкция може да се приложи и за n точки.


2. Нека разположим V-те вектора в началото на координатна система.
Ще докажем следната лема:
Нека U е максимално множество и нека S е сумата на векторите от U. Нека p е полуравнина с ръб, преминаващ през центъра на координатната система и успореден на S. Тогава U съдържа точно тези вектори, които са изцяло в p.
Да допуснем противното. Ако съществува вектор в полуравнината извън U, то добавянето му към U води до по-голяма дължина, и оттук U не е максимално подмножество. Ако пък някой вектор е в U, но не лежи изцяло в полуравнината, изваждането му от U ще ни даде множество с по-голяма сумарна дължина, което е противоречие. (фиг. 3).



Сега, взимаме произволна полуравнина през началото на координатната система и започваме да я "въртим" около началото (това е известно като sweep line). Лемата ни казва, че в най-добрия случай, можем да имаме максимум броя на пресичанията на полуравнината с някой вектор максимални подмножества, докато полуравнината извършва пълно завъртане. Можем да разглеждаме полуравнината като два лъча, всеки от които изминава пълен оборот, т.е. преминава през всичките n вектора по веднъж, следователно браят на максималните подмножества не надминава 2n.