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

Ответ:

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

Ответ: ниже при­ве­ден при­мер од­но­го из воз­мож­ных ре­ше­ний:

«ини­ци­а­ли­за­ция» ре­зуль­та­та;

за­ме­на пер­вых двух еди­ниц одной;

сти­ра­ние оче­ред­ной еди­ни­цы числа;

сти­ра­ние сле­ду­ю­щей за оче­ред­ной еди­ни­цы числа;

поиск конца ре­зуль­та­та;

и до­бав­ле­ние;

еди­ни­цы в его конце;

поиск оче­ред­ной еди­ни­цы за­дан­но­го числа;

и по­вто­ре­ние опе­ра­ции двух еди­ниц числа еди­ни­цей ре­зуль­та­та;

за­вер­ше­ние ра­бо­ты;

через про­пуск стер­тых сим­во­лов;

и оста­нов­кой;

на пер­вой еди­ни­це ре­зуль­та­та;

в слу­чае чётного числа еди­ниц;

то же для нечётного числа еди­ниц.

Функ­ция XOR поз­во­ля­ет легко от­де­лить чётное число еди­ниц на входе от нечётного. Так схема, со­от­вет­ству­ю­щая ло­ги­че­ско­му вы­ра­же­нию хXORyXORzXORu (Легко про­ве­рить, что по­ря­док вы­пол­не­ния опе­ра­ций может быть любым, по­это­му ско­бок можно не ста­вить) даёт на выход 1, если число еди­ниц на входе нечётно, то есть одна или три. От­ри­ца­ние этого вы­ра­же­ния даёт на вы­хо­де 1, если на входе число еди­ниц  — 0, 2 или 4. Эти слу­чаи можно учесть если до­ба­вить (с по­мо­щью опе­ра­ции AND) усло­вия хORyORzORu и

Ответ: один из ва­ри­ан­тов, ис­поль­зу­ю­щий 12 ло­ги­че­ских эле­мен­тов: (xXORyXORzXORu) AND (xORyORzORu) AND NOT (xANDyANDzANDu).

За ос­но­ву можно взять граф ико­са­эд­ра. Раз­лич­ных ре­ше­ний бес­ко­неч­но много.

Ответ: смот­реть ри­су­нок.

Усло­вие можно пе­ре­фор­му­ли­ро­вать так: «Если на поле стоит фи­гу­ра, то найдётся фи­гу­ра, сто­я­щая левее или пра­вее её, но не ниже и не выше».

Ответ: в фор­маль­ной за­пи­си: ДЛЯ ВСЕХ х СУ­ЩЕ­СТВУ­ЕТ у ТАКОЙ, ЧТО (((х левее у) ИЛИ (у левее х)) И (НЕ ВЕРНО, ЧТО (х выше y) И (HE BEPHO, ЧTO (у выше x)).

За­ме­тим, что по ин­дук­ции легко до­ка­зать, что в любом де­ре­ве число вер­шин на 1 боль­ше числа рёбер (на­чи­ная с одной вер­ши­не, до­бав­ля­ем по од­но­му ребру  — при этом до­бав­ля­ет­ся по одной вер­ши­не и по од­но­му ребру): Если сум­ми­ро­вать число рёбер, вхо­дя­щих в каж­дую вер­ши­ну (сте­пе­ни вер­шин), то по­лу­чит­ся число вдвое боль­ше числа рёбер, так как каж­дое ребро со­еди­ня­ет две вер­ши­ны:

Таким об­ра­зом, для пяти вер­шин сумма сте­пе­ней будет равна 2 · 4  =  8. Рас­смот­рим все раз­ло­же­ния числа 8 в сумму пяти сла­га­е­мых и со­от­вет­ству­ю­щие де­ре­вья:

Ответ: не­труд­но ви­деть, что каж­до­му раз­ло­же­нию со­от­вет­ству­ет ровно одно де­ре­во. Все дру­гие можно по­лу­чить пе­ре­ме­ще­ни­ем вер­шин из этих трёх (изо­морф­ны), в то же время ни какие два из этих трёх де­ре­вьев не изо­морф­ны, так как от­ли­ча­ют­ся сте­пе­ня­ми вер­шин.

За­ме­ча­ние. Более длин­ный ответ

об­ла­да­ет тем не менее одним за­ме­ча­тель­ным свой­ством  — каж­дая це­поч­ка в нём учи­ты­ва­ет­ся ровно один раз.

Ответ:

Дви­га­ясь слева на­пра­во, меняя нули на еди­ни­цы, а еди­ни­цы на нули (ин­вер­ти­руя сим­во­лы), до тех пор пока они че­ре­ду­ют­ся таким об­ра­зом. Если это пра­ви­ло не со­блю­да­ет­ся, идём в об­рат­ном на­прав­ле­ния ин­вер­ти­руя эле­мен­ты по­втор­но.

Ответ:

ин­вер­ти­ро­ва­ние;

эле­мен­тов по­сле­до­ва­тель­но­сти;

фик­са­ция на­ру­ше­ния нуж­но­го;

че­ре­до­ва­ния со­сто­я­ни­ем q2;

дви­же­ние об­рат­но;

с по­втор­ным ин­вер­ти­ро­ва­ни­ем;

оста­нов­ка вы­пол­не­ния;

для раз­ных слу­ча­ев;

не обя­за­тель­но на на­чаль­ном сим­во­ле.

Можно пе­ре­брать все пары вхо­дов на ко­то­рые по­да­ют­ся еди­ни­цы, со­еди­нив их опе­ра­ци­ей AND а сами пары  — опе­ра­ци­ей OR.

Ответ: xANDy OR xANDz OR xANDu OR yANDz OR yANDu OR zANDu (11 эле­мен­тов) можно умень­шить число ло­ги­че­ских эле­мен­тов xAND(yORzORu) OR yAND(zORu) OR zANDu (8 эле­мен­тов).

Ответ: смот­реть ри­су­нок.

Усло­вие можно пе­ре­фор­му­ли­ро­вать так: «Если на поле стоит фи­гу­ра, то найдётся фи­гу­ра, сто­я­щая выше или ниже её, но не левее и не пра­вее».

Ответ: в фор­маль­ной за­пи­си: ДЛЯ ВСЕХ х СУ­ЩЕ­СТВУ­ЕТ у ТАКОЙ, ЧТО (((х выше у) ИЛИ (у выше х)) И (НЕ ВЕРНО, ЧТО (х левее у) И (НЕ ВЕРНО, ЧТО (у левее х)).

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

Вот, на­при­мер, ри­су­нок со стра­нич­ки, где эти числа об­суж­да­ют­ся:

Если ли­стья про­ну­ме­ро­вать: L1, L2, ..., Ln, то опи­са­ние раз­лич­ных де­ре­вьев можно опи­сать с по­мо­щью ско­бок, опи­сы­ва­ю­щих, какие ли­стья и ветки со­еди­не­ны. На­при­мер, де­ре­вьям на кар­тин­ке со­от­вет­ству­ют такие ско­боч­ные фор­му­лы (для крат­ко­сти за­пи­си буква L опу­ще­на):

Эта идея поз­во­ля­ет на­пи­сать фор­му­лу для чисел Ка­та­ла­на:

где   — число би­нар­ных де­ре­вьев на вер­ши­нах. В преды­ду­щем при­ме­ре фор­му­ла вы­гля­дит так:

и может быть про­чи­та­но сле­ду­ю­щим об­ра­зом. От корня идут две ветви  — левая и пра­вая. Рас­пре­де­ле­ние ли­стьев между этими вет­вя­ми может быть таким: 1 + 3, 2 + 2, 3 + 1. По­сколь­ку ком­би­на­ции на каж­дой ветви не за­ви­сят от ком­би­на­ций на дру­гой, при­ме­ня­ем прин­цип умно­же­ния. По­сле­до­ва­тель­но по по­лу­чен­ной ре­кур­рент­ной фор­му­ле можно вы­чис­лить: В нашей за­да­че из корня вы­хо­дит три ветви, каж­дая из ко­то­рых уже яв­ля­ет­ся би­нар­ным де­ре­вом, по­это­му нужно рас­смот­реть рас­пре­де­ле­ние ли­стьев между тремя вет­ка­ми и далее уже при­ме­нить фор­му­лу для чисел Ка­та­ла­на:

Таких ва­ри­ан­тов 10 и их тоже можно раз­де­лить на три груп­пы:

а)  три ва­ри­ан­та со сла­га­е­мы­ми

б)  шесть ва­ри­ан­тов со сла­га­е­мы­ми

в)  один ва­ри­ант со сла­га­е­мы­ми

Таким об­ра­зом, ре­зуль­тат вы­чис­ля­ет­ся по фор­му­ле:

Ответ: 28.

Когда мы ко­пи­ру­ем стро­ку, нам важно по­ни­мать, какие эле­мен­ты мы уже ско­пи­ро­ва­ли, а какие ещё нет. По­это­му уже ско­пи­ро­ван­ные еди­ни­цы мы будем «по­ме­чать» ис­поль­зуя для этого вспо­мо­га­тель­ный сим­вол 2.

Как ра­бо­та­ет наша ма­ши­на:

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

б)  Так   — эти пра­ви­ла от­ве­ча­ют за дви­же­ние управ­ля­ю­ще­го эле­мен­та на­пра­во до вто­рой встре­чен­ной звез­доч­ки (когда мы встре­ча­ем первую звез­доч­ку, это от­ме­ча­ет­ся пе­ре­хо­дом из со­сто­я­ния q1 в со­сто­я­ние q2.

в)  Так   — мы на­хо­дим вто­рую звёздоч­ку, за­ме­ня­ем её на еди­ни­цу и на­чи­на­ем дви­же­ние на­ле­во.

г)  Так   — ана­ло­гич­но преды­ду­щей груп­пе пра­вил, дви­жем­ся на­ле­во до тех пор, пока не встре­тим двой­ку. Встре­тив двой­ку, мы воз­вра­ща­ем­ся в на­чаль­ное со­сто­я­ние s и на­чи­на­ем ис­кать сле­ду­ю­щую еди­ни­цу. Если мы её нашли, мы воз­вра­ща­ем­ся об­рат­но к пер­во­му пра­ви­лу и по­вто­ря­ем про­цесс за­но­во. Если сле­ду­ю­щая еди­ни­ца не об­на­ру­же­на, вы­пол­ня­ет­ся пра­ви­ло   — про­цесс ко­пи­ро­ва­ния окон­чен, но все ис­ход­ные еди­ни­цы у нас за­ме­не­ны двой­ка­ми, и надо вер­нуть их в ис­ход­ное со­сто­я­ние. Это де­ла­ет­ся при по­мо­щи пра­ви­ла На­ко­нец, когда мы в со­сто­я­нии встре­ча­ем звёздоч­ку, пра­ви­ло го­во­рит нам за­кон­чить ра­бо­ту.

Ответ: см. рис.

Если слово не удо­вле­тво­ря­ет ре­гу­ляр­но­му вы­ра­же­ние (ab)^*, т. е. не имеет вид это зна­чит, что или это слово на­чи­на­ет­ся на b, или за­кан­чи­ва­ет­ся на a, или со­дер­жит две оди­на­ко­вые буквы под­ряд. За пер­вый слу­чай от­ве­ча­ет пер­вое сла­га­е­мое в фор­му­ле, за вто­рой  — вто­рое, за тре­тий  — тре­тье.

Ответ: см. рис.

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

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

Пусть у них те­перь не сов­па­да­ет пер­вая скоб­ка, т. е. у од­но­го из них пер­вый мно­жи­тель это а, а у вто­ро­го аb. Это ав­то­ма­ти­че­ски опре­де­ля­ет вто­рую скоб­ку в пер­вом ва­ри­ан­те: долж­но по­лу­чать­ся b. Зна­че­ние тре­тьей скоб­ки в пер­вом ва­ри­ан­те обя­за­тель­но на­чи­на­ет­ся с а, что ав­то­ма­ти­че­ские опре­де­ля­ет зна­че­ние вто­рой скоб­ки во вто­ром ва­ри­ан­те: это ab.

Далее за­ме­ча­ем, что чтобы два спо­со­ба рас­кры­тия ско­бок за­да­ва­ли одно слово, не­об­хо­ди­мо, в этих спо­со­бах оди­на­ко­вое ко­ли­че­ство ско­бок рас­кры­ва­лось «ко­рот­ким» спо­со­бом, как а или b и оди­на­ко­вое ко­ли­че­ство «длин­ным» спо­со­бом, как ab. По­сколь­ку в пер­вом ва­ри­ан­те уже две скоб­ки рас­кры­ты «ко­рот­ким» спо­со­бом, а во вто­ром  — «длин­ным», а пятая скоб­ка долж­на рас­кры­вать­ся оди­на­ко­во, это ав­то­ма­ти­че­ски опре­де­ля­ет зна­че­ния тре­тей и четвёртой ско­бок в обоих ва­ри­ан­тах: ab и abаb. Таким об­ра­зом, мы по­лу­ча­ем два слова, за­да­ю­щи­е­ся двумя спо­со­ба­ми: это abababab и abababa.

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

Зна­чит, толь­ко два слова за­да­ют­ся двумя спо­со­ба­ми, осталь­ные одним. Таким об­ра­зом, ответ в этой за­да­че

Ответ: 30.

Возьмём за ос­но­ву пред­ло­жен­ный в на­чаль­ном ре­ше­нии ав­то­мат. Когда он за­кан­чи­ва­ет ра­бо­ту в со­сто­я­нии S0 это зна­чит, что стро­ка рас­по­зна­лась, а когда в S1  — что не рас­по­зна­лась. Нам же сей­час нужно сде­лать всё на­о­бо­рот, по­это­му S0 пе­ре­стаёт быть ко­неч­ным со­сто­я­ни­ем, зато им ста­но­вит­ся S1.

Кроме того, ис­ход­ный ав­то­мат во­об­ще не об­ра­ба­ты­вал слова, к ко­то­рых буквы а и b не че­ре­до­ва­лись. Те­перь нам нужны эти слова, по­это­му надо до­ба­вить их об­ра­бот­ку. Как толь­ко мы в со­сто­я­нии S0 встре­ча­ем букву b или в со­сто­я­нии S1 букву а, это сразу озна­ча­ет, что нам встре­ти­лось нуж­ное слово вне за­ви­си­мо­сти от того, что будет даль­ше. По­это­му в этом слу­чае мы пе­ре­хо­дим в ко­неч­ное со­сто­я­ние S2, ко­то­рое уже не по­ки­да­ем.

Ответ: см. рис.

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

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

Ответ: ми­ни­маль­ное не­об­хо­ди­мое ко­ли­че­ство уче­ни­ков равно 4.

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

Ответ: см. рис.

На ри­сун­ке при­ве­де­на пол­ная схема тур­ни­ра для 6 че­ло­век. Легко по­счи­тать, что в ней 9 рёбер, т. е. до­ба­вить надо 4 ребра.

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

В ис­ход­ном графе n  — 1 ребро. Ко­ли­че­ство рёбер в пол­ном дву­доль­ном графе вы­чис­ля­ет­ся как про­из­ве­де­ние ко­ли­че­ства вер­шин в одной доле (людей в одной ко­ман­де) на ко­ли­че­ство вер­шин в дру­гой доле (людей в дру­гой ко­ман­де). Для слу­чая чётного n в со­от­вет­ству­ю­щем пол­ном дву­доль­ном графе рёбер, зна­чит, до­ба­вить не­об­хо­ди­мо ребро, что можно также пред­ста­вить как В слу­чае нечётного n ито­го­вое ко­ли­че­ство рёбер это до­ба­вить не­об­хо­ди­мо ребро, что также можно пред­ста­вить как

Ответ: при чет­ном n: при не­чет­ном n:

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

Самое за­мет­ное от­ли­чие между кар­тин­ка­ми - на­ли­чие на левой кар­тин­ке блока из не­сколь­ких (боль­ше одной) синих вер­шин, не со­единённых с крас­ны­ми) ко­то­ро­го нет на пра­вой. Вы­ска­зы­ва­ние «Для любой синей вер­ши­ны су­ще­ству­ет крас­ный сосед» не про­хо­дит, так как оди­но­кая синяя вер­ши­на на левой кар­тин­ке всё же есть. А вот вы­ска­зы­ва­ние «Для любых двух со­сед­них синих вер­шин есть общая со­сед­няя крас­ная»  — как раз то, что нам нужно.

Ответ: см. рис.