До­ка­жем оцен­ку Пусть су­ще­ству­ет стра­те­гия, поз­во­ля­ю­щая оши­бать­ся не более чем в k битах (т. е. Тогда за­ме­тим, что На­блю­да­тель, зна­ю­щий стра­те­гию Фо­кус­ни­ка, со­об­щен­ное Ас­си­стен­том слово, и набор бит, в ко­то­рых ошиб­ся Фо­кус­ник, может вос­ста­но­вить на­пи­сан­ное Зри­те­лем слово. В самом деле, На­блю­да­тель берет слово, ко­то­рое дол­жен был на­пи­сать Фо­кус­ник, и ме­ня­ет его в тех ме­стах, где Фо­кус­ник ошиб­ся. Зна­чит, ко­ли­че­ство раз­лич­ных пар вида «слово со­об­щен­ное Ас­си­стен­том и набор мест, в ко­то­рых фо­кус­ник ошиб­ся» не мень­ше, чем раз­лич­ных слов, ко­то­рые мог на­пи­сать зри­тель. То есть

Пе­ре­пи­шем в виде

и за­ме­тим, что при не­ра­вен­ство не­вер­но: но

Те­перь по­про­бу­ем по­ка­зать, из каких со­об­ра­же­ний стро­ит­ся при­мер. Для на­ча­ла на­пом­ним кон­струк­цию, из­вест­ную как ма­те­ма­ти­кам так и про­грам­ми­стам: дво­ич­ный код длины 15, поз­во­ля­ю­щий пе­ре­дать 11 бит по­лез­ной ин­фор­ма­ции и ис­пра­вить ошиб­ку не более чем в одном бите (также из­ве­стен как 15-бит­ный код Хэм­мин­га). По­стро­им его.

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

Те­перь по­стро­им код таким об­ра­зом: в пер­вые 11 бит за­пи­шем те биты, ко­то­рые хотим пе­ре­дать (пер­вые 11 по­зи­ций будем на­зы­вать ин­фор­ма­ци­он­ны­ми). В по­след­ние 4 бита за­пи­шем сле­ду­ю­щие кон­троль­ные суммы. В 12-й за­пи­шем сумму по мо­ду­лю два тех из пер­вых 11 бит, при­пи­сан­ное 4-знач­ное число ко­то­рых имеет 1 в пер­вом раз­ря­де, то есть биты №№ 3, 5, 6, 8, 9, 10, 11. В 13-й  — сумму тех из пер­вых 11 бит, при­пи­сан­ное 4-знач­ное число ко­то­рых имеет 1 во вто­ром раз­ря­де, в 14-й сумму бит, име­ю­щих 1 в тре­тьем раз­ря­де при­пи­сан­но­го слова, в 15-й  — в чет­вер­том. По­ка­жем, по­че­му этот код поз­во­ля­ет ис­пра­вить одну ошиб­ку при пе­ре­да­че.

Пусть По­лу­ча­тель по­лу­чил ко­до­вое слово, воз­мож­но ис­ка­жен­ное в одном бите. По­лу­ча­тель точно так же по пер­вым 11 битам по­счи­та­ет 4 кон­троль­ные суммы, и срав­нит их с че­тырь­мя по­лу­чен­ны­ми. Если сов­па­ли все че­ты­ре  — то слово дошло без ис­ка­же­ний. В самом деле, если бы ис­ка­зил­ся кон­троль­ный бит  — в нем было бы рас­хож­де­ние, а если ин­фор­ма­ци­он­ный  — то рас­хож­де­ния были бы во всех кон­троль­ных, в ко­то­рые он вхо­дит. Ана­ло­гич­но, если рас­хож­де­ние есть ровно в одном кон­троль­ном бите, то ис­ка­зил­ся имен­но он. В самом деле, если ис­ка­зил­ся дру­гой кон­троль­ный  — то все ин­фор­ма­ци­он­ные дошли пра­виль­но, тогда в этом кон­троль­ном рас­хож­де­ния бы не было; а если ис­ка­зил­ся ин­фор­ма­ци­он­ный, то все кон­троль­ные дошли пра­виль­но, и тогда рас­хож­де­ния были бы во всех кон­троль­ных, в ко­то­рые вхо­дит ис­ка­жен­ный ин­фор­ма­ци­он­ный, а таких кон­троль­ных хотя бы два (имен­но за этим мы при­пи­сы­ва­ли ком­би­на­ции нулей и еди­ниц, со­дер­жа­щие хотя бы две еди­ни­цы). По ана­ло­гич­ным со­об­ра­же­ни­ям если по­лу­ча­тель видит не менее двух рас­хож­де­ний с кон­троль­ны­ми би­та­ми, то ис­ка­жен точно ин­фор­ма­ци­он­ный. Тогда до­ста­точ­но из 11 ин­фор­ма­ци­он­ных по­зи­ций вы­брать ту, в при­пи­сан­ном 4-бит­ном слове ко­то­рой еди­ни­цы стоят ровно на тех ме­стах, на ко­то­рых есть рас­хож­де­ния с кон­троль­ны­ми сум­ма­ми  — это и есть ис­ка­жен­ная по­зи­ция.

Те­перь по­ду­ма­ем в дру­гих тер­ми­нах, что же мы по­стро­и­ли. У нас есть код из 2¹¹ ко­до­вых слов. Каж­дое из этих слов можно ис­ка­зить 16 спо­со­ба­ми (ни­че­го не ме­нять, или из­ме­нить один из 15 бит). Все по­лу­чен­ных в ре­зуль­та­те слов будут раз­ны­ми. В самом деле, если бы какое-то слово w по­лу­ча­лось двумя раз­ны­ми спо­со­ба­ми: ис­ка­же­ни­ем ко­до­во­го слова u₁ и ис­ка­же­ни­ем ко­до­во­го слова u₂ (в обоих слу­ча­ях  — не более чем в одном бите), то код бы не ис­прав­лял одну ошиб­ку  — По­лу­ча­тель может по­лу­чить слово w, но в этом слу­чае не может по­нять, по­сы­ла­ли ему u₁ или u₂. Итак, все слов раз­ные, но это озна­ча­ет что во­об­ще любое из слов длины 15 по­лу­ча­ет­ся ис­ка­же­ни­ем ка­ко­го-то из ко­до­вых слов не более чем в одном бите.

На этом и по­стро­им стра­те­гию Фо­кус­ни­ка и Ас­си­стен­та. Ас­си­стент видит на­пи­сан­ное зри­те­лем 60-бит­ное слово, режет его на че­ты­ре 15-бит­ных слова w₁, w₂, w₃, w₄. Как до­ка­за­но выше, для них най­дут­ся ко­до­вые слова u₁, u₂, u₃, u₄, такие что w_i от­ли­ча­ет­ся от u_i не более чем в одном сим­во­ле. Тогда Ас­си­стент вы­бра­сы­ва­ет из каж­до­го ко­до­во­го слова кон­троль­ные сим­во­лы, по­лу­ча­ет че­ты­ре слова длины 11, то есть одно слово длины 44. Его он и пе­ре­да­ет Фо­кус­ни­ку. Фо­кус­ник вос­ста­нав­ли­ва­ет кон­троль­ные суммы, по­лу­ча­ет слово u₁u₂u₃u₄ от­ли­ча­ю­ще­е­ся от ис­ход­но­го мак­си­мум в че­ты­рех битах  — по­бе­да.

Ответ: