Игра, фишки, полоски

[ole-ole-ole]

Помогите, пожалуйста, разобраться с задачей!
Даны полоска $1 × 1000$ и $n$ фишек. Два игрока ходят по очереди. Первый своим ходом может взять не более $17$ фишек (как из кучи, так и с клеток полоски) и поставить их на любые свободные клетки. Второй своим ходом может снять любое количество стоящих подряд фишек, и положить их обратно в кучу. Первый игрок выигрывает, если поставит все $n$ фишек в ряд без пробелов. Докажите, что если а) $n\le 89$; б) $n\le 98$, то первый игрок сможет выиграть. Докажите, что если в) $n > 324$; г) $n > 305$; д) $n > 98$, то второй игрок может помешать первому выиграть.

a) Ясно, что первому нужно будет не менее $\left[\dfrac{89}{17}\right]=5$ ходов. Мне кажется, что первый может сначала ставить все фишки через одну в полоску на нечетные места, чтобы не было подряд стоящих, но тогда поставив такую полосу, заполнив дырки четными местами, то есть поставив 17 фишек, будет полоска из 35 фишек, которую второй игрок следующим ходом уберет. Пока что не очевидна потенциальная стратегия первого игрока.

[Cash]

Давайте сперва для понимания игры примем такую стратегию второго игрока: он убирает как можно больше фишек. Как вы думаете, какая может быть позиция перед последним (выигрывающим) ходом первого?

[ole-ole-ole]

Cash в сообщении #1034737 писал(а):

Давайте для простоты примем такую стратегию второго игрока: он убирает как можно больше фишек. Как вы думаете, какая может быть позиция перед последним (выигрывающим) ходом первого?

Спасибо. 72 фишек с 17 дырками!

[Cash]

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

[ole-ole-ole]

Второму нужно снять как можно больше фишек, потому он оставит лишь отдельно стоящие после каждого своего хода.
Но это это же его может спасти, потому как он всегда сможет оставить фишки только на четных или только на нечетных местах после каждого своего хода. Или же имеется ввиду, что второй игрок не может несколько полосок снимать, а может снять только одну?

[Cash]

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

Четные-нечетные здесь не по делу.

[ole-ole-ole]

Я пока что не пойму все равно одну вещь.

Вот пусть $0$ -- пустая клетка, $1$ -- клетка с фишкой.

Пусть после некоторого хода первого игрока получилась вот такая комбинация

1010000001111100001110010101011111111000011111100001111100111100010101

Тогда второй игрок походит вот так:

1010000000000100000010010101000000001000000000100000000100000100010101

Ну а первому опять мучатся. Пока что не ясно -- как себя ведет второй игрок. Он же может все портить одним махом, как Мамай)

[Cash]

Первый игрок придерживается след. конфиурации:
111110111110111110111110...011111011111
Я здесь сделал островки по 5 фишек, но это не факт, что оптимально - просчитаете потом сами.
Второй игрок убирает не больше одного островка. А первый исправляет ситуацию и делает новые островки, а последним ходом заполняет пробелы.

[ole-ole-ole]

(Оффтоп)

Cash в сообщении #1034897 писал(а):

Первый игрок придерживается след. конфиурации:
111110111110111110111110...011111011111
Я здесь сделал островки по 5 фишек, но это не факт, что оптимально - просчитаете потом сами.
Второй игрок убирает не больше одного островка. А первый исправляет ситуацию и делает новые островки, а последним ходом заполняет пробелы.

Спасибо большое за то, что помогли, я уже не сегодня зайду, спать пора!
P.S. А разве из условия следует, что Второй игрок убирает не больше одного островка?

[Cash]

ole-ole-ole в сообщении #1034918 писал(а):

P.S. А разве из условия следует, что Второй игрок убирает не больше одного островка?

Второй своим ходом может снять любое количество стоящих подряд фишек

[ole-ole-ole]

Cash в сообщении #1034935 писал(а):

Второй своим ходом может снять любое количество стоящих подряд фишек

Спасибо, я как-то протупил

Cash в сообщении #1034897 писал(а):

Первый игрок придерживается след. конфиурации:
111110111110111110111110...011111011111
Я здесь сделал островки по 5 фишек, но это не факт, что оптимально - просчитаете потом сами.
Второй игрок убирает не больше одного островка. А первый исправляет ситуацию и делает новые островки, а последним ходом заполняет пробелы.

Если делать островки по 5 фишек, то желательно к последнему ходу, чтобы стояло 15 островов для первого игрока, иначе он не сможет походить.
Я кажется понял беспроигрышную стратегию первого игрока.
Он берет первым ходом ставит на места кратные $7$ фишки. Пусть будет $7k$
100000010000001....
Затем на $7k+1$, затем на $7k+2$, $7k+3$, $7k+4$. А все что испортит ему второй игрок, восстановит.

За каждый ход в первом случае (при 89 фишках) второй игрок не более чем 5 фишек испортит, то есть 12 фишек удастся поставить. А значит первому потребуется не более 8-9 ходов (при такой стратегии).

Верно ли рассуждаю?

[Cash]

Общая идея правильная. Дело осталось за конкретными расчетами.

[ole-ole-ole]

Cash в сообщении #1035512 писал(а):

Общая идея правильная. Дело осталось за конкретными расчетами.

А как мы можем произвести рассчеты? Ведь у второго игрока может быть очень много вариантов для ходов. Я здесь лишь вижу описание стратегии. Что-то не пойму пока что

[Cash]

Ну подумайте.

[ole-ole-ole]

Все равно пока что не придумать(