Два иг­ро­ка, Петя и Ваня иг­ра­ют в сле­ду­ю­щую игру. На столе в кучке лежат фишки. На ли­це­вой сто­ро­не каж­дой фишки на­пи­са­но дву­знач­ное на­ту­раль­ное число, обе цифры ко­то­ро­го на­хо­дят­ся в диа­па­зо­не от 1 до 4. Ни­ка­кие две фишки не по­вто­ря­ют­ся. Игра со­сто­ит в том, что иг­ро­ки по­оче­ред­но берут из кучки по одной фишке и вы­кла­ды­ва­ют в це­поч­ку на стол ли­це­вой сто­ро­ной вверх таким об­ра­зом, что каж­дая новая фишка ста­вит­ся пра­вее преды­ду­щей и бли­жай­шие цифры со­сед­них фишек сов­па­да­ют. Верх­няя часть всех вы­ло­жен­ных фишек на­прав­ле­на в одну сто­ро­ну, то есть пе­ре­во­ра­чи­вать фишки нель­зя. На­при­мер, из фишки, на ко­то­рой на­пи­са­но 23, нель­зя сде­лать фишку, на ко­то­рой на­пи­са­но 32. Пер­вый ход де­ла­ет Петя, вы­кла­ды­вая на стол любую фишку из кучки. Игра за­кан­чи­ва­ет­ся, когда в кучке нет ни одной фишки, ко­то­рую можно до­ба­вить в це­поч­ку. Тот, кто до­ба­вил в це­поч­ку по­след­нюю фишку, вы­иг­ры­ва­ет, а его про­тив­ник про­иг­ры­ва­ет.

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

При­мер пар­тии.

Пусть на столе в кучке лежат фишки: 11, 12, 13, 21, 22, 23.

Пусть пер­вый ход Пети 12.

Ваня может по­ста­вить 21, 22 или 23. Пред­по­ло­жим, он ста­вит 21. По­лу­чим це­поч­ку 12-21.

Петя может по­ста­вить 11 или 13. Пред­по­ло­жим, он ста­вит 11. По­лу­чим це­поч­ку 12-21-11.

Ваня может по­ста­вить толь­ко фишку со зна­че­ни­ем 13. По­лу­чим це­поч­ку 12-21-11-13.

Перед Петей в кучке оста­лись толь­ко фишки 22 и 23, то есть нет фишек, ко­то­рые он мог бы до­ба­вить в це­поч­ку. Таким об­ра­зом, пар­тия за­кон­че­на, Ваня вы­иг­рал.

Вы­пол­ни­те сле­ду­ю­щие три за­да­ния при ис­ход­ном на­бо­ре фишек в кучке {12, 14, 21, 22, 24, 41, 42, 44}.

За­да­ние 1.

а)  При­ве­ди­те при­мер самой ко­рот­кой пар­тии, воз­мож­ной при дан­ном на­бо­ре фишек. Если таких пар­тий не­сколь­ко, до­ста­точ­но при­ве­сти одну.

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

За­да­ние 2. Пусть Петя пер­вым ходом пошел 44. У кого из иг­ро­ков есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая в этой си­ту­а­ции вы­иг­рать своим чет­вер­тым ходом? По­строй­те в виде ри­сун­ка или таб­ли­цы де­ре­во всех пар­тий, воз­мож­ных при ре­а­ли­за­ции вы­иг­ры­ва­ю­щим иг­ро­ком этой стра­те­гии. На рёбрах де­ре­ва ука­зы­вай­те ход, в узлах  — це­поч­ку фишек, по­лу­чив­шу­ю­ся после этого хода.

За­да­ние 3. Ука­жи­те хотя бы один спо­соб убрать 2 фишки из ис­ход­но­го на­бо­ра так, чтобы все­гда вы­иг­ры­вал не тот игрок, ко­то­рый имеет вы­иг­рыш­ную стра­те­гию в за­да­нии 2. При­ве­ди­те при­мер пар­тии для на­бо­ра из 6 остав­ших­ся фишек.