2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Задачки профессора Снэйпа
Сообщение09.03.2021, 08:11 
Аватара пользователя


13/08/13

4323
Наткнулся на старую тему, и почему-то никто не решил задачки из первого поста ТС :-) Я попробую)

Цитата:
Ангел и чёрт играют в такую игру. В начале игры перед ангелом стоит пустой ящик, перед чёртом --- корзина, полная натуральных чисел (в ней лежит по одному экземпляру каждого числа). Ходы делаются по очереди. В свой ход ангел кладёт в ящик два произвольных натуральных числа (которых там ещё нет). В ответ на это чёртик выкидывает любое число из корзины. Чёрт выигрывает, если после завершения игры (в полдень :) ) в корзине остаётся бесконечное множество чисел и оно оказывается подмножеством множества чисел, лежащих в ящике у ангела. Всегда ли чёрт может выиграть?

Да, черт всегда побеждает. Стратегия следующая - пусть ангел кладет два числа, большее красим в красный, его не трогаем. Каждый ход выбрасываем число, которое удовлетворяет условию - оно наименьшее из чисел, которые есть в корзине, и при этом не являющееся красным.
Цитата:
То же самое, только ангел кладёт не по два, а по одному числу?

Тут выигрывает ангел. Сначала он кладет в корзину любое число. Если черт выкидывает это число из корзины, он снова кладет любое число. Если черт выкидывает другое число, то ангел кладет это число.
Цитата:
Корзина, ящик и очерёдность ходов такие же, как и в первой задаче. Ангел может на каждом своём ходе класть любое конечное количество чисел в ящик (в том числе и нулевое количество, то есть, фактически, пропускать ход). Чёрт может либо выкидывать число из корзины, либо пропускать ход. Считается, что чёрт выигрывает, если после завершения игры множество $D$ чисел, оставшихся в корзине, бесконечно и либо $D \cap A$, либо $D \setminus A$ --- конечное множество, где $A$ --- множество чисел, положенных ангелом в ящик в процессе игры. Вопрос тот же: всегда ли чёрт может выиграть?

Тут выигрывает снова черт. Для этого ему надо действовать так - если ангел пропускает ход, то и он пропускает ход. Если ангел кладет множество чисел, то наибольшее помечает красным, и его не трогает. Стратегия следующая - если на этом ходу появилось красное число (оно не должно быть выкинутым до этого), то черт выкидывает наименьшее не красное число, в противном случае пропускает ход.

 Профиль  
                  
 
 Re: Задачки профессора Снэйпа
Сообщение09.03.2021, 17:19 
Заслуженный участник


23/07/08
10626
Crna Gora
Sicker в сообщении #1508441 писал(а):
Да, черт всегда побеждает. Стратегия следующая - пусть ангел кладет два числа, большее красим в красный, его не трогаем. Каждый ход выбрасываем число, которое удовлетворяет условию - оно наименьшее из чисел, которые есть в корзине, и при этом не являющееся красным.
Ок.

Del

 Профиль  
                  
 
 Re: Задачки профессора Снэйпа
Сообщение09.03.2021, 17:28 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Я видимо чего-то не понимаю в условии третьей задачи. Стратегия "пойти спать" (пропускать все ходы) для черта не является выигрышной? Получим $D = \mathbb N$, и либо $D \cap A$ либо $D \setminus A$ бесконечно, т.к. $D \cap A \cup D \setminus A = D = \mathbb N$.

 Профиль  
                  
 
 Re: Задачки профессора Снэйпа
Сообщение09.03.2021, 21:01 


21/05/16
4292
Аделаида
mihaild в сообщении #1508498 писал(а):
либо $D \cap A$ либо $D \setminus A$ бесконечно

А надо, чтобы было конечно.

 Профиль  
                  
 
 Re: Задачки профессора Снэйпа
Сообщение11.03.2021, 13:10 
Аватара пользователя


23/12/18
430
Sicker в сообщении #1508441 писал(а):
Да, черт всегда побеждает. Стратегия следующая - пусть ангел кладет два числа, большее красим в красный, его не трогаем. Каждый ход выбрасываем число, которое удовлетворяет условию - оно наименьшее из чисел, которые есть в корзине, и при этом не являющееся красным.


Но ведь может быть так, что оба числа, которые ангел положил в ящик, чёрт до этого уже выкинул из корзины. Тогда чёрт помечает красным число, которое уже выкинул. Не факт, что в конце игры множество красных чисел, которые чёрт не выкинул, будет бесконечным.

 Профиль  
                  
 
 Re: Задачки профессора Снэйпа
Сообщение11.03.2021, 13:16 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
xagiwo в сообщении #1508675 писал(а):
Но ведь может быть так, что оба числа, которые ангел положил в ящик, чёрт до этого уже выкинул из корзины
Не может - черт выкидывает только числа, которые уже есть в корзине.

 Профиль  
                  
 
 Re: Задачки профессора Снэйпа
Сообщение11.03.2021, 13:31 
Аватара пользователя


23/12/18
430
mihaild в сообщении #1508676 писал(а):
Не может - черт выкидывает только числа, которые уже есть в корзине.

И что? Здесь речь не о том, что делает чёрт, а о том, что делает ангел. А ангелу достаточно всего лишь взять два числа, которых на момент его хода нет ни в ящике ни в корзине, и ничто в стратегии не запрещает появления таких пар. Тогда чёрту придётся покрасить в красное число, которое он уже выкинул.

 Профиль  
                  
 
 Re: Задачки профессора Снэйпа
Сообщение11.03.2021, 13:36 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
xagiwo в сообщении #1508679 писал(а):
и ничто в стратегии не запрещает появления таких пар
Запрещает. Все числа, которых нет в корзине, есть в ящике. Потому что черт выкидывает число из корзины только после того, как оно появится в ящике.

 Профиль  
                  
 
 Re: Задачки профессора Снэйпа
Сообщение11.03.2021, 13:45 
Аватара пользователя


23/12/18
430
mihaild в сообщении #1508680 писал(а):
Потому что черт выкидывает число из корзины только после того, как оно появится в ящике.

Нет, выкидывается наименьшее не-красное число из корзины, которое там ещё есть, независимо от того, в ящике оно или нет
Sicker в сообщении #1508441 писал(а):
Каждый ход выбрасываем число, которое удовлетворяет условию - оно наименьшее из чисел, которые есть в корзине, и при этом не являющееся красным.

Но если сделать так, как Вы сказали, и выкидывать из корзины только числа, находящиеся в ящике, то получится вообще плохо – любое число, которое за игру ангел так и не положит в ящик, останется в корзине. Тогда корзина не будет подмножеством ящика, в ней есть число, которого нет в ящике.

 Профиль  
                  
 
 Re: Задачки профессора Снэйпа
Сообщение12.03.2021, 06:14 
Аватара пользователя


13/08/13

4323
xagiwo в сообщении #1508675 писал(а):
Но ведь может быть так, что оба числа, которые ангел положил в ящик, чёрт до этого уже выкинул из корзины. Тогда чёрт помечает красным число, которое уже выкинул.

Ну да, и?
xagiwo в сообщении #1508675 писал(а):
Не факт, что в конце игры множество красных чисел, которые чёрт не выкинул, будет бесконечным.

Факт, т.к. ангел кладет по два числа, а черт выкидывает по одному.

-- 12.03.2021, 06:15 --

mihaild в сообщении #1508676 писал(а):
Не может

Может :-)

 Профиль  
                  
 
 Re: Задачки профессора Снэйпа
Сообщение12.03.2021, 07:34 
Аватара пользователя


23/12/18
430
Sicker в сообщении #1508780 писал(а):
Факт, т.к. ангел кладет по два числа, а черт выкидывает по одному.

И правда. Извиняюсь.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: mihaild


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group