 Регистрирайте се
| Предишната тема :: Следващата тема |
| Автор |
Съобщение |
krainik
Фен на форума
Регистриран на: 01 May 2009
Мнения: 697
  
гласове: 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
гласове: 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] мухи 
Последната промяна е направена от martosss на Wed Jun 10, 2009 9:02 am; мнението е било променяно общо 2 пъти |
|
| Върнете се в началото |
|
|
krainik
Фен на форума
Регистриран на: 01 May 2009
Мнения: 697
гласове: 44
|
| Пуснато на: Wed Jun 10, 2009 8:44 am Заглавие: |
|
|
| Прав си, че това е отговорът, но не показваш никакво доказателство. |
|
| Върнете се в началото |
|
|
krainik
Фен на форума
Регистриран на: 01 May 2009
Мнения: 697
гласове: 44
|
| Пуснато на: Wed Jun 10, 2009 9:12 am Заглавие: |
|
|
Да, така е  И се пише двоична! Моето решение е почти същото(с малки промени при оформянето)! И това мисля, че е една от разновидностите, за които говореше Баронов в другата тема.
ПП Ако знаеш това свойство - задача става тривиална... Все пак 1999 година това не е било толкова известен факт, колкото сега |
|
| Върнете се в началото |
|
|
martosss
VIP Gold
Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
гласове: 213
|
| Пуснато на: Wed Jun 10, 2009 9:24 am Заглавие: |
|
|
| krainik написа: | | И се пише двоична! |
Да, неграмотник съм  Чудех се дали с о или у и речника е в библиотеката, ама ... мързел...
| krainik написа: | | ПП Ако знаеш това свойство - задача става тривиална... Все пак 1999 година това не е било толкова известен факт, колкото сега |
а) наистина по този начин е лесна, но може ли някакъв хинт за б) и в) и по-точно как да намеря сумата от единиците на двоичните числа от 1 до n 
П.П. Ако не беше Баронов никога нямаше да се сетя |
|
| Върнете се в началото |
|
|
krainik
Фен на форума
Регистриран на: 01 May 2009
Мнения: 697
гласове: 44
|
| Пуснато на: Wed Jun 10, 2009 9:36 am Заглавие: |
|
|
Е, изчакай малко, де  Не са минали и 3 часа, откакто съм я пуснал...
ПП Всъщност, тази функция([tex]f(n)=m[/tex], където [tex]m[/tex] е почивката преди [tex]n[/tex]-тата муха)) е една от първите, които споменахме по информатика тази година( а съм 9 клас  ) |
|
| Върнете се в началото |
|
|
martosss
VIP Gold
Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
гласове: 213
|
| Пуснато на: Wed Jun 10, 2009 10:46 am Заглавие: |
|
|
| krainik написа: | Е, изчакай малко, де Не са минали и 3 часа, откакто съм я пуснал...
ПП Всъщност, тази функция([tex]f(n)=m[/tex], където [tex]m[/tex] е почивката преди [tex]n[/tex]-тата муха)) е една от първите, които споменахме по информатика тази година( а съм 9 клас ) |
Добре, търпеливо чакам(даже мога да помисля сам през това време ). За съжаление нашите г-жи по информатика не са толкова амбициозни(даже никак даже ) и не ни дават задачи с такава трудност(те сега ни дават някакви елементарни, пък какво остава в 9-ти клас, аз съм 11ти ), така че поздравления за желанието им да ви научат на нещо интересно  |
|
| Върнете се в началото |
|
|
krainik
Фен на форума
Регистриран на: 01 May 2009
Мнения: 697
гласове: 44
|
| Пуснато на: Wed Jun 10, 2009 8:44 pm Заглавие: |
|
|
Най-вероятно не си слушал достатъчно по информатика  , защото това е първата програма, която написахме с блок-схеми.
ПП Напиши на ЛС кой ти преподава информатика |
|
| Върнете се в началото |
|
|
|
|
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
Може да прикачвате файлове
Може да сваляте файлове от този форум
|
|
Меню
