Сумма чисел на карточках уменьшается

Question

Алиса и Боб играют в игру с $n$открытки. Алиса пишет числа$1,2,\ldots,n$по одному разу, и Боб тоже (на том же наборе карточек). Затем они по очереди выбирают карты в определенной последовательности. На каждом ходу игрок выбирает карту со своим наименьшим числом. В конце игры Алиса отмечает сумму своих чисел на своих карточках.

После этого указанная последовательность изменяется путем перемещения Алисы на несколько ходов раньше (никакие другие модификации не допускаются), и игра повторяется таким же образом. Верно ли, что Алиса обязательно получает меньшую или равную сумму, чем раньше?

Пример : Алиса пишет$1, 2, 3, 4$, Боб пишет $1, 3, 4, 2$. Первоначально последовательность: Боб, Алиса, Боб, Алиса. Боб выбирает первую карту, Алиса - вторую, Боб - четвертую (потому что число Боба на четвертой карте меньше, чем на третьей), а Алиса - третью, поэтому Алиса получает$2+3=5$. После этого предположим, что последовательность изменена путем перемещения первого хода Алисы вперед, так что теперь это Алиса, Боб, Боб, Алиса. Алиса выбирает первую карту, Боб - четвертую, Боб - вторую, а Алиса - третью, поэтому Алиса получает$1+3=4$.

Чтобы доказать, что это правда, достаточно показать, что для каждого $k$, Алиса получает меньшее или равное число $k$-й ход оригинальной игры, чем в ней $k$-й ход модифицированной игры. Можно ли это сделать по индукции?

Answer 1

Теорема верна; Оценка Алисы может только уменьшаться. У меня нет элегантного доказательства, но я могу исчерпать все случаи внимательным исследованием.

Предварительные действия: давайте проиндексируем карты, используя порядок Алисы, чтобы Алиса всегда выбирала крайнюю левую невыбранную карту. Заглавные буквы вроде$A_i$ и $B_j$относится к определенному ходу во время игры. Соответствующие строчные буквы вроде$a_i$ и $b_j$ сослаться на индекс карты, которая будет выбрана во время ходов $A_i$ и $B_j$соответственно. Так что если$b_j=4$, это означает, что во время хода Боба $B_j$, Боб выберет карту с индексом 4 (по соглашению с индексом Алисы).

В качестве базового случая рассмотрим последовательность $\cdots BA$. Мы собираемся поменять местами последние два хода.$B$ и $A$. Обратите внимание, что мы можем просто игнорировать любую из уже выбранных / вытянутых карт; они не могут быть затронуты этим свопом. Поскольку это конец игры, остаются только две невыбранные карты.

• Был $a<b$? В этом случае карты раскладываются как$a\;b$. Обмен$B$ и $A$не имеет значения, потому что оба игрока все равно предпочтут свои исходные позиции. Следовательно, счет Алисы остается прежним.

• Был $b>a$? Затем карты раскладываются как$b\;a$. После обмена Алиса жадно предпочтет крайнюю левую незанятую карту, а Боб возьмет другую. После обмена Алиса выбрала строго меньшую карту; следовательно, оценка Алисы уменьшится, QED.

В качестве индуктивного случая рассмотрим последовательность $\cdots BA^{k+1}B\cdots $, который мы собираемся поменять местами, чтобы сделать $\cdots ABA^{k}B\cdots$. Обратите внимание: поскольку мы начали с чередующегося набора движений$A$ и $B$, и мы разрешаем движение только влево $A$s, у нас есть определенные инварианты. В частности, если последовательность ходов позволяет Алисе$k$ последовательных ходов, то после этого у Боба должно быть не менее $k$ осталось ходов.

Назовем индексы этих ходов $b, a_0,\ldots,a_k, \hat b$соответственно.

• Был $a_0<b$? Ситуация выглядит так:$\quad a_0\ldots\ldots\ldots b$. Если это так, то, как и раньше, смена порядка ходов не влияет на предпочтения игроков, и остальная часть игры продолжается точно так же, как и первоначально, без изменения счета.

• Был $a_0>b$? Поскольку Алиса всегда выбирает крайнюю левую незанятую карту, она должна была выглядеть так:$b \; a_0 a_1a_2\ldots a_k \cdots\cdots\cdots \hat b $. Следовательно, после обмена Алиса с жадностью займет крайнее левое место в первом ходу. Что теперь будет делать Боб? Ситуация выглядит так$a_0^\prime \cdots\cdots\cdots\cdots$. Есть удивительно ограниченный выбор.

  • Возможно, первый ход Боба находится где-то в середине $a_1\ldots a_k$ теперь, когда у Боба есть шанс перебраться туда раньше Алисы, нарушив место одного из $A_1\ldots A_k$раньше ходил. Это не проблема, так как все$A_i$ можно просто сдвинуть влево к вакансии, оставленной Бобом: $$a_0^\prime \underbrace{a_1^\prime}_{\text{was }b} a_2^\prime a_3^\prime\ldots b^\prime \ldots a_k^\prime$$ Если посчитать, Алиса просто получит меньшую карту в $b$, в обмен на потерю более высокой карты в некоторых $a_i$. Следовательно, оценка Алисы снизилась. Поскольку после обмена были взяты все те же карты, что и раньше, остальная часть игры фактически продолжается точно так же, как и раньше, после того, как мы закончим делать$ABA^k$. Следовательно, оценка Алисы только уменьшилась.

  • Единственная возможность состоит в том, что первый ход Боба $\hat b$. Чтобы понять, почему, нужно внимательно подумать. Из оригинальной игры мы знали, что Боб предпочитает$b$как первый выбор; но если все$a_0\ldots a_k$ и $b$ были заняты, выбор Боба был $\hat{b}$среди всех оставшихся карт. После обмена$b$ действительно занят, и мы уже рассмотрели случай, когда Боб предпочитает $a_0\ldots a_k$ когда $b$уже занято. Следовательно, согласно ранее выраженным предпочтениям Боба, первым шагом Боба после обмена будет принятие$\hat b$.

    Следовательно, когда Алиса двинется, Алиса сможет сдвинуть $A_1\ldots A^k$ влево, создавая потенциальную новую вакансию на $a_k$. $a_0^\prime\underbrace{a_1^\prime}_{\text{was }b}a_2^\prime\ldots a_k^\prime \square\cdots\cdots b^\prime $.

    Если это так, то для этой конкретной игры с конкретными нумерациями / предпочтениями Алисы и Боба порядок ходов $\cdots A\dot{B}A^kB\cdots $ фактически эквивалентен $\cdots A^{k+1}B\hat{B}\cdots$- мы можем «шунтировать» $\dot{B}$ полностью до конца.

    Теперь мы можем закрыть индуктивный шаг. Боб только что взял$\hat{b}$. Следующим шагом Боба может стать заполнение вакансии. В этом случае остальная часть игры должна продолжаться так же, как и раньше, с этого момента, потому что нам снова удалось выбрать все те же карты, что и в игре до обмена (Алиса и Боб выбрали разные карты, чем возможно, они делали это раньше, но суть в том, что все те же самые карты были удалены из игры; мы находимся в стратегически эквивалентной точке в будущем.) Следовательно, счет Алисы останется уменьшенным до конца игры, QED.

    В качестве альтернативы -

Продолжение следует.