Вероятности: задача от АМИП (2003 AIME II задача 13)

Буболечка тръгва от връх на равностранен триъгълник. При всяко движение тя избира един или друг ъгъл, на който не се намира, и пълзи по стената на триъгълника до него. Вероятността при десетото си движение тя да се озове на първоначалния връх е m/n, където m и n са взаимно несъкратими положителни цели числа, намерете m + n. Това, че m и n са взаимно несъкратими положителни цели числа означава, че тази дроб е положителна и е своята опростена форма. Да помислим върху задачата, имаме равностранен триъгълник с три върха А, В и С, а буболечката ще тръгне, да речем, от върха А. Това тук е буболечката, при всяко движение избира случаен ъгъл от останалите два ъгъла. При първото движение ще отиде или на върха В, или на върха С, а след това, зависи от това дали е там, ако е на върха С, следващото движение е към върха В или върха А. Ако е на върха В, следващото движение ще е към върха А или към върха С. Да помислим за това. Трябва да намерим вероятността при своето десето движение да отиде на върха А. Да помислим какво се случва при всяко движение. Вероятността за движение към върховете при дадено движение. Приемаме, че в тази колона имаме движение 1, имаме връх А, В и С, да помислим за движение 1. Каква е вероятността за придвижване към връх А при движение 1? Е, вече сме на връх А, а е дадено, че насекомото ще отиде на друг ъгъл. Така вероятността за движение към А е 0. Каква е вероятността за върха В? Тя ще бъде 1/2. Каква е вероятността за връх С? Тя също ще бъде 1/2. Половин възможност да дойде тук или тук. Очевидно сборът на всички възможности трябва да 1, защото тя ще направи нещо при това движение. Да помислим за движение 2. Каква е вероятността за връх А сега? Има 1/2 вероятност да сме на връх В. Ако сме на него, има 1/2 вероятност да се върнем обратно на А. Това е 1/2 по 1/2, отнася се само за ситуацията, в която сме на В. Ако сме на С, също има 1/2 вероятност да отидем върху А. Това е 1/2 вероятност да сме върху С по вероятността да отидем на А. 1/2 х 1/2 = 1/4 + 1/2 х 1/2 = 1/2. Каква е вероятността да отидем на В при второто движение? Единственото място, освен В, на което може да отиде при второто движение, е С. Знаем това, защото в края на първото буболечката няма да е на А. Ще бъде на В или на С. Ако буболечката е на В, няма как да отиде на В. Единственият случай е, ако буболечката е на С, вероятността за това е 1/2. Това число тук. Ако буболечката е на С, това е вероятност 1/2, а след това има 1/2 вероятност да отиде на В. Получава се 1/2 по 1/2 = 1/4. Каква е вероятността да иде на С? Логиката е същата. Тя няма да е на върха А след първото движение и има 1/2 вероятност да е върху В; ако е на В има 1/2 вероятност да отиде на С. Това също ще бъде 1/4. Да обобщим като кажем, че при движение N вероятността да е на върха А е вероятността на А. Вероятността да е на върха В е вероятност да се намира на В при движение N. А вероятността на С е вероятността да се придвижи до връх С при движение N. Да помислим за вероятността на всеки от върховете при N+1. За да отидете на А при N+1, трябва да сте на В или С. Не можете да сте на А и да останете на А. Вероятността да отидете на А при N+1 ще е вероятността да сте на В по 1/2 (защото ако сте на В има вероятност 1/2 да отидете на А) + вероятността да сте на С в края на последното си движение по 1/2. Има половин възможност, ако сте на С, да отидете на А. Има половин възможност ако сте на В, да отидете на А. Каква е вероятността да отидете на В? Има два начина да отидете на В. Да започнете от А. Вероятността да сте върху А по 1/2 или вероятността да сте на С. Прибавяме вероятността на С по 1/2. Ако решавате тази задача за ограничено време, не е задължително да минавате през всичко това, искам само да изясня нещата. И накрая, каква е вероятността да сте на С при движение N+1? Това ще е вероятността на А по 1/2 + вероятността на В по 1/2. Надявам се, че това изяснява модела за решаване на задачата. При всички положения А ще бъде средната стойност. В следващото движение А ще бъде средната вероятност на А и С. Можете да видите. Средното на 1/2 и 1/2 е 1/2. Вероятността на В при движение N+1 ще бъде средната вероятност на вероятностите на А и С при последното движение, средното на 0 и 1/2 е 1/4. Същата логика и за С. Средното на 0 и 1/2 е 1/4. Това ще ми помогне да опростя нещата още малко. Да продължим по този начин, ще допълня колоната. Редовете А, В и С Сега сме на движение 3. Трябва да продължа надолу. Каква е вероятността да сме на А при движение 3? Казахме, че това е средното на В и С, а В и С са 1/4. Средното на 1/4 и 1/4 ще бъде 1/4. Каква е вероятността да сме на В? Средното на А и С при движение 2 е 1/2 и 1/4, това е равно на средното на 4/8 и 2/8, това е 3/8. Ще получим същата стойност за С. Мисля, че е 3/8. Друг модел тук е, че В и С винаги ще са равни и тъй като В и С винаги са равни, средното ще бъде тази стойност и това ще е вероятността да отидете на А при следващото движение. Да продължим. Можем да стигнем до 10, но може би ще видим някакъв модел. Каква е вероятността за А при движение 4? Кое е средното на В и С? Това е 3/8. Можем да вземем тази стойност, каква е вероятността да сме на В? Това ще е средното на А и С, това е 4/16 + 6/16 = 10/16, ще разделим на 2, което прави 5/16. Прав ли съм? Ще го сметна в ъгъла. Не искам да сгреша от бързина. 1/4 е 4/16 + 6/16, след това разделяме на 2. Взимаме средното. 10/16 делено на 2 е равно на 5/16. Ще изчистя това, за да не хабя пространство. Ок, Това ще бъде 5/16, защото е средното на 3/8 и 1/4, затова е 5/16. Сега сме на движение 5. Мога да продължа така до 10, но се надявам да намерим някакъв модел. Движение 5, вероятността да отидем на А ще бъде 5/16, средното на тези двете, 5/16. Вероятността да идем на В (вече виждаме модела) изглежда, че минахме през 2,4,8 в знаменателя до 16. Предполагам, че ще получим 32 в знаменателя. Ще вземем средното на 10/32 и 12/32, това е 11/32. Това ще бъде 11/32. Движение 6. Ще бъде 11/32 (моделът се задържа), това ще е нещо върху 64, това ще е средното, ако умножите това по 4, получавате 20 това е 20/64, а това е 22/64, средното ще бъде 21. Можем да продължим тази екстраполация и да изчислим за 7, 8, 9 и10. Направете го сами, ако ви е интересно, надявам се да получите правилен отговор. Но да видим модела. Това също ще е 21/64, за А движение 7 е лесно. Средното на тези двете, 21/64. Но да видим дали се оформя модел. Изглежда все едно (помнете, че търсим вероятността за преместването върху А на 10-тото движение) ако гледате А, започвате със знаменателя. Това е 2 за движението минус 1, 1/2 за движението минус 1. Изглежда винаги се приближава с 1/2 към 0. Това е 1/2 към 1 и имате 1/2 на квадрат, това е с 1 по-малко от 3 1/2 към 1/3. Да превъртим до N-тото движение, или още по-добре, към 10-тото движение. 7, 8 , 9 и 10. Тук няма много математика. Но да го намерим. 7, 8, 9, 10, това ще е 16, 32, 64, това ще е 128, ако продължим с този модел. Това ще е 256, а тази редица ще е 512. Така намерихме частта N. Да видим можем ли да намерим модел за числителите. Преминахме от 1 на 3 на 5. Да видим, 5 е 3 + 2, не 1. Имате 5, изглежда все едно взимате 2 пъти това и прибавяте това, 2 пъти 1 + 3 е 5, 2 пъти 3 + 5 е 11, 2 пъти 5 + 11 е 21. Да продължим. 2 пъти 11 е 22 + 21 = 43, след това 2 пъти 21 е 42 + 43 = 85, след това 86 + 85, 85 по 2 е 170, така че 171. Ако вярваме на това, което направихме, то нашият отговор е m + n = 171+512 Което е, да видим, ще съберем 2 + 1 = 3, 1 плюс, това става 10 и получаваме 703. Момент, сгреших при събирането, ще го направя пак. 1 + 7 е 8, не 10. Не знам защо си мислех така, а след това 5 + 1 е 6. Получаваме отговора 683. Това е m + n и вероятността при 10-тото движение на отидем на връх А е 171/512. Можете да се убедите сами. Можем да докажем, ако ни е интересно, че всеки следващ елемент е равен на предишния, плюс 2 пъти по-предишния елемент. Всъщност, нека да го докажем. Да кажем, че това е N-тия елемент. Вероятността да сме на А е А/2^n. И това, което получаваме, е вероятността да сме на В и С, да я наречем В. Тази степен винаги е степен на 2-ката, по-висока с 1. 2^n + 1, това ще е същата вероятност като 2/n+1. Тогава при елемента n+1 вероятността за А ще бъде средното на тези двете, което ще бъде В по 2 към N+1, а вероятността да сме, това е В, това е С, това е А, Вероятността да сме на В ще бъде средното на 2А/2^(n+1) (само умножих числителя и знаменателя по 2) + В/2^(n+1) и всичко това върху 2. Ще разделим цялото на 2 стойността за С ще бъде същата. Ако използваме малко математика ще получим [2A + B]/[2^(n+2)] При движението n+2 стойността за А ще бъде тази. Средното на тези двете, което ще бъде точно [2A+B] / [2^(n+2)] Това доказва модела, който открихме. Степените на 2 нарастват с преминаването през елементите. Този елемент е равен на 2 пъти предишния елемент. 2А+В. Използвахме този модел и можем да сме сигурни в своя отговор!