Задачки профессора Снэйпа

[Sicker]

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

Цитата:

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

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

Цитата:

То же самое, только ангел кладёт не по два, а по одному числу?

Тут выигрывает ангел. Сначала он кладет в корзину любое число. Если черт выкидывает это число из корзины, он снова кладет любое число. Если черт выкидывает другое число, то ангел кладет это число.

Цитата:

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

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

[svv]

Sicker в сообщении #1508441 писал(а):

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

Ок.

Del

[mihaild]

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

[kotenok gav]

mihaild в сообщении #1508498 писал(а):

либо $D \cap A$ либо $D \setminus A$ бесконечно

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

[xagiwo]

Sicker в сообщении #1508441 писал(а):

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

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

[mihaild]

xagiwo в сообщении #1508675 писал(а):

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

Не может - черт выкидывает только числа, которые уже есть в корзине.

[xagiwo]

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

Не может - черт выкидывает только числа, которые уже есть в корзине.

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

[mihaild]

xagiwo в сообщении #1508679 писал(а):

и ничто в стратегии не запрещает появления таких пар

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

[xagiwo]

mihaild в сообщении #1508680 писал(а):

Потому что черт выкидывает число из корзины только после того, как оно появится в ящике.

Нет, выкидывается наименьшее не-красное число из корзины, которое там ещё есть, независимо от того, в ящике оно или нет

Sicker в сообщении #1508441 писал(а):

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

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

[Sicker]

xagiwo в сообщении #1508675 писал(а):

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

Ну да, и?

xagiwo в сообщении #1508675 писал(а):

Не факт, что в конце игры множество красных чисел, которые чёрт не выкинул, будет бесконечным.

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

-- 12.03.2021, 06:15 --

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

Не может

Может

[xagiwo]

Sicker в сообщении #1508780 писал(а):

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

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