2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

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

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Игра, фишки, полоски
Сообщение08.07.2015, 18:24 


03/06/12
209
Помогите, пожалуйста, разобраться с задачей!
Даны полоска $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 фишек, которую второй игрок следующим ходом уберет. Пока что не очевидна потенциальная стратегия первого игрока.

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение08.07.2015, 18:39 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение08.07.2015, 18:43 


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

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

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение08.07.2015, 18:50 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение08.07.2015, 21:37 


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

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение08.07.2015, 22:05 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение08.07.2015, 23:17 


03/06/12
209
Я пока что не пойму все равно одну вещь.

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

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

1010000001111100001110010101011111111000011111100001111100111100010101

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

1010000000000100000010010101000000001000000000100000000100000100010101

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

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение08.07.2015, 23:26 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение08.07.2015, 23:40 


03/06/12
209

(Оффтоп)

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

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

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение08.07.2015, 23:52 
Заслуженный участник


12/09/10
1547
ole-ole-ole в сообщении #1034918 писал(а):
P.S. А разве из условия следует, что Второй игрок убирает не больше одного островка?

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

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение09.07.2015, 10:29 


03/06/12
209
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 ходов (при такой стратегии).

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

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение10.07.2015, 17:17 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение10.07.2015, 20:49 


03/06/12
209
Cash в сообщении #1035512 писал(а):
Общая идея правильная. Дело осталось за конкретными расчетами.

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

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение11.07.2015, 01:40 
Заслуженный участник


12/09/10
1547
Ну подумайте.

 Профиль  
                  
 
 Re: Игра, фишки, полоски
Сообщение11.07.2015, 14:56 


03/06/12
209
Все равно пока что не придумать(

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 47 ]  На страницу 1, 2, 3, 4  След.

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



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

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


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

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