Если шагов всего один, то робот может оста­но­вить­ся в двух по­ло­же­ни­ях, услов­но изоб­ра­жен­ных на ри­сун­ке.

Здесь 0  — на­ча­ло дви­же­ния, −1  — шаг назад, 1  — шаг впе­ред. Ве­ро­ят­ность по­пасть в по­ло­же­ния −1 и 1 оди­на­ко­вая и равна Если шагов два, то су­ще­ству­ет три воз­мож­ных по­ло­же­ния ро­бо­та в конце дви­же­ния, услов­но обо­зна­чен­ных на ри­сун­ке.

В по­ло­же­ние −2 можно по­пасть из по­ло­же­ния −1 после пер­во­го шага, со­вер­шив шаг назад. Таким об­ра­зом, ве­ро­ят­ность по­па­да­ния в по­ло­же­ние −2 за два шага равна В по­ло­же­ние 0 можно по­пасть из по­ло­же­ний −1 и 1 после пер­во­го шага, со­вер­шив шаги впе­ред и назад со­от­вет­ствен­но. Тогда ве­ро­ят­ность по­па­да­ния в по­ло­же­ние 0 после двух шагов равна

В по­ло­же­ние 2 после вто­ро­го шага воз­мож­но по­пасть толь­ко из по­ло­же­ния 1, делая один шаг впе­ред. Ве­ро­ят­ность по­па­да­ния в 2 за два шага равна

Далее об­ра­зо­ва­ние ко­эф­фи­ци­ен­тов при сте­пе­нях опре­де­ля­ет­ся тре­уголь­ни­ком Пас­ка­ля. Пред­по­ло­жим, что робот сде­лал до оста­нов­ки k шагов. Тогда су­ще­ству­ет воз­мож­ных по­ло­же­ний, в ко­то­рых он может оста­но­вить­ся. Край­ние из них на­хо­дят­ся на рас­сто­я­нии k шагов от на­чаль­но­го по­ло­же­ния дви­же­ния. Рас­сто­я­ние между со­сед­ни­ми по­ло­же­ни­я­ми равно двум шагам. На рис. изоб­ра­же­ны эти по­ло­же­ния для чет­ных и не­чет­ных k.

Для ве­ро­ят­ность оста­нов­ки в по­ло­же­нии равна в по­ло­же­нии (на рас­сто­я­нии 2 шага от на­ча­ла дви­же­ния) эта ве­ро­ят­ность равна в по­ло­же­ние (на рас­сто­я­нии 4 шага от на­чаль­но­го по­ло­же­ния) и т. д. в по­ло­же­нии эта ве­ро­ят­ность равна В ва­ри­ан­те Ве­ро­ят­ность оста­но­вит­ся в по­ло­же­нии, от­сто­я­щем от на­чаль­но­го не более двух шагов, равна

а ве­ро­ят­ность про­ти­во­по­лож­но­го со­бы­тия Для ве­ро­ят­ность оста­нов­ки в по­ло­же­нии равна в по­ло­же­нии (на рас­сто­я­нии 3 шага от на­ча­ла дви­же­ния)  — и т. д. оста­нов­ка в по­ло­же­нии про­ис­хо­дит с ве­ро­ят­но­стью

Ответ: