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 ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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