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

IMO shortlist 1999


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


Регистриран на: 01 May 2009
Мнения: 697

Репутация: 51.8
гласове: 44

МнениеПуснато на: Wed Jun 10, 2009 7:39 am    Заглавие: IMO shortlist 1999

Един биолог наблюдавал един хамелеон. Хамелеонът ловял мухи и след всяка уловена муха, той почивал.Биологът забелязал, че:
[tex]i)[/tex]Първата муха е хваната след едноминутна почивка.
[tex]ii)[/tex]Почивката преди улавянето на [tex](2m)[/tex]-тата муха е същата като тази преди улавянето на [tex](m)[/tex]-тата и с 1 минута по-кратка от тази преди улавянето на [tex](2m+1)[/tex]-вата.
[tex]iii)[/tex]Веднага след като си почине хамелеона, той хваща друга муха.

[tex]1)[/tex]Колко мухи е уловил хамелеонът, преди да направи първата си 9-минутна почивка?
[tex]2)[/tex]След колко време той ще хване 98-мата си муха?
[tex]3)[/tex]Колко мухи ще бъдат хванати от хамелеона за 2009 минути(оригиналния проблем е с 1999)?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Wed Jun 10, 2009 8:39 am    Заглавие: Re: IMO shortlist 1999

krainik написа:
[tex]1)[/tex]Колко мухи е уловил хамелеонът, преди да направи първата си 9-минутна почивка?

Спомням си, че някой от форума (мисля че беше Баронов) беше предложил модел с представяне на цялата ситуация в двуична бройна система, тоест номерът на всяка муха се представя в двуична бройна система и броят на единиците в този номер указва колко минутна почивка се изисква преди да се хване съответната муха

За целта трябва да се докаже, че условията се изпълняват при този модел:
1) 1-вата муха се представя като [tex]1[/tex], откъдето и почивката преди нейното хващане е 1 мин.
2) При m-та и 2m-та муха имаме равен брой мухи - ако числото m има представяне [tex]\overline{a_1a_2a_3\dots a_n}[/tex], то числото 2m има представяне [tex]\overline{a_1a_2a_3\dots a_n0[/tex], при което сборът от цифрите и в двата случая е [tex]\sum_{1}^{n} a_i[/tex] и е равен.

3) Представянето на 2m+1-вата муха е [tex]\overline{a_1a_2\dots a_n1[/tex], откъдето сумата от цифрите е [tex]\left(\sum_{1}^{n}a_i\right) +1[/tex], тоест нараства с 1, тоест почивката преди хващането ще е с една минута по-голяма.

С това успешно "внедряваме" този модел и сега за решението на задачата ще ни е нужно да намерим най-малкото двуично число с 9 единици(9-минутна почивка), което е 111 111 111 или още 1 000 000 000 -1, тоест [tex]2^9-1[/tex], тоест преди [tex]2^9-1[/tex]-вата муха хамелеонът прави 9-минутна почивка. Но дотогава той е хванал точно [tex]2^9-2=510[/tex] мухи Smile


Последната промяна е направена от martosss на Wed Jun 10, 2009 9:02 am; мнението е било променяно общо 2 пъти
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
krainik
Фен на форума


Регистриран на: 01 May 2009
Мнения: 697

Репутация: 51.8
гласове: 44

МнениеПуснато на: Wed Jun 10, 2009 8:44 am    Заглавие:

Прав си, че това е отговорът, но не показваш никакво доказателство.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
krainik
Фен на форума


Регистриран на: 01 May 2009
Мнения: 697

Репутация: 51.8
гласове: 44

МнениеПуснато на: Wed Jun 10, 2009 9:12 am    Заглавие:

Да, така е Wink И се пише двоична! Моето решение е почти същото(с малки промени при оформянето)! И това мисля, че е една от разновидностите, за които говореше Баронов в другата тема.
ПП Ако знаеш това свойство - задача става тривиална... Все пак 1999 година това не е било толкова известен факт, колкото сега Wink
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Wed Jun 10, 2009 9:24 am    Заглавие:

krainik написа:
И се пише двоична!
Да, неграмотник съм Embarassed Чудех се дали с о или у и речника е в библиотеката, ама ... мързел...

krainik написа:
ПП Ако знаеш това свойство - задача става тривиална... Все пак 1999 година това не е било толкова известен факт, колкото сега Wink
а) наистина по този начин е лесна, но може ли някакъв хинт за б) и в) и по-точно как да намеря сумата от единиците на двоичните числа от 1 до n Confused
П.П. Ако не беше Баронов никога нямаше да се сетя Smile
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
krainik
Фен на форума


Регистриран на: 01 May 2009
Мнения: 697

Репутация: 51.8
гласове: 44

МнениеПуснато на: Wed Jun 10, 2009 9:36 am    Заглавие:

Е, изчакай малко, де Laughing Не са минали и 3 часа, откакто съм я пуснал...
ПП Всъщност, тази функция([tex]f(n)=m[/tex], където [tex]m[/tex] е почивката преди [tex]n[/tex]-тата муха)) е една от първите, които споменахме по информатика тази година( а съм 9 клас Cool )
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Wed Jun 10, 2009 10:46 am    Заглавие:

krainik написа:
Е, изчакай малко, де Laughing Не са минали и 3 часа, откакто съм я пуснал...
ПП Всъщност, тази функция([tex]f(n)=m[/tex], където [tex]m[/tex] е почивката преди [tex]n[/tex]-тата муха)) е една от първите, които споменахме по информатика тази година( а съм 9 клас Cool )
Добре, търпеливо чакам(даже мога да помисля сам през това време Smile ). За съжаление нашите г-жи по информатика не са толкова амбициозни(даже никак даже Laughing ) и не ни дават задачи с такава трудност(те сега ни дават някакви елементарни, пък какво остава в 9-ти клас, аз съм 11ти Wink ), така че поздравления за желанието им да ви научат на нещо интересно Exclamation
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
krainik
Фен на форума


Регистриран на: 01 May 2009
Мнения: 697

Репутация: 51.8
гласове: 44

МнениеПуснато на: Wed Jun 10, 2009 8:44 pm    Заглавие:

Най-вероятно не си слушал достатъчно по информатика Razz , защото това е първата програма, която написахме с блок-схеми.
ПП Напиши на ЛС кой ти преподава информатика Wink
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Олимпиади и състезания за 9-12 клас Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

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