Задания
Версия для печати и копирования в MS Word

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 10 кам­ней, а в дру­гой  — 5 кам­ней; такую по­зи­цию в игре будем обо­зна­чать (10, 5). Тогда за один ход можно по­лу­чить любую из четырёх по­зи­ций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

В на­чаль­ный мо­мент в пер­вой куче было семь кам­ней, во вто­рой куче  — S кам­ней; 1 ≤ S ≤ 69.

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

Най­ди­те два таких зна­че­ния S, при ко­то­рых у Пети есть вы­иг­рыш­ная стра­те­гия, причём од­но­вре­мен­но вы­пол­ня­ют­ся два усло­вия:

—  Петя не может вы­иг­рать за один ход;

—  Петя может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Ваня.

Най­ден­ные зна­че­ния за­пи­ши­те в от­ве­те в по­ряд­ке воз­рас­та­ния без раз­де­ли­тель­ных зна­ков.

Спрятать решение

Ре­ше­ние.

Из хода ре­ше­ния преды­ду­ще­го за­да­ния можно за­клю­чить, что зна­че­ния S 35 и 36 не под­хо­дят, по­сколь­ку в этом слу­чае Петя может вы­иг­рать своим пер­вым ходом. Рас­смот­рим зна­че­ние S  =  34. В этом слу­чае Петя своим пер­вым ходом может до­ба­вить в первую кучу один ка­мень и по­лу­чить кучу (8, 34). После пер­во­го хода Вани может воз­ник­нуть одна из четырёх по­зи­ций: (9, 34), (8, 35), (16, 34), (8, 68). Во всех слу­ча­ях Петя удва­и­ва­ет ко­ли­че­ство кам­ней во вто­рой куче и вы­иг­ры­ва­ет своим вто­рым ходом.

Вто­рое зна­че­ние S  — 31. При S  =  31 Петя удва­и­ва­ет ко­ли­че­ство кам­ней в пер­вой куче и по­лу­ча­ет по­зи­цию (14, 31). После пер­во­го хода Вани может воз­ник­нуть одна из четырёх по­зи­ций: (15, 31), (14, 32), (28, 31), (14, 62). Во всех слу­ча­ях Петя удва­и­ва­ет ко­ли­че­ство кам­ней во вто­рой куче и вы­иг­ры­ва­ет своим вто­рым ходом.

Таким об­ра­зом, ответ  —3134.

 

Ответ: 3134.

 

При­ведём ре­ше­ние на языке Python.

def f(x, y, h):

if h == 4 and x + y >= 77:

return 1

elif h == 4 and x + y < 77:

return 0

elif x + y >= 77 and h < 4:

return 0

else:

if h % 2 != 0:

return f(x + 1, y, h + 1) or f(x, y + 1, h + 1) or f(x * 2, y, h + 1) or f(x, y * 2, h + 1) # стра­те­гия по­бе­ди­те­ля

else:

return f(x + 1, y, h + 1) and f(x, y + 1, h + 1) and f(x * 2, y, h + 1) and f(x, y * 2, h + 1) # стра­те­гия про­иг­рав­ше­го(любой ход)

 

for x in range(1, 70):

if f(x, 7, 1) == 1:

print("За­да­ча 20:", x)

 

При­ведём ре­ше­ние Вик­то­рии Зи­бе­ро­вой на языке Python.

def f (k1,k2, m):

if k1+k2 >= 77:

return m%2==0

if m==0:

return 0

h=[f(k1+1, k2, m-1),f(k1, k2+1, m-1), f(k1*2, k2, m-1), f(k1, k2*2, m-1)]

return any(h) if m%2 !=0 else all(h)

print('За­да­ние 20:', (*[s for s in range (1, 70) if f(7,s,3) and not f(7, s, 1)]))

 

При­ведём ре­ше­ние Ге­ор­гия Востри­ко­ва на языке Python.

def f(k1, k2, hod):

# hod - номер хода. 1 - пер­вый ход Пети, 2 - пер­вый ход Вани, 3 - вто­рой ход Пети, 4 - вто­рой ход Вани

if hod == who_win and k1 + k2 >= win_sum:

# нуж­ный игрок по­бе­дил на нуж­ном ходе

return 1

elif hod == who_win and k1 + k2 < win_sum:

# нуж­ный игрок не по­бе­дил на нуж­ном ходе

return 0

elif hod < who_win and k1 + k2 >= win_sum:

# Петя или Ваня по­бе­дил рань­ше вре­ме­ни

if ZADANIE != 21:

return 0

elif hod == who_win-2:

# в №21 до­пус­ка­ем по­бе­ду Вани пер­вым ходом(рань­ше вре­ме­ни, когда hod == 3)

return 1

# даль­ше на­чи­на­ет­ся сам ход иг­ро­ка

# ПРИ­МЕР: если hod = 3, то выше мы про­ве­ри­ли не по­бе­дил ли Ваня после сво­е­го пер­во­го хода

# если ещё не по­бе­дил, тогда уже де­ла­ем вто­рой ход Пети

else:

# hod - чётный, зна­чит, сей­час ходит Ваня, иначе(нечёт) Петя

if hod % 2 == 0:

# дей­ствия Вани с ку­ча­ми (по усло­вию: k1/k2 + 1 и k1/k2 * 2)

if ZADANIE == 19 or ZADANIE == 21:

# иг­ра­ем за Ваню, по­дойдёт любое удоб­ное дейт­свие(or)

return f(k1, k2 + sum2, hod + 1) or f(k1 + sum1, k2, hod + 1) or f(k1, k2 * x2, hod + 1) or f(k1 * x1, k2, hod + 1)

elif ZADANIE == 20:

# иг­ра­ем про­тив Вани, про­ве­ря­ем все его воз­мож­ные дей­ствия(and)

return f(k1, k2 + sum2, hod + 1) and f(k1 + sum1, k2, hod + 1) and f(k1, k2 * x2, hod + 1) and f(k1 * x1, k2, hod + 1)

else:

# дей­ствия Пети с ку­ча­ми (по усло­вию: k1/k2 + 1 и k1/k2 * 2)

if ZADANIE == 19 or ZADANIE == 20:

# иг­ра­ем про­тив Пети или за Петю, по­дойдёт любое не­удач­ное/удач­ное дей­ствие Пети(or)

return f(k1, k2 + sum2, hod + 1) or f(k1 + sum1, k2, hod + 1) or f(k1, k2 * x2, hod + 1) or f(k1 * x1, k2, hod + 1)

elif ZADANIE == 21:

# иг­ра­ем про­тив Пети, про­ве­ря­ем все его воз­мож­ные дей­ствия(and) для по­бе­ды Вани 2ым ходом

if who_win == 5:

return f(k1, k2 + sum2, hod + 1) and f(k1 + sum1, k2, hod + 1) and f(k1, k2 * x2, hod + 1) and f(k1 * x1, k2, hod + 1)

elif who_win == 3:

# иг­ра­ем про­тив Пети: про­ве­ря­ем, что не при любых ходах Пети, Ваня может вы­иг­рать пер­вым ходом

if ((f(k1, k2 + sum2, hod + 1) + f(k1 + sum1, k2, hod + 1) + f(k1, k2 * x2, hod + 1) + f(k1 * x1, k2, hod + 1)) < kol):

return 1

# УСЛО­ВИЯ ЗА­ДА­ЧИ ------------------------------------------------

sum1 = 1 # сколь­ко можно при­бав­лять в 1ую кучу

sum2 = 1 # сколь­ко можно при­бав­лять во 2ую кучу

x1 = 2 # во сколь­ко раз можно умно­жать 1ую кучу

x2 = 2 # во сколь­ко раз можно умно­жать 2ую кучу

kol = 4 # ко­ли­че­ство ва­ри­ан­тов дей­ствий с ку­ча­ми

k1 = 7 # ко­ли­че­ство кам­ней в 1ой куче

win_sum = 77 # общая сумма кам­ней от ко­то­рой на­чи­на­ет­ся по­бе­да

k2_max = 69 # мак­си­маль­ное S(ко­ли­че­ство кам­ней во 2ой куче)

# НОМЕР ЗА­ДА­ЧИ --------------------------------------------------

ZADANIE = 20 # для ка­ко­го за­да­ния про­грам­ма (19, 20 или 21)

if ZADANIE == 19:

# who_win - кто дол­жен вы­иг­рать и каким ходом?

who_win = 3 # №19 - Ваня пер­вым ходом

elif ZADANIE == 20:

who_win = 4 # №20 - Петя вто­рым ходом

elif ZADANIE == 21:

who_win = 5 # №21 - Ваня вто­рым ходом

for k2 in range(1, k2_max):

if f(k1, k2, 1) == 1:

if ZADANIE == 21:

who_win = 3 # про­ве­ря­ем, что не при любых ходах Пети, Ваня может вы­иг­рать пер­вым ходом

if f(k1, k2, 1) == 1:

print(k2)

break

else:

print(k2)

if ZADANIE != 20:

break

Источник: Де­мон­стра­ци­он­ная вер­сия ЕГЭ−2021 по ин­фор­ма­ти­ке
Раздел кодификатора ФИПИ: 1.5.2 Це­поч­ки, де­ре­вья, спис­ки, графы, мат­ри­цы, псев­до­слу­чай­ные по­сле­до­ва­тель­но­сти
Спрятать решение · Помощь
1

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 10 кам­ней, а в дру­гой 5 кам­ней; такую по­зи­цию в игре будем обо­зна­чать (10, 5). Тогда за один ход можно по­лу­чить любую из четырёх по­зи­ций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

В на­чаль­ный мо­мент в пер­вой куче было семь кам­ней, во вто­рой куче  — S кам­ней; 1 ≤ S ≤ 69.

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

Из­вест­но, что Ваня вы­иг­рал своим пер­вым ходом после не­удач­но­го пер­во­го хода Пети. Ука­жи­те ми­ни­маль­ное зна­че­ние S, когда такая си­ту­а­ция воз­мож­на.

Решение · Помощь
2

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 10 кам­ней, а в дру­гой  — 5 кам­ней; такую по­зи­цию в игре будем обо­зна­чать (10, 5). Тогда за один ход можно по­лу­чить любую из четырёх по­зи­ций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

В на­чаль­ный мо­мент в пер­вой куче было семь кам­ней, во вто­рой куче  — S кам­ней; 1 ≤ S ≤ 69.

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

Най­ди­те ми­ни­маль­ное зна­че­ние S, при ко­то­ром од­но­вре­мен­но вы­пол­ня­ют­ся два усло­вия:

—  у Вани есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети;

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

Решение · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026