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

При каком минимальном n Вася сможет обеспечить себе победу?

(18) на вашем ходу не может быть четное количество крестиков)

ай наврал, надо подумать

На 47 ходу.

http://savepic.org/4963737.jpg

(32) (31)  вопрос в задаче: найти минимальный размер ленты.
а не число ходов

(33) Минимальный размер ленты 76
Для основной игры 74 и 2 для завершения формирования игрового поля.

http://savepic.org/4941256.jpg

Вот поэтому то и тз писать смысла нет, откуда тут появились квадраты, если в условиях задачи лента

Предположим Петя за 1 ход стирает самую длинную последовательность (самая примитивная логика).

Смоделируем с конца:
На поле: 1 последовательность из 10 крестиков.
Вася (последний ход):  добавляет к 8 крестикам 2 крестика.
На поле: 1 последовательность из 8 крестиков.
Петя: стирает 1 последовательность из 8 крестиков.
На поле: 2 последовательности из 8 крестиков.
Вася: добавляет по 1 крестику к двум последовательностям из 7 крестиков.
На поле: 2 последовательности из 7 крестиков.
Петя: стирает 1 последовательность из 7 крестиков.
На поле: 3 последовательности из 7 крестиков.
Вася: добавляет по 1 крестику к двум последовательностям из 6 крестиков.
На поле: 2 последовательности из 6 крестиков и 1 последовательность из 7 крестиков.
.... и т.п.
Кто составит формулу?

(37) проще будет если ты будешь соединять крестики
х_х ставить вместо _ х

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

По идее последний ход Васи может быть таким:
XXX_XX_XXX

Но тогда Пете надо стремиться уничтожать центральные последовательности, таким образом, чтобы промежуток между ними был больше 1.

Тогда возможно логика снова сведется к примитивной.

(34) Корректировка: Минимум 68 (65 для игры и 3 для завершения поля).

(35)  Петя явно поддается Васе. Например на 44-м ходу.

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

Как я понимаю, сначала надо понять сколько последовательностей крестиков нужно стартовать.

Затем мы начинаем их увеличивать. Одну из последовательностей Петя вычеркивает. Наша задача увеличвать последовательности так, чтобы всегда имелась запасная.

(41) Почему? Есть 3 равноценные группы крестиков и где убирать  из без разницы.

(43) их* (крестики)

Имея две последовательности вида: ХХ_ХХ_Х_ХХ (как вариант ХХ_ХХ_ХХ_Х) Васся выигрывает при любом ходе Пети.

Чтобы получить две последовательности ХХ_ХХ_Х_ХХ, надо иметь четыре последовательнсти ХХ_ХХ_Х_Х_ (возможны различные варианты)
И так далее. Получается:

ХХ_ХХ_Х_ХХ 2шт
ХХ_ХХ_Х_Х_ 4шт
_Х_ХХ_Х_Х_ 8шт
_Х_Х__Х_Х_ 16шт

Итого n=175. n можно уменьшить за счет уплотнения, но не сильно.

Сорри поправка.

Имея две последовательности вида: ХХ_ХХ_Х_ХХ (как вариант ХХ_ХХ_ХХ_Х) Вася выигрывает при своем ходе.

Создавая две последовательности
ХХ_ХХХХ_ХХ (как вариант ХХ_ХХХХХ_Х)

(46) без разницы - 2 последовательности с количеством крестиков 7 из 10ти на своем ходу

(18) Наконец то решил почитать что пишут другие :). Отличная идея!! Несколько замечаний:

1) >>За первые 40 шагов заполним прямоугольник через 1 крестик.
х х х х х х х х х х х х х х х х х х х х х х х х х х х х ...

Петя может не дать построить такое.  Так что придется использовать n=90. В 8-ми из 9-ти кусков по 10 клеток мы всегда сможем построить Х_Х_Х_Х_Х_.

2) Концы одной пары двух соседних последовательностей из 10 ячеек можно соединить. Тем самым получить n=89.

(48) Петя не может не дать выстроить последовательность "через один крестик". При чем любой длины.

(49) но он может противостоять конкретной стратегии увеличив время построения 40+ крестиков в два раза

(49) "через один крестик" мы хотим получить перед ходом Васи, после хода Пети. Пятя не обязан удалять крестики с краю. Он может удалять крестики в середине. Тогда у нас получится две последовательности "через один крестик" а не одна.

(49) Скажем Петя упорно будет удалять крестики в районе 35-й ячейки. Тогда 80 ячеек нам не хватит.

(50) Ему (Пете) придется это сделать, т. к. в условии не сказано, что Петя может за свой ход вообще ничего не стирать.
Время построения "через один крестик" зависит только от длины такого построения, но не от действий Пети.

(51) Вася за ход ставит _два_ крестика.

(52) А Вася упорно будет за свой ход один из двух крестиков ставить в районе 35-й ячейки...

(43) Что будет, если на 39-м ходу Петя удалит крестик в ячейке 21?

Интересно ТС сам-то знает решение :)?

(55) Вася построит бесконечную последовательность через один, но перед своим ходом крестик в ячейке 35 так и не увидит.

(58) Естественно.

(58) А что мешает Васе первым крестиком восстановить последовательность, а вторым сделать ход с краю, сделав _XX, вот из Петя и снесет своим ходом.

(60) из -> их :)

Кто напишет конфу этой для сетевой игры? ;)

(60) Двойных крестиков бояться в лес не ходить. Вася будет удалять крестик в ячейке 35, пока не увидит реальных угроз.

Блин извиняйте, конечно не Вася, а Петя.

(63) Не самая удачная тактика, так вообще потребуется 59 ячеек.
http://savepic.org/4962812.jpg

(65) В строке 28 можно удалять группу в ячейках 1,2,3

(66) Можно, как и сделано было в (35), но я же сделал по твоему совету "Вася будет удалять крестик в ячейке 35, пока не увидит реальных угроз." (63)

(67) Интересно как вы понимаете фразу "пока не увидит реальных угроз"? :)

(68) Ну мало ли, для кого какие угрозы реальны :)
В своих вариантах я считал что Петька будет стремиться затереть максимальное возможное число крестиков.

Согласно (42) у меня получилось, что сначала надо сделать 2 в степени (k-2) стартовых позиций и затем независимо от действий Пети довести ее по победного конца просто последовательно подрисовывая крестики.

То есть итоговое кол-во получается = (2 в степени (k-2))*k

проверил для k от 3 до 6. для 10 это будет 2560 клеток

может это и не минимум ...

кстати не совсем понятно - можно ли ставить крестики туда где раньше уже было зачеркнуто? если можно, то клеток можно использовать меньше

(71) Можно конечно.
Иначе достаточно вечеркивать каждый 10й крестик чтобы заблокировать поле любого размера.

(72) вообще-то в (70) написан алгоритм, который не зависит от того как будут вычеркивать крестики.

Вывел формулу для (37)

Количество полей: (2^(8-n) + 1), где n - размер поля.
Клетки, занимаемые полями: (КоличествоПолей * n)

Осталось выяснить какое расстояние надо оставить полями при первичной расстановке Х_Х_...
Возьмем максимум (без оптимизации), чтобы на ходу когда есть 2 последовательности
из 8 крестиков между последовательностями оставалась как минимум 1 пустая ячейка: 8_8
Клетки между полями: (КоличествоПолей - 1) * (9 - n)

Итого, формула: (2^(8-n) + 1) * n + ((2^(8-n) + 1) - 1) * (9 - n),
Сокращенно: n + 9*2^(8-n)

Ответ: 1159

(73) Да, согласен что возможность есть.
Применимо к моей формуле получается так:
Клетки между полями: КоличествоПолей * (11 - n)
Итого, формула: (2^(8-n) + 1) * n + (2^(8-n) + 1) * (11 - n)
Сокращенно: 11 + 11*2^(8-n)
т.е. получится 1419.

Рассчитал количество клеток для (46)
Получилось 16 таких последовательностей:
Х__Х__Х__Х
+ 15 клеток между ними.
10*16+15 = 175
... вроде так...

(76) Ошибся порядком:
ХХ_ХХХХ_ХХ 10*2+1
ХХ_ХХ_Х_ХХ 10*4+3
ХХ_Х__Х_ХХ 10*8+7
Х__Х__Х_ХХ 10*16+15
Х__Х__Х__Х 10*32+31
Итого 351

Закончил анализ для (39) - если Петя не затупит, то для сохранения прогресса возможен только симметричный подход (такой же как для всех остальных решений)

Количество полей получилось на один порядок более оптимальным чем для (46)
ХХХХХХХХХХ 10*1+0
ХХХ_ХХ_ХХХ 10*2+1
ХХХ_ХХ_Х_Х 10*4+3
Х_Х_ХХ_Х_Х 10*8+7
Х_Х_Х__Х_Х 10*16+15
10*16+15 = 175

Точнее на одну степень двойки.

+2 или +3 кстати, т.к. хитрый Вася все-же одно поле выпилит прежде чем Петя начнет составлять первые пары.
= 177/178.

У меня получилось, что Васе для победы достаточно n=59 ячеек.

(81) Почему и пример приведи...

(81) Я почему-то уверен, что если Петя будет правильно стирать ячейки, то Васе не хватит 59 ячеек.
Можем сыграть... )))

(81) А уверен я в этом потому, что моделировал несимметричные перестановки.

(83)
ХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХ
Ход Пети.

ХОХОХОХОХОХОХОХОХОХОХОХОХОХОХО_ОХОХОХОХОХОХОХОХОХОХОХОХОХОХ

ХОХОХОХОХОХОХОХОХОХОХОХОХОХОХО_ОХОХОХОХОХОХОХОХОХОХОХОХОХОХ
ХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХХХ

ХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХХХ
ХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХО___

ХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХО___
ХХХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХХХОООО

ХХХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХХХОООО
ХХХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОOOOОООО

ХХХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОOOOОООО
ХХХОХОХОХОХХХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХХХОOOOОООО

ХХХОХОХОХОХХХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХХХОOOOОООО
ХХХОХОХОХОOOOОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХХХОOOOОООО

ХХХОХОХОХОOOOОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХОХХХОOOOОООО
ХХХОХОХОХОOOOОХХХОХОХОХОХОХОХОХОХОХОХОХХХОХОХОХОХХХОOOOОООО
Вася построил 4 группы по 10 ячеек, в каждой 6 крестиков. Петя проиграл.
(ХХХОХОХОХО)OOOО(ХХХОХОХОХО)ХОХОХОХ(ОХОХОХОХХХ)(ОХОХОХОХХХ)ОOOOОООО

Предлагаю доиграть.
ХХХОХОХОХОOOOОХХХОХОХОХОХОХОХОХОХОХОХОХХХОХОХОХОХХХОOOOОООО
ХХХОХОХОХОOOOОХХХОХОХОХОХОХОХОХОХОХОХОOOOОХОХОХОХХХОOOOОООО

Ой обсчитался. 59 мало. После хода Васи должно быть 5 групп по 10 ячеек, в каждой 6 крестиков. Одну Петя уничтожит останется 4-е. Из них получится 2 группы с 7-ю крестиками. А из них одна с 8-ю крестиками.  
То есть надо n=65 ячеек. Ладно подробно опишу алгоритм, заодно все тщательно проверю.

(95) Ок).
Прием со сменой направления захвата ячеек мне понравился.
Возможно для моего алгоритма (основная часть Х_Х_Х__Х_Х) тоже подойдет...

Кстати, и вправду, таким подходом можно еще сократить количество ячеек.
Например, моим алгоритмом смоделировал за 80, но наверное можно и меньше (там видно что остался запас).
http://imageshack.com/a/img826/5990/m9t7.jpg

Собственно, алгоритмом (37) за 59 клеток:
http://imageshack.com/a/img812/2874/qsvi.jpg

Хотя в моем случае 1й ходил Вася, а должен был Петя, возможно это 60 или 61 клетка (при условии что достигнута максимальная степень сжатия).

сто

Вроде как Васе для победы хватает 69 ячеек.
http://www.imageup.ru/img170/1634381/krestiki.jpg

(101) почти. осталось немного до 68 (65 игра + 3 для поля).

+ (102) В (101) пожно первую группу для удаления построить из 2-х крестиков, а не из 3-х.

(98) Разобрался в вашем алгоритме. Васе для победы достаточно 57 ячеек!
Вот примерный вариант. В каждой строке ход Пети.
_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_
ХХ_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_
__ХХ_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_ХХ
____ХХ_Х_Х_Х_Х_Х_Х_Х_Х_ХХХ_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_ХХ
____ХХ_Х_Х_Х_Х_Х_Х_Х_ХХ___ХХ_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_ХХ
Два различных варианта ходов Пети.
____ХХ_Х_Х_Х_Х_Х_Х_ХХ_____ХХ_Х_Х_Х_Х_Х_Х_ХХХ_Х_Х_Х_Х_Х_ХХ
____ХХ_Х_Х_Х_Х_Х_Х_Х_ХХ_____ХХ_Х_Х_Х_Х_Х_ХХХ_Х_Х_Х_Х_Х_ХХ

(104) Не прокатит - ходить Петя не так должен - оба варианты не правильные.

____ХХ_Х_Х_Х_0_Х_Х_Х_ХХ___ХХ_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_ХХ

И конструкция вся ломается.

Не ломается!
____ХХ_Х_Х_Х_0_Х_Х_Х_ХХ___ХХ_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_Х_ХХ
____ХХ_Х_Х_Х_Х_Х_Х_Х_ХХ___ХХ_Х_Х_Х_Х_Х_Х_ХХХ_Х_Х_Х_Х_Х_ХХ
Идея почерпнута из (98)

Конструкции
ХХ_Х_Х_Х_Х_Х_Х_Х_ХХ
ХХХ_Х_Х_Х_Х_Х_ХХ
не ломаются.

Поправка
Конструкции
ХХ_Х_Х_Х_Х_Х_Х_ХХ (6 одиночных крестиков)
_ХХХ_Х_Х_Х_Х_Х_ХХ (5 одиночных крестиков)
не ломаются.

В (98) Есть конструкция
Х_Х_ХХ_Х_Х_Х_ХХ_Х

(106) Продолжим?
____ХХ_Х_Х_Х_Х_Х_Х_Х_ХХ___ХХ_Х_Х_Х_Х_Х_Х_000_Х_Х_Х_Х_Х_ХХ
____ХХ_Х_Х_Х_Х_Х_Х_Х_ХХ___ХХ_Х_Х_Х_Х_Х_Х_____Х_Х_Х_Х_Х_ХХ

____ХХ_Х_Х_Х_Х_Х_Х_Х_ХХ___ХХ_Х_Х_Х_Х_Х_Х_____Х_Х_Х_Х_Х_ХХ
____ХХХХ_Х_Х_Х_Х_Х_ХХХХ___ХХ_Х_Х_Х_Х_Х_Х_____Х_Х_Х_Х_Х_ХХ

____ХХХХ_Х_Х_Х_Х_Х_0000___ХХ_Х_Х_Х_Х_Х_Х_____Х_Х_Х_Х_Х_ХХ
____ХХХХ_Х_Х_Х_Х_Х________ХХ_Х_Х_Х_Х_Х_Х_____Х_Х_Х_Х_Х_ХХ

____ХХХХ_Х_Х_Х_Х_Х________ХХ_Х_Х_Х_Х_Х_Х_____Х_Х_Х_Х_Х_ХХ
____ХХХХ_Х_Х_Х_Х_Х________ХХХХ_Х_Х_Х_Х_Х_____Х_Х_Х_Х_ХХХХ

(111) тут ступил.
____ХХХХ_Х_Х_Х_Х_Х_ХХХХ___00_Х_Х_Х_Х_Х_Х_____Х_Х_Х_Х_Х_ХХ
____ХХХХ_Х_Х_Х_Х_Х_ХХХХ______Х_Х_Х_Х_Х_Х_____Х_Х_Х_Х_Х_ХХ

Пока сдаюсь :) Может и 57 достаточно :)

(113) (114) -

(112)
____0000_Х_Х_Х_Х_Х________ХХХХ_Х_Х_Х_Х_Х_____Х_Х_Х_Х_ХХХХ
_________Х_Х_Х_Х_Х________ХХХХ_Х_Х_Х_Х_Х_____Х_Х_Х_Х_ХХХХ

Просто показать как разыгрываются подобные констукции.
____ХХХХ_Х_Х_Х_Х_Х_ХХХХ______Х_Х_Х_Х_Х_Х_____Х_Х_Х_Х_Х_ХХ
____ХХХХХХ_Х_Х_Х_ХХХХХХ______Х_Х_Х_Х_Х_Х_____Х_Х_Х_Х_Х_ХХ

_________Х_Х_Х_Х_Х________ХХХХ_Х_Х_Х_Х_Х_____Х_Х_Х_Х_ХХХХ
_________Х_Х_Х_Х_Х________ХХХХХХ_Х_Х_Х_Х_____Х_Х_Х_ХХХХХХ

(118) согласен 10-ка получениется

(104) А может в 53 уложиться?
http://savepic.org/4966299.jpg

может до пятницы подождать?

(120) Хм... На первый взгляд решение корректное.

(120) Нашел ошибку!! Вы использовали 51 ячейку!

1. Важная промежуточная цель Васи построить 5 групп по 6 крестиков в каждой. В свете (120) для этого требуется 25 крестиков.
2. Количество крестиков не может быть больше пустых ячеек боле чем на 2.
3. Отсюда количество ячеек достаточное для победы Васи не может быть меньше чем 23+25=48. Скорее всего этот предел не достижим. Есть основания полагать, что 51 ячейка это минимум.

(123) Точно, сам себя обсчитал... :)

"..я хренею с вас, дорогая редакция.." - пишет нам девочка Маша. и мы ей верим!!!

откуда вас столько умных... ;-)

(120) Строка 28. Надо удалять группу в ячейках 27,28. Тогда Петя отбивается. 51 ячейка мало, а вот 53 вполне хватает.