Презентация на тему по теме Теория игр

использовать для побега угнанный автомобиль. Полиция не может доказать, что

именно они ограбили банк, но поймала их с поличным в украденном автомобиле. Их развели по разным комнатам и каждому предложили сделку: сдать сообщника и отправить его за решетку на 10 лет, а самому выйти на свободу. Но если они оба сдадут друг друга, то каждый получит по 7 лет. Если же никто ничего не скажет, то оба сядут на 2 года только за угон автомобиля.

ИГРА 1

и одновременно озвучиваем суммы. Если наша общая сумма меньше ста,

каждый получает то, что хотел. Если общее количество больше ста, тот, кто попросил наименьшее количество, получает желаемую сумму, а более жадный человек получает то, что осталось. Если мы просим одинаковую сумму, каждый получает 50 $. Сколько вы попросите? Как вы разделите деньги? Существует единственный выигрышный ход.

ИГРА 2

в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки

ходят по оче­ре­ди, пер­вый ход де­ла­ет Паша. За один ход игрок может до­ба­вить в кучу 1 ка­мень или 10 кам­ней. На­при­мер, имея кучу из 7 кам­ней, за один ход можно по­лу­чить кучу из 8 или 17 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней. Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся не менее 41. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 41 или боль­ше кам­ней.В на­чаль­ный мо­мент в куче было S кам­ней, 1 ≤ S ≤ 40.
Будем го­во­рить, что игрок имеет вы­иг­рыш­ную стра­те­гию, если он может вы­иг­рать при любых ходах про­тив­ни­ка. Опи­сать стра­те­гию иг­ро­ка — зна­чит опи­сать, какой ход он дол­жен сде­лать в любой си­ту­а­ции, ко­то­рая ему может встре­тить­ся при раз­лич­ной игре про­тив­ни­ка.
 

ответ.
1. а) Ука­жи­те все такие зна­че­ния числа S, при

ко­то­рых Паша может вы­иг­рать в один ход. Обос­нуй­те, что най­де­ны все нуж­ные зна­че­ния S, и ука­жи­те вы­иг­ры­ва­ю­щие ходы.
б) Ука­жи­те такое зна­че­ние S. при ко­то­ром Паша не может вы­иг­рать за один ход, но при любом ходе Паши Вова может вы­иг­рать своим пер­вым ходом. Опи­ши­те вы­иг­рыш­ную стра­те­гию Вовы.
2. Ука­жи­те два зна­че­ния S, при ко­то­рых у Паши есть вы­иг­рыш­ная стра­те­гия, причём Паша не может вы­иг­рать за один ход, но может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Вова. Для ука­зан­ных зна­че­ний S опи­ши­те вы­иг­рыш­ную стра­те­гию Паши.
3. Ука­жи­те зна­че­ние S, при ко­то­ром у Вовы есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Паши, од­на­ко у Вовы нет стра­те­гии, ко­то­рая поз­во­лит ему га­ран­ти­ро­ван­но вы­иг­рать пер­вым ходом. Для ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Вовы.

31, ..., 40. При мень­ших зна­че­ни­ях S за один

ход нель­зя по­лу­чить кучу, в ко­то­рой боль­ше 40 кам­ней. Паше до­ста­точ­но уве­ли­чить ко­ли­че­ство кам­ней на 10. При S < 31 по­лу­чить за один ход боль­ше 40 кам­ней не­воз­мож­но.
б) Вова может вы­иг­рать пер­вым ходом (как бы ни играл Петя), если ис­ход­но в куче будет S = 30 кам­ней. Тогда после пер­во­го хода Пети в куче будет 31 ка­мень или 40 кам­ней. В обоих слу­ча­ях Ваня уве­ли­чи­ва­ет ко­ли­че­ство кам­ней на 10 и вы­иг­ры­ва­ет в один ход.
2.  Воз­мож­ные зна­че­ния S: 20, 29. В этих слу­ча­ях Паша, оче­вид­но, не может вы­иг­рать пер­вым ходом. Од­на­ко он может по­лу­чить кучу из 30 кам­ней (при S = 20 он уве­ли­чи­ва­ет ко­ли­че­ство кам­ней на 10; при S = 29 до­бав­ля­ет 1 ка­мень). Эта по­зи­ция разо­бра­на в п. 1. б). В ней игрок, ко­то­рый будет хо­дить (те­перь это Вова), вы­иг­рать не может, а его про­тив­ник (то есть Паша) сле­ду­ю­щим ходом вы­иг­ра­ет.
3. Воз­мож­ное зна­че­ние S: 28. После пер­во­го хода Паши в куче будет 29 или 38 кам­ней. Если в куче ста­нет 38 кам­ней, Вова уве­ли­чит ко­ли­че­ство кам­ней на 10 и вы иг­ра­ет своим пер­вым ходом. Си­ту­а­ция, когда в куче 29 кам­ней, разо­бра­на в п. 2. В этой си­ту­а­ции игрок, ко­то­рый будет хо­дить (те­перь это Вова), вы­иг­ры­ва­ет своим вто­рым ходом.
В таб­ли­це изоб­ра­же­но де­ре­во воз­мож­ных пар­тий при опи­сан­ной стра­те­гии Вовы. За­клю­чи­тель­ные по­зи­ции (в них вы­иг­ры­ва­ет Вова) подчёрк­ну­ты. На ри­сун­ке это же де­ре­во изоб­ра­же­но в гра­фи­че­ском виде (оба спо­со­ба изоб­ра­же­ния де­ре­ва до­пу­сти­мы).
                                                                                     
 

сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят

по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в кучу один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в пять раз. На­при­мер, имея кучу из 10 кам­ней, за один ход можно по­лу­чить кучу из 11 или 50 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся более 200. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 201 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней,
1 ≤ S ≤ 200.
Го­во­рят, что игрок имеет вы­иг­рыш­ную стра­те­гию, если он может вы­иг­рать при любых ходах про­тив­ни­ка. Опи­сать стра­те­гию иг­ро­ка - зна­чит опи­сать, какой ход он дол­жен сде­лать в любой си­ту­а­ции, ко­то­рая ему может встре­тить­ся при раз­лич­ной игре про­тив­ни­ка.
Вы­пол­ни­те сле­ду­ю­щие за­да­ния. Во всех слу­ча­ях обос­но­вы­вай­те свой ответ.
1. а) При каких зна­че­ни­ях числа S Петя может вы­иг­рать пер­вым ходом? Ука­жи­те все такие зна­че­ния и вы­иг­ры­ва­ю­щий ход Пети.
б) Ука­жи­те такое зна­че­ние S, при ко­то­ром Петя не может вы­иг­рать за один ход, но при любом ходе Пети Ваня может вы­иг­рать своим пер­вым ходом. Опи­ши­те вы­иг­рыш­ную стра­те­гию Вани. 
2. Ука­жи­те два зна­че­ния S, при ко­то­рых у Пети есть вы­иг­рыш­ная стра­те­гия, причём (а) Петя не может вы­иг­рать пер­вым ходом, но (б) Петя может вы­иг­рать своим вто­рым ходом, не­за­ви­си­мо от того, как будет хо­дить Ваня.
Для ука­зан­ных зна­че­ний S опи­ши­те вы­иг­рыш­ную стра­те­гию Пети.
3. Ука­жи­те такое зна­че­ние S, при ко­то­ром
- у Вани есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети, и при этом
- у Вани нет стра­те­гии, ко­то­рая поз­во­лит ему га­ран­ти­ро­ван­но вы­иг­рать пер­вым ходом.
Для ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Вани. По­строй­те де­ре­во всех пар­тий, воз­мож­ных при этой вы­иг­рыш­ной стра­те­гии Вани (в виде ри­сун­ка или таб­ли­цы). На рёбрах де­ре­ва ука­зы­вай­те, кто де­ла­ет ход, в узлах — ко­ли­че­ство кам­ней в по­зи­ции.

При мень­ших зна­че­ни­ях S за один ход нель­зя по­лу­чить

кучу, в ко­то­рой боль­ше 200 кам­ней. Пете до­ста­точ­но уве­ли­чить ко­ли­че­ство кам­ней в 5 раз. При S < 41 по­лу­чить за один ход боль­ше 200 кам­ней не­воз­мож­но.
б) Ваня может вы­иг­рать пер­вым ходом (как бы ни играл Петя), если ис­ход­но в куче будет S = 40 кам­ней. Тогда после пер­во­го хода Пети в куче будет 41 ка­мень или 200 кам­ней. В обоих слу­ча­ях Ваня уве­ли­чи­ва­ет ко­ли­че­ство кам­ней в 5 раз и вы­иг­ры­ва­ет в один ход.
 
2. Воз­мож­ные зна­че­ния S: 8, 39. В этих слу­ча­ях Петя, оче­вид­но, не может вы­иг­рать пер­вым ходом. Од­на­ко он может по­лу­чить кучу из 40 кам­ней (при S=8 он уве­ли­чи­ва­ет ко­ли­че­ство кам­ней в 5 раз; при 5=39 - до­бав­ля­ет 1 ка­мень). Эта по­зи­ция разо­бра­на в п. 
1 б. В ней игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­рать не может, а его про­тив­ник (то есть Петя) сле­ду­ю­щим ходом вы­иг­ра­ет.
 
3. Воз­мож­ное зна­че­ние S: 38. После пер­во­го хода Пети в куче будет 39 или 190 кам­ней. Если в куче ста­нет 190 кам­ней, Ваня уве­ли­чит ко­ли­че­ство кам­ней в 5 раз и вы­иг­ра­ет своим пер­вым ходом. Си­ту­а­ция, когда в куче 39 кам­ней, разо­бра­на в п. 2. В этой си­ту­а­ции игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­ры­ва­ет своим вто­рым ходом.

сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят

по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в кучу один ка­мень, или до­ба­вить в кучу два камня, или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза.
На­при­мер, имея кучу из 10 кам­ней, за один ход можно по­лу­чить кучу из 11, 12 или 20 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.
Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче пре­вы­ша­ет 33. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 34 или боль­ше кам­ней. В на­чаль­ный мо­мент в куче было S кам­ней, 1 ≤ S ≤ 33.
Го­во­рят, что игрок имеет вы­иг­рыш­ную стра­те­гию, если он может вы­иг­рать при любых ходах про­тив­ни­ка. Опи­сать стра­те­гию иг­ро­ка — зна­чит опи­сать, какой ход он дол­жен сде­лать в любой си­ту­а­ции, ко­то­рая ему может встре­тить­ся при раз­лич­ной игре про­тив­ни­ка.
Вы­пол­ни­те сле­ду­ю­щие за­да­ния.
За­да­ние 1.
а) При каких зна­че­ни­ях числа S Петя может вы­иг­рать пер­вым ходом? Ука­жи­те все такие зна­че­ния и вы­иг­ры­ва­ю­щий ход Пети.
б) Ука­жи­те такое зна­че­ние S, при ко­то­ром Петя не может вы­иг­рать за один ход, но при любом ходе Пети Ваня может вы­иг­рать своим пер­вым ходом. Опи­ши­те вы­иг­рыш­ную стра­те­гию Вани.
За­да­ние 2.
Ука­жи­те три зна­че­ния S, при ко­то­рых у Пети есть вы­иг­рыш­ная стра­те­гия, причём Петя не может вы­иг­рать пер­вым ходом, но может вы­иг­рать своим вто­рым ходом не­за­ви­си­мо от того, как будет хо­дить Ваня. Для ука­зан­ных зна­че­ний S опи­ши­те вы­иг­рыш­ную стра­те­гию Пети.
За­да­ние 3.
Ука­жи­те такое зна­че­ние S, при ко­то­ром у Вани есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети, и при этом у Вани нет стра­те­гии, ко­то­рая поз­во­лит ему га­ран­ти­ро­ван­но вы­иг­рать пер­вым ходом