Вася и Петя

[RIP]

Имеется лента размера $1\times n$, разбитая на квадратики $1\times1$. Вася и Петя играют в игру. За 1 ход Вася ставит 2 крестика в разные квадратики. Петя за свой ход может стереть любое кол-во крестиков, стоящих подряд. Вася стремится получить 13 крестиков подряд. Внимание, вопрос.
При каком минимальном n Вася сможет обеспечить себе победу?

[ИСН]

Нетривиален сам факт, что это вообще возможно. 13 - число огромное, практически за пределами моего воображения. Пусть будет 6.
Вася ставит 8 крестиков порознь на подобающем расстоянии друг от друга (по ходу восстанавливая их там, где Петя стирает).
Потом он приписывает к каждому крестику ещё один, а Петя идёт за ним по пятам и успевает снести половину этих парочек, так что их остаётся 4.
Потом они таким же макаром строят две тройки.
Потом - одну четвёрку.
И тут Вася резким движением пририсовывает к ней два крестика.
Короче, что-то порядка n\cdot 2^{n-2}.
Upd. Ан нет, им необязательно быть с самого начала на таком расстоянии друг от друга. Можно меньше, а вот сколько...

[Руст]

Можно конечно короче. Например при n<=3 ответ N=n, при n=4 требуется N=5, дальше N(n) растёт примерно в два раза при росте n на 1.

[Macavity]

ИСН писал(а):

Нетривиален сам факт, что это вообще возможно. 13 - число огромное, практически за пределами моего воображения. Пусть будет 6.
Вася ставит 8 крестиков порознь на подобающем расстоянии друг от друга (по ходу восстанавливая их там, где Петя стирает).
Потом он приписывает к каждому крестику ещё один, а Петя идёт за ним по пятам и успевает снести половину этих парочек, так что их остаётся 4.
Потом они таким же макаром строят две тройки.
Потом - одну четвёрку.
И тут Вася резким движением пририсовывает к ней два крестика.
Короче, что-то порядка n\cdot 2^{n-2}.
Upd. Ан нет, им необязательно быть с самого начала на таком расстоянии друг от друга. Можно меньше, а вот сколько...

А у меня получилось всего 2416.

На последнем шаге должно быть 13 крестиков,
на предпоследнем перед удалением два раза по 11 (2*11+2=24)
еще раньше комбинация 11 10 10 выигрывает.
В итоге получилось 13*186-2=2416

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

[Sasha2]

А мне кажется, что перед последним ходом должна быть возможность вместить 2 раза по 12 (идущие подряд) и плюс еще один квадрат между ними, перед предпоследним ходом - должна быть возможность вместить три раза по 11 (подряд) и плюс два раза с двумя квадратами между ними и так далее. Отсюда и ищем максимум.
То есть получаем такой ряд:
2 x 12 + 1 x 1
3 x 11 + 2 x 2
4 x 10 + 3 x 3
5 x 9 + 4 x 4
6 x 8 + 5 x 5
7 x 7 + 6 x 6
8 x 6 + 7 x 7
9 x 5 + 8 x 8
10 x 4 + 9 x 9
11 x 3 + 10 x 10
12 x 2 +11 x 11

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

[Руст]

Рост явно медленнее 2^n, так как для сбора n достаточно собирать в двух местах по n-2. Учитывая, что перед сбором другой одну уничтожает, получаем N(n)<=3N(n-2), т.е. $N(n)\le 3^{n-2}.$ Алгоритм сборки на площадке длины $N(2k+1)=3^k, N(13)=3^{6}=729$ легко представить. Можно существенно эффективнее собрать я пока не знаю.
Исправил ошибку вычисления.

[Macavity]

Руст писал(а):

Рост явно медленнее 2^n, так как для сбора n достаточно собирать в двух местах по n-2. Учитывая, что перед сбором другой одну уничтожает, получаем N(n)<=3N(n-2), т.е. $N(n)\le 3^{n-2}.$ Алгоритм сборки на площадке длины $N(n)=3^{n-2}, N(13)=3^{11}=177147$ легко представить. Можно существенно эффективнее собрать я пока не знаю. Возможно вы Macavity, что-то не учли.

Возможно.
Надо ещё думать.

Я представлял цепочки вроде:
13
11 11
11 10 10
10 10 10 9
9 9 9 9 9 9
8 8 8 8 8 8 8 8 8 8

и т.д.

может и неверно, но получалось,вроде, что
n_{i-1}=even^+(n_i+(n_i/2))
хотя возможно ошибаюсь
even^+ округление в большую сторону до четного.

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

[Sasha2]

Странно, но можно рассуждать и так:

Всю ленту делим на отрезки по 14 квадратов в каждом. Далее Вася идет и ставит квадратики через один. В каждом таком участке выставляется 1, 3, 5, 7, 8, 11 и 13 квадраты. Это тривиально и Петя тут помешать ничем не может. Далее осталось заполнить шесть победных квадратов. Пусть таких отрезков перед этим было x. Ставим еще где нибудь в этих участках по два квардрата. Петя портит один, мы далее ставим еще в двух, Петя снова портит один. И так после всей этой процедуры будем иметь x/2 отрезков, в которых надо доставить по 5 квадратов. Продолжая ту же процедуру, придем что участков (по 14 квадратов в каждом) должно быть 2 в шестой степени. То есть вся линия равна 896 квадратам.

Ну и наконец, процедуру можно усовершенствовать, примерно так: разрезав всю ленту на участки по 13 и наложив их друг на друга, получим, что Вася выграет, если заполнит в одной x квадратов, а в вышестоящей (с противоположной стороны) 13-x квадратов. Теперь надо заполнять так, чтобы крайние квадраты в соседних участках не были заполнены (то есть в шахматном порядке). Тогда та же самая процедура только оценка станвится уже 13+64, то есть 832 квадрата.

[RIP]

Sasha2, Ваш алгоритм можно еще чуть-чуть улучшить. Разобьем всю ленту на $33(=2^5+1)$ кусков длины 12. Сначала ставим крестики так, чтобы они "раскрасили" всю ленту в шахматном порядке. После последнего хода коварного Пети остается 32 неиспорченных куска длины 12. Далее легко получить 16 кусков, в которых закрашены первые 3 клетки(а дальше в шахматном порядке), потом 8 кусков, в которых закрашены первые 5, итд. Кончится тем, что получим 11 клеток подряд(и это после хода Пети!) Осталось присобачить к ним 2 крестика. Поэтому достаточно 12*33=396 клеток. А вот насколько это можно ещё уменьшить?
В общем случае это дает, что достаточно что-то вроде $n\cdot2^{\frac n2}$. Интересно было бы посмотреть какое-нибудь док-во, где бы показывалось, что какого-то кол-ва клеток недостаточно (если, конечно Петя не полный даун.)

[Руст]

Вроде оптимальный является распределение $N(n)=2N(n-2)+N(n-4)$, т.е. достаточно одного разделителя для N(n-4). Тогда из N(1)=1, N(3)=3 получаем $N(2k-1)=\frac{(1+\sqrt 2 )^k+(1-\sqrt 2 )^k }{2}$, т.е. N(13)=239.

[Руст]

Вроде N(13)<=99. Суть алгоритма: вначале все нечётные, потом образуем тройки из двух сторон. Если одну тройку Петя вычеркнул (a-1,a,a+1) создаем тройку (a+7, a+8,a+9) (когда с верхнего конца отступая на 7 меньше. Если не вычеркнута, то отступаем на 12, и т.д. При сборке используем не тронутые куски, т.е. не теряем по на каждом шаге как у Sasha, а меньшие куски.

[worm2]

Мой маленький, но грубый и сильный электронный друг подсказывает мне, что
N(5) = 7 (макс. число ходов Васи при идеальной защите Пети --- 7)
N(6) = 10 (12)
N(7) = 15 (12)
N(8) = 22 (24)
N(9) > 29
Статистики, конечно, маловато, но уже бросается в глаза формула для нечётных n=2k-1: $N(2k-1)=2^k-1$, верная для всех нечётных n, меньших 9.
Любопытно также, что при оптимальных N на некоторых шагах наблюдается аномально маленькое число позиций, через которые игра обязательно пройдёт при оптимальной игре обоих игроков.
Например, при n = 6, N = 10 при оптимальной игре после 4-го хода Васи обязательно встретится одна из пяти позиций:
x0x00x0x0x
x0x0x00x0x
x0x0x0xx0x
x0x0xx0x0x
x0xx0x0x0x
Т.е. можно сказать, что Вася должен стремиться к одной из этих пяти позиций.
Что ещё можно добавить? Не всегда оптимальной для Пети является стратегия стирания максимального числа крестиков. Например, в позиции (n=6, N=10)
xxx0x0xxx0
оптимальнее стереть центральный крестик. Это позволит продержаться на ход больше.

[Руст]

Формула $N(2k-1)=2^k-1$ похоже на правду. Возможно и найдётся способ доказать. Только не очень понятно ведут себя N(2k), при этом N(4)=5 нечётное число, а другие (если точно вычислили ) чётные.

[Macavity]

Руст писал(а):

Формула $N(2k-1)=2^k-1$ похоже на правду. Возможно и найдётся способ доказать. Только не очень понятно ведут себя N(2k), при этом N(4)=5 нечётное число, а другие (если точно вычислили ) чётные.

Интересно, насколько изменится алгоритм и оценка минимальной достаточной для Васиной победы длины ленты, если Вася может делать три креста за раз? s крестов за раз?

Например, для трех крестов, вроде бы
N_3(4)=4
N_3(5)=5
N_3(6)=7
N_3(7)=9
N_3(8)\leqslant15
N_3(9)\leqslant15

Можно ли обобщить полученную формулу, например, как-то так

N_s(n)\leqslant2^{\lceil({n+s})/s\rceil}-1

Или каким-то другим способом...