2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Вася и Петя
Сообщение07.11.2006, 14:34 
Заслуженный участник
Аватара пользователя


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

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


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

 Профиль  
                  
 
 
Сообщение07.11.2006, 18:00 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение07.11.2006, 18:01 
Заслуженный участник


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


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

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

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

 Профиль  
                  
 
 
Сообщение07.11.2006, 19:48 


21/06/06
1721
А мне кажется, что перед последним ходом должна быть возможность вместить 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

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

 Профиль  
                  
 
 
Сообщение07.11.2006, 19:56 
Заслуженный участник


09/02/06
4382
Москва
Рост явно медленнее 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$ легко представить. Можно существенно эффективнее собрать я пока не знаю.
Исправил ошибку вычисления.

 Профиль  
                  
 
 
Сообщение07.11.2006, 20:10 
Заслуженный участник


05/09/05
515
Украина, Киев
Руст писал(а):
Рост явно медленнее 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- количество цепочек данной длины
добавление к цепочке двух крестиков и из-за этого превращение её в максимальную по длине возможно вероятно только на последнем шаге.

 Профиль  
                  
 
 
Сообщение07.11.2006, 20:48 


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

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

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

 Профиль  
                  
 
 
Сообщение07.11.2006, 21:47 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение07.11.2006, 22:28 
Заслуженный участник


09/02/06
4382
Москва
Вроде оптимальный является распределение $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.

 Профиль  
                  
 
 
Сообщение08.11.2006, 08:47 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение08.11.2006, 20:31 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Мой маленький, но грубый и сильный электронный друг подсказывает мне, что
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
оптимальнее стереть центральный крестик. Это позволит продержаться на ход больше.

 Профиль  
                  
 
 
Сообщение08.11.2006, 21:02 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение09.11.2006, 18:41 
Заслуженный участник


05/09/05
515
Украина, Киев
Руст писал(а):
Формула $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

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

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

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



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

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


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

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