0 Потребители и 13 Гости преглежда(т) тази тема.

*

Неактивен gorkia

  • 43
  • Пол: Мъж
Re: Помощ за решения на задачи
« Отговор #140 -: 27.04.2015, 22:29 »
Искам да помоля за решение на следната задача: На колко части се разделя равнината от 21 прави в общо положение?
*

Неактивен Ant12

  • 234
Re: Помощ за решения на задачи
« Отговор #141 -: 27.04.2015, 23:18 »
Светльо, ти ш‘то не спиш по това време?

Отговорът е 232.

Това е стара задача: n прави в общо положение разделят равнината на [n(n + 1)]/2 + 1 региона – крайни или безкрайни.

Получава се сравнително лесно с индукция, или за по-малки частни случаи – с релация за еквивалентност.

Идеята е следната: k + 1 – вата права се разделя от останалите k прави най-много на k + 1 части (2 безкрайни и k - 1 крайни). Тези k + 1 части могат да разделят на две най-много k + 1 от съществуващите до момента региони, т.е. броя на регионите след прекарването на k + 1 – вата права може да се увеличи най-много с k + 1.

p(n + 1) = p(n) + n + 1, където p(n) e броя на регионите, на които n прави разделят равнината.

p(1) = 2; p(2) = 4; p(3) = 7; p(4) = 11, . . .
« Последна редакция: 27.04.2015, 23:37 от Ant12 »

*

Неактивен Ant12

  • 234
Re: Помощ за решения на задачи
« Отговор #142 -: 28.04.2015, 14:43 »
Светльо, ти ш‘то не спиш по това време?

Отговорът е 232.

Това е стара задача: n прави в общо положение разделят равнината на [n(n + 1)]/2 + 1 региона – крайни или безкрайни.

Получава се сравнително лесно с индукция, или за по-малки частни случаи – с рекурентна редица (сега видях, че снощи съм използвал неправилен термин).

Идеята е следната: k + 1 – вата права се разделя от останалите k прави най-много на k + 1 части (2 безкрайни и k - 1 крайни). Тези k + 1 части могат да разделят на две най-много k + 1 от съществуващите до момента региони, т.е. броя на регионите след прекарването на k + 1 – вата права може да се увеличи най-много с k + 1.

p(n + 1) = p(n) + n + 1, където p(n) e броя на регионите, на които n прави разделят равнината.

p(1) = 2; p(2) = 4; p(3) = 7; p(4) = 11, . . .

Надявам се, че така е по-ясно.

В началото имаме една равнина, т.е. един регион.

При построяване на първата права равнината се разделя на 2 полуравнини - броя на регионите се увеличава с един.

При построяване на втората права равнината се разделя на 4 части – втората права се разделя от първата на два лъча, всеки от които разделя получените до момента две полуравнини на два региона, общо 4, т.е. броя на регионите се увеличава с два.

При построяване на третата права, първите две прави пресичат третата в две точки и я разделят на една отсечка и два лъча. Отсечката и двата лъча от третата права могат да бъдат обща граница на не повече от два региона едновременно (например, един от едната страна на отсечката/лъча и друг от другата) и следователно при построяването на третата права броя на регионите ще се увеличи с три, като третата права разделя три от съществуващите региони на две.

Ако следваме същата логика, при построяването на k - тата права, начертаните до момента k - 1 прави ще я разделят на два лъча и k – 2 отсечки, които ще разделят k от съществуващите до момента региони на две и по този начин броя на регионите ще се увеличи с k.

В началото имаме една равнина и при начертаване на k-тата права броя на регионите се увеличава с k.

Тогава броя на регионите при последователно начертаване на k прави е:

1 + 1 (първа права) + 2 (втора права) + 3 (трета права) + . . . + k (k-та права) = k(k + 1)/2 + 1.
« Последна редакция: 28.04.2015, 15:23 от Ant12 »

*

Неактивен gorkia

  • 43
  • Пол: Мъж
Re: Помощ за решения на задачи
« Отговор #143 -: 28.04.2015, 18:20 »
Надявам се, че така е по-ясно.

В началото имаме една равнина, т.е. един регион.

При построяване на първата права равнината се разделя на 2 полуравнини - броя на регионите се увеличава с един.

При построяване на втората права равнината се разделя на 4 части – втората права се разделя от първата на два лъча, всеки от които разделя получените до момента две полуравнини на два региона, общо 4, т.е. броя на регионите се увеличава с два.

При построяване на третата права, първите две прави пресичат третата в две точки и я разделят на една отсечка и два лъча. Отсечката и двата лъча от третата права могат да бъдат обща граница на не повече от два региона едновременно (например, един от едната страна на отсечката/лъча и друг от другата) и следователно при построяването на третата права броя на регионите ще се увеличи с три, като третата права разделя три от съществуващите региони на две.

Ако следваме същата логика, при построяването на k - тата права, начертаните до момента k - 1 прави ще я разделят на два лъча и k – 2 отсечки, които ще разделят k от съществуващите до момента региони на две и по този начин броя на регионите ще се увеличи с k.

В началото имаме една равнина и при начертаване на k-тата права броя на регионите се увеличава с k.

Тогава броя на регионите при последователно начертаване на k прави е:

1 + 1 (първа права) + 2 (втора права) + 3 (трета права) + . . . + k (k-та права) = k(k + 1)/2 + 1.

Да, мерси! Аз и първият път го разбрах, но сега ми е по-ясно.

Re: Помощ за решения на задачи
« Отговор #144 -: 11.05.2015, 20:23 »
Моля за помощ с решението на следната задача:
Колко най-много мача могат да се изиграят между 19 отбора (всеки отбор играе с другите най-много по един мач), така че измежду всеки три отбора да има два, които не са играли?

*

Неактивен Ant12

  • 234
Re: Помощ за решения на задачи
« Отговор #145 -: 12.05.2015, 19:34 »
Моля за помощ с решението на следната задача:
Колко най-много мача могат да се изиграят между 19 отбора (всеки отбор играе с другите най-много по един мач), така че измежду всеки три отбора да има два, които не са играли?

Отговорът е 90.

Задачата може да бъде обобщена: между 2n + 1 отбора (n е естествено) могат да се изиграят най-много n(n + 1) мача така, че всеки два отбора да са играли помежду си не повече от веднъж и измежду всеки три отбора да има два, които не са играли помежду си.

Първи начин (с индукция).

При n = 1 имаме 3 = 2.1 + 1 отбора и между тях могат да се изиграят най-много 2 = 1.2 мача така, че да са изпълнени изискванията.

Нека при n = k ≥ 1, между 2k + 1 отбора могат да се изиграят най-много k(k + 1) мача, които изпълняват изискванията.

Разглеждаме 2(k + 1) + 1 = 2k + 3 отбора и нека X и Y са два от тези отбори, които са играли помежду си. Ще наричаме останалите отбори (2k + 1 на брой) група Z.

Всеки отбор от група Z може да е играл или с X или с Y, но не и едновременно с X и Y, защото в противен случай ще имаме три отбора, всеки два от които са играли помежду си.

Следователно отборите от група Z може да са изиграли най-много 2k + 1 мача с някой от отборите X или Y.

Според индуктивното предположение отборите от група Z могат да изиграят помежду си най-много k(k + 1) мача така, че да са изпълнени изискванията.

Тогава измежду 2k + 3 отбора могат да се изиграят най-много k(k + 1) + 2k + 1 + 1 =
= k2 + k + 2k + 2 = k2 + 3k + 2 = (k + 1)(k + 2) мача – последната единица отразява мача между X и Y.

С това индукцията е завършена.

Втори начин (с рекурентна зависимост).

Нека М(2n + 1) е най-големият възможен брой мачове, които 2n + 1 отбора могат да изиграят помежду си така, че да са изпълнени изискванията.

Ясно е, че M(3) = 2.

Разглеждаме два отбора Х и Y, които са играли помежду си и нека останалите  2n – 1 отбора са от група Z. С аналогични на по-горните разсъждения получаваме, че
М(2n + 1) = M(2n – 1) + 2n – 1 + 1 = M(2n – 1) + 2n.

Следователно,
М(2n + 1) = M(2n – 1) + 2n = M(2n – 3) + 2(n – 1) + 2n = . . . =
= M(3) + 2.2 + 2.3 + . . . + 2(n – 1) + 2n = 2.1 + 2.2 + . . . + 2.n =
= 2(1 + 2 + . . . + n) = n(n + 1).

P.S. При 2n отбора могат да се изиграят най-много n2 мача така, че да са изпълнени изискванията. Доказателството е аналогично.

Задачата може да се обобщи така: между N отбора могат да се изиграят най-много
[N/2]×[N + 1/2] мача така, че всеки два отбора да са играли помежду си не повече от веднъж и измежду всеки три отбора да има два, които не са играли помежду си.

С [k] означаваме най-голямото цяло число, не по-голямо от k.

 


« Последна редакция: 12.05.2015, 19:37 от Ant12 »

Re: Помощ за решения на задачи
« Отговор #146 -: 12.05.2015, 23:30 »
Разбрах я !!! Много ви благодаря!!!

*

Неактивен gorkia

  • 43
  • Пол: Мъж
Re: Помощ за решения на задачи
« Отговор #147 -: 23.05.2015, 19:15 »
Може ли помощ за 15та задача на PMWC 2013? Благодаря предварително.

*

Неактивен Ant12

  • 234
Re: Помощ за решения на задачи
« Отговор #148 -: 23.05.2015, 21:47 »
 М = 1 + 1/22 + 1/32 + 1/42 + 1/52 + 1/62 + 1/72 + . . . =

= 1 + 1/32 + 1/52 + 1/72 + . . . + 1/22 + 1/42 + 1/62 + . . . =

= К + 1/22 + 1/42 + 1/62 + . . . = К + 1/(2.1)2 + 1/(2.2)2 + 1/(2.3)2 + . . . =

= К + 1/4 + 1/4.22 + 1/4.32 + . . . = К + 1/4(1 + 1/22 + 1/32 + . . .) =

= К + 1/4М   =>   3/4М = К   =>   М : К = 4 : 3     

*

Неактивен gorkia

  • 43
  • Пол: Мъж
Re: Помощ за решения на задачи
« Отговор #149 -: 23.05.2015, 23:05 »
М = 1 + 1/22 + 1/32 + 1/42 + 1/52 + 1/62 + 1/72 + . . . =

= 1 + 1/32 + 1/52 + 1/72 + . . . + 1/22 + 1/42 + 1/62 + . . . =

= К + 1/22 + 1/42 + 1/62 + . . . = К + 1/(2.1)2 + 1/(2.2)2 + 1/(2.3)2 + . . . =

= К + 1/4 + 1/4.22 + 1/4.32 + . . . = К + 1/4(1 + 1/22 + 1/32 + . . .) =

= К + 1/4М   =>   3/4М = К   =>   М : К = 4 : 3     

Мерси много!

Re: Помощ за решения на задачи
« Отговор #150 -: 30.05.2015, 08:36 »
Може ли помощ за една задача:Куки Монстер има 10чинии.На тях има сътветно 1,2,4,8,16,32,64,128,256,512 кифли.Той може да вземе произволен брой чинии и да изяде от тях по равен брой кифли.Докажете,че не може да изяде всички кифли за 9 хода.

*

Неактивен Ant12

  • 234
Re: Помощ за решения на задачи
« Отговор #151 -: 31.05.2015, 11:29 »
Може ли помощ за една задача:Куки Монстер има 10чинии.На тях има сътветно 1,2,4,8,16,32,64,128,256,512 кифли.Той може да вземе произволен брой чинии и да изяде от тях по равен брой кифли.Докажете,че не може да изяде всички кифли за 9 хода.

Ще решим следната, по-обща задача: Куки има n ≥ 2 чинии, номерирани от 1 до n, като за всяко k = 1, 2, …, n, в чиния k има 2k-1 на брой кифли. За един ход Куки може да избере произволен брой чинии и да изяде от тях по равен брой кифли. Да се докаже, че минималният брой ходове, с които Куки може да изяде всички кифли е равен на n.

Доказателството ще извършим по индукция.

При n = 2, Куки има две чинии, в които има съответно 1 и 2 кифли. След първия ход са възможни следните конфигурации: (1, 2) => (0, 2); (1, 0); (1, 1); (0, 1). Следователно Куки не може да изяде всички кифли с един ход. От друга страна, Куки може да изяде всички кифли с два хода по следния начин: (1, 2) => (0, 1) => (0, 0). Следователно при n = 1 твърдението е изпълнено.

Да допуснем, че за някое n = k ≥ 2, минималният брой ходове, с които Куки може да изяде всички кифли е равен на k. Ще докажем, че при n = k + 1, минималният брой ходове, с които Куки може да изяде всички кифли е равен на k + 1.

Понеже кифлите са краен брой, то съществуват и краен брой последователности от ходове, с които Куки може да изяде всички кифли. Следователно съществуват една или няколко последователности от ходове, при които броят ходове е минимален.

Нека П0 е последователност от минимален брой ходове, с която Куки може да изяде всички кифли.

Понеже 20 + 21 + 22 + . . . + 2k-1 = 2k - 1 < 2k, то в П0 трябва да има поне един ход, при който Куки изяжда някакъв брой кифли (от 1 до 2k) само и единствено от чиния k + 1. В противен случай общият брой кифли в чинии от 1 до k трябва да бъде поне 2k.

Понеже П0 е последователност от минимален брой ходове, то има точно един ход, на който Куки изяжда кифли само и единствено от чиния k + 1. Няколко различни хода, при които Куки изяжда съответно X1, Х2, ..., Хm, m ≥ 2, само от чиния k + 1, могат да бъдат заменени от един ход (на мястото на Xm), при който той изяжда X1 + X2 + . . . + Xm кифли само от чиния k + 1.

Нека П1 е последователността, която се получава от П0 като преместим на последно място хода, при който Куки изяжда кифли само и единствено от чиния номер k + 1 и запазим всички останали ходове като последователност при избор на чиниите и брой изядени кифли. Ясно е, че П1 също е последователност от минимален брой ходове, с която Куки може да изяде всички кифли.

Нека П2 е последователността, която се получава от П1 като запазим всички ходове като последователност при избор на чиниите и брой изядени кифли, но без да се изяждат кифли от чиния k + 1, като всички 2k кифли от чиния k + 1 се изяждат на последния ход. П2 също е последователност от минимален брой ходове, с която Куки може да изяде всички кифли.

Нека П3 е последователността, която се получава от П2 като запазим всички ходове като последователност при избор на чиниите и брой изядени кифли, но премахваме последния ход, на който се изяждат всички 2k кифли от чиния k + 1. П3 е последователност, с която се изяждат всички кифли в чинии от 1 до k и понеже П0, П1 и П2 са последователности от минимален брой ходове, то П3 трябва да бъде последователност от минимален брой ходове, с която се изяждат всички кифли в чинии от 1 до k, защото иначе ще получим противоречие с минималния избор на П0.

Според индукционното предположение П3 се състои от k хода и следователно П0 се състои от k + 1 хода.

С това индукцията е завършена.

При n = 10, минималният брой ходове, с които Куки може да изяде всички кифли е равен на 10.       

Re: Помощ за решения на задачи
« Отговор #152 -: 5.06.2015, 08:54 »
Може ли някой да ни помогне със 7-ма задача от националния кръг на ЕК 2007 година? Благодаря предварително.

*

Неактивен EliG

  • 139
  • Пол: Жена
Re: Помощ за решения на задачи
« Отговор #153 -: 17.06.2015, 18:49 »
Да помоля решението на една задача:

Числата 21000 и 51000 са написани едно до друго в десетичен запис. Колко цифри общо са написани?