Регистрирайте сеРегистрирайте се

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


 
   Форум за математика Форуми -> Олимпиади и състезания за 9-12 клас
Предишната тема :: Следващата тема  
Автор Съобщение
luboslav_p
Начинаещ


Регистриран на: 16 Feb 2008
Мнения: 33
Местожителство: София
Репутация: 12.6
гласове: 7

МнениеПуснато на: Fri May 22, 2009 8:07 pm    Заглавие: Дадено е множество A съставено от n ненулеви вектора

Дадено е множество 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
Редовен


Регистриран на: 05 Jan 2006
Мнения: 146
Местожителство: Ню Йорк, BG
Репутация: 57.9
гласове: 18

МнениеПуснато на: Sun Aug 02, 2009 9:05 pm    Заглавие:

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.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Олимпиади и състезания за 9-12 клас Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
Може да прикачвате файлове
Може да сваляте файлове от този форум
Copyright © 2005-2020 math10.com.