а) По опре­де­ле­нию ве­ро­ят­ность успеш­но­го от­ве­та равна от­но­ше­нию числа спо­со­бов вы­бо­ра двух во­про­сов из тех, от­ве­ты на ко­то­рые ему из­вест­ны, к числу спо­со­бов вы­бо­ра двух во­про­сов из 16 вы­не­сен­ных на зачет. Число спо­со­бов вы­бо­ра двух пред­ме­тов из k раз­лич­ных равна би­но­ми­аль­но­му ко­эф­фи­ци­ен­ту   — числу со­че­та­ний из k по 2. Таким об­ра­зом, если уче­ник знает от­ве­ты на p во­про­сов (при­чем по усло­вию ), то ве­ро­ят­ность его успеш­но­го от­ве­та на оба по­став­лен­ных во­про­са равна

зна­чит,

от­ку­да и сле­ду­ет ответ.

б) Этот во­прос не­мно­гим слож­нее преды­ду­ще­го. Од­на­ко в нем име­ет­ся сле­ду­ю­щая пси­хо­ло­ги­че­ская труд­ность: не­ис­ку­шен­но­му уча­ще­му­ся может по­ка­зать­ся оче­вид­ным, что в дан­ных усло­ви­ях уче­ник вы­учил от­ве­ты на по­ло­ви­ну из об­ще­го числа во­про­сов, и так и на­пи­сать в своем ре­ше­нии, со­слав­шись на некую «сим­мет­рию». Од­на­ко это «оче­вид­ное»  — не­вер­но.

Если уче­ник знает от­ве­ты на p во­про­сов, то вы­брать пару во­про­сов, из ко­то­рых ответ на один ему из­ве­стен, а ответ на вто­рой  — нет, он может спо­со­ба­ми. По­это­му

в) Ве­ро­ят­ность того, что он знает один слу­чай­но вы­бран­ный им во­прос, равна Число ва­ри­ан­тов вы­бо­ра им трех во­про­сов, от­ве­ты по край­ней мере на два из ко­то­рых ему из­вест­ны, равно По­это­му усло­вие за­да­чи за­пи­сы­ва­ет­ся не­ра­вен­ством

т. е. (после пре­об­ра­зо­ва­ний)

г) Решим за­да­чу в общем виде. Вна­ча­ле под­счи­та­ем число спо­со­бов раз­бить во­про­сов по n за­ну­ме­ро­ван­ным би­ле­там. По­сколь­ку во­про­сы для пер­во­го би­ле­та можно вы­брать спо­со­ба­ми, для вто­ро­го  — спо­со­ба­ми, и так далее, то общее число ва­ри­ан­тов равно

Пред­по­ло­жим те­перь, что уче­ник знает от­ве­ты на p во­про­сов и най­дем число «удач­ных» для него спо­со­бов рас­пре­де­ле­ния во­про­сов по n би­ле­там (здесь, ко­неч­но, ). Рас­ста­вим вна­ча­ле n во­про­сов из p из­вест­ных по n би­ле­там; это можно сде­лать спо­со­ба­ми. Остав­ши­е­ся n во­про­сов про­из­воль­ным об­ра­зом рас­став­ля­ем по би­ле­там, что можно осу­ще­ствить спо­со­ба­ми. В итоге имеем ва­ри­ан­тов, од­на­ко не­об­хо­ди­мо учесть, что у нас ока­жет­ся би­ле­тов, от­ве­ты на оба во­про­са в каж­дом из ко­то­рых уче­ни­ку из­вест­ны, и такие би­ле­ты мы со­счи­та­ли два­жды. По­это­му число удач­ных ва­ри­ан­тов равно а ис­ко­мая ве­ро­ят­ность есть

Под­ста­вив по­лу­чим ответ.

Ответ: а) 15; б) 6; 10; в) г)

а)  Каж­дая пара про­ти­во­по­лож­ных гра­ней может быть од­но­цвет­ной или раз­но­цвет­ной  — из че­ты­рех ва­ри­ан­тов рас­крас­ки ровно два раз­но­цвет­ных и два од­но­цвет­ных. Зна­чит, ве­ро­ят­ность для одной пары гра­ней равна а для всех трех пар будет

б)  Если у куба число белых гра­ней равно 0, 1, 5, 6, то такая рас­крас­ка всего одна для каж­до­го ко­ли­че­ства гра­ней.

Если белых гра­ней две или че­ты­ре (то есть чер­ных гра­ней две), то есть две такие рас­крас­ки  — грани того цвета, ко­то­ро­го мень­ше, могут быть со­сед­ни­ми или нет.

На­ко­нец, если белых гра­ней три, то либо есть пара про­ти­во­по­лож­ных белых гра­ней (тогда уже не­важ­но, где тре­тья белая грань  — все такие рас­крас­ки оди­на­ко­вы), либо такой пары нет (тогда най­дет­ся вер­ши­на, к ко­то­рой при­мы­ка­ют все три белых грани и такая рас­крас­ка тоже одна)  — итого таких рас­кра­сок тоже две. Всего

ва­ри­ан­тов.

в)  Вто­рой может каж­дым ходом кра­сить грань, про­ти­во­по­лож­ную к толь­ко что по­кра­шен­ной пер­вым, в про­ти­во­по­лож­ный цвет. В итоге все ку­би­ки будут окра­ше­ны оди­на­ко­во (по­след­ней рас­крас­кой, опи­сан­ной в пунк­те б).

г)  За­фик­си­ру­ем по­ло­же­ние куба в про­стран­стве. Те­перь есть 64 рав­но­ве­ро­ят­ных его рас­крас­ки, ко­то­рые груп­пи­ру­ют­ся в 10 групп рас­кра­сок, ко­то­рые счи­та­ют­ся оди­на­ко­вы­ми. Вы­чис­лим число рас­кра­сок в каж­дой груп­пе.

Есть по одной рас­крас­ке, где все кубы чер­ные или все белые.

Можно 6 спо­со­ба­ми вы­брать одну грань для по­крас­ки в белый цвет, а осталь­ные по­кра­сить в чер­ный - по­лу­чит­ся 6 ва­ри­ан­тов с одной белой гра­нью. Ана­ло­гич­но есть 6 ва­ри­ан­тов с одной чер­ной гра­нью.

Есть также три ва­ри­ан­та вы­брать пару про­ти­во­по­лож­ных гра­ней и по­кра­сить ее в белый цвет и по­лу­чить пер­вый тип рас­крас­ки с двумя бе­лы­ми гра­ня­ми. Ана­ло­гич­но есть три ва­ри­ан­та такой же чер­ной рас­крас­ки.

Для каж­до­го та­ко­го вы­бо­ра можно по­кра­сить одну из осталь­ных 4 гра­ней в белый цвет и по­лу­чить пер­вый тип рас­крас­ки с тремя бе­лы­ми гра­ня­ми. Таким об­ра­зом, этих ва­ри­ан­тов

Для вто­рой рас­крас­ки с тремя бе­лы­ми гра­ня­ми есть 8 ва­ри­ан­тов (они опре­де­ля­ют­ся тем, к какой из 8 вер­шин при­ле­га­ют все три белых грани).

Итого мы пе­ре­чис­ли­ли

ва­ри­ан­тов, зна­чит, на остав­ши­е­ся два спо­со­ба рас­крас­ки при­хо­дит­ся ва­ри­ан­та  — по 12 на каж­дый (ясно, что ва­ри­ан­тов с двумя смеж­ны­ми бе­лы­ми гра­ня­ми столь­ко же, сколь­ко с двумя смеж­ны­ми чер­ны­ми).

Те­перь ясны все ве­ро­ят­но­сти по­лу­чить каж­дый из спо­со­бов и мы можем по­счи­тать ве­ро­ят­ность по­лу­чить оди­на­ко­вые спо­со­бы на двух ку­би­ках (про­из­ве­де­ние двух оди­на­ко­вых ве­ро­ят­но­стей), а затем сло­жить их для всех спо­со­бов по­крас­ки. Най­дем

Ответ: а) б) де­сять рас­кра­сок; г)

а)  Рас­смот­рим де­ре­во воз­мож­ных пе­ре­хо­дов из со­сто­я­ния в со­сто­я­ние в те­че­ние пер­вых трех се­кунд (см. рис.). По­сколь­ку все воз­мож­ные из вось­ми ва­ри­ан­тов пе­ре­хо­дов рав­но­ве­ро­ят­ны, то ответ сле­ду­ет из того, что в ниж­ней строч­ке со­сто­я­ние a встре­ча­ет­ся два раза, а каж­дое из со­сто­я­ний b и c  — по три.

б)  Если k  — это число раз, ко­то­рое со­сто­я­ние x встре­ча­ет­ся в ниж­ней строч­ке де­ре­ва воз­мож­ных пе­ре­хо­дов за n се­кунд, то

в)  По­ло­жим для крат­ко­сти за­пи­си Тогда Дей­стви­тель­но, на n-й се­кун­де устрой­ство будет на­хо­дит­ся в со­сто­я­нии x тогда и толь­ко тогда, когда на преды­ду­щей се­кун­де оно на­хо­ди­лось в одном из двух дру­гих со­сто­я­ний (ве­ро­ят­ность чего равна ) из ко­то­рых оно и пе­ре­шло в x (с ве­ро­ят­но­стью ). Оста­лось за­ме­тить, что

по­это­му при

За­ме­ча­ние. Не­труд­но до­ка­зать явную фор­му­лу для ве­ро­ят­но­стей Имен­но

г)  Утвер­жде­ние будет сле­до­вать, к при­ме­ру, из фор­му­лы

и ее ана­ло­гов для ве­ро­ят­но­стей и До­ка­жем при­ве­ден­ную фор­му­лу (до­ка­за­тель­ство двух дру­гих ана­ло­гич­но).

При­пи­шем пе­ре­хо­дам число а пе­ре­хо­дам в об­рат­ном на­прав­ле­нии  —   — число −1. Таким об­ра­зом, по­сле­до­ва­тель­ность пе­ре­хо­дов за n се­кунд ко­ди­ру­ет­ся по­сле­до­ва­тель­но­стью длины n. Пред­по­ло­жим, что в не­ко­то­рой такой по­сле­до­ва­тель­но­сти встре­ча­ют­ся k штук Не­труд­но по­нять, что по­след­нее со­сто­я­ние сов­па­да­ет с пер­вым тогда и толь­ко тогда, когда (mod 3), от­сю­да (mod 3) или (mod 3). Оста­лось за­ме­тить, что ве­ро­ят­ность каж­дой из по­сле­до­ва­тель­но­стей равна а число по­сле­до­ва­тель­но­стей, в ко­то­рых встре­ча­ет­ся k раз, равно

Ответ: а) б) нет.

а)  За­пи­шем усло­вие в виде

и пре­об­ра­зу­ем его Ясно, что Кроме того, от­ку­да и В то же время от­ку­да Итак, Урав­не­ние сво­дит­ся к Ясно, что (при по­лу­чи­лось бы чет­ное зна­че­ние), а тогда и Ответ

б)  Ясно, что мак­си­маль­ное зна­че­ние n до­сти­га­ет­ся при До­ка­жем, что оно равно по ин­дук­ции. База   — вер­ное утвер­жде­ние.

Пе­ре­ход. Пусть тогда

что и тре­бо­ва­лось до­ка­зать.

в)  Ясно, что каж­до­му на­бо­ру t_i (ко­то­рых ровно по­сколь­ку вы­брать t_i можно спо­со­бом не­за­ви­си­мо от дру­гих вы­бо­ров) со­от­вет­ству­ет ровно одно целое число, при­чем оно все­гда от 0 до (см. пункт б). В этом про­ме­жут­ке как раз целых чисел. Оста­лось до­ка­зать, что ни­ка­кие два зна­че­ния N для раз­ных на­бо­ров не сов­па­да­ют. До­пу­стим, они сов­па­ли. Вы­бе­рем мак­си­маль­ный ин­декс i для ко­то­ро­го в пер­вом на­бо­ре t_i от­ли­ча­ет­ся от p_i во вто­ром на­бо­ре. Пусть в пер­вом оно боль­ше.

Тогда уже за счет сла­га­е­мо­го вме­сто сумма в пер­вом на­бо­ре боль­ше суммы во вто­ром на­бо­ре ми­ни­мум на Все боль­шие сла­га­е­мые в сум­мах равны, а мень­шие, даже если во вто­ром на­бо­ре взять мак­си­маль­но воз­мож­ные ко­эф­фи­ци­ен­ты, а в пер­вом нули, ском­пен­си­ру­ют лишь раз­ни­цу

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

г)  Сна­ча­ла най­дем набор такой, что

По до­ка­зан­но­му выше, можно ис­кать числа с конца, вы­би­рая мак­си­маль­но воз­мож­ное t_i, для ко­то­ро­го сумма еще не пре­вос­хо­дит нуж­ной (если вы­брать боль­ше, то сумма будет боль­ше чем надо, а если мень­ше, то даже мак­си­маль­но воз­мож­ные мень­шие сла­га­е­мые не смо­гут этого ском­пен­си­ро­вать).

По­лу­ча­ем по­сле­до­ва­тель­но, при

Те­перь можно уста­но­вить место каж­до­го из чисел в пе­ре­ста­нов­ке. На­при­мер, 1 долж­на сто­ять после 0 (иначе ). Те­перь по­ста­вим двой­ку. Она долж­на сто­ять левее и 1 и 0, чтобы вы­пол­ня­лось Ана­ло­гич­но до­бав­ля­ем осталь­ные числа. По­сле­до­ва­тель­но по­лу­чим

Ком­мен­та­рий. По­сколь­ку все про­из­ве­ден­ные здесь дей­ствия легко ал­го­рит­ми­зи­ру­ют­ся, они пред­став­ля­ют собой один из самых про­стых спо­со­бов ор­га­ни­за­ции пол­но­го пе­ре­бо­ра всех пе­ре­ста­но­вок дан­ных чисел с по­мо­щью ком­пью­те­ра для ре­ше­ния какой-либо за­да­чи о по­ис­ке пе­ре­ста­нов­ки с нуж­ны­ми свой­ства­ми.

Ответ: а) 1; 2; 0; г) 2, 5, 4, 0, 6, 3, 1.