ТУРНИР !!!, теория игр и не только... Опции Рейтинг

[Крантец]

Правила:
1. Не пишем в теме мыслей по решению, только вопросы по условию.
2. Ответы отправляем мне в личку до 1 августа. Присылать можно задачи по отдельности. Можно многократно отвечать на ту же задачу, но при этом я учту ТОЛЬКО ПОСЛЕДНЕЕ решение. Если хотите внести изменение в предыдущее решение, то отправьте полностью исправленное решение, а не указание, что и где заменить и т.д.
3. Обсуждения не будет- это турнир. Поэтому настоятельно прошу максимально подробно и аргументированно отвечать на вопросы задач. Я оставляю за собой право задавать уточняющие вопросы по вашему решению, но исправить/изменить присланный вариант нельзя в любом случае.
4. В некоторых задачах необходима картинка. Лучше отправить графику, нежели попытаться объяснить на словах или еще как-то. Мне достаточно ссылки.
5. Некоторые вопросы задач я и сам не решил пока При этом я вполне допускаю, что они могут и не иметь решения, поскольку большую часть задач я формулировал сам.
6. Занявший первое место будет поощрен мозгобаксами. В зависимости от ответов призы могут получить также 2-е и 3-е места. 1-е место - не менее 10- МБ. Как-то так.
7. В углу есть "голосовалка". Прошу всех проголосовать, чтобы я составил мнение о целесообразности проведения подобных мероприятий в дальнейшем. Материал и задумки у меня есть
8. Прошу прощения за безобразные картинки. Аккуратность - не мой конек.
9. Модераторы принимают участие на общих основаниях, только призы (в случае победы, естественно) для них предусмотрены другие.

Условия:
1. На доске nхn расставлены фишки, по одной на каждой клетке. Игрок имеет право убрать с доски несколько фишек, стоящих строго подряд на одной горизонтали или вертикали. Проигрывает тот, кто берет последнюю фишку. Играют двое. Существует ли выигрышная стратегия (если да, то для кого) при:
а) n=3
б) n=4
в) n=5

2. На окружности отмечено n точек. Игрок в свой ход соединяет две любые точки отрезком своего цвета таким образом, чтобы отрезки, проведенные им, не образовывали треугольник с вершинами в начальных точках. Проигрывает тот, кто не может сделать ход. Существует ли выигрышная стратегия (если да, то для кого) при:
а) n=4
б) n=5
в) n=6
г) n=7 ?

3. На решетке n х n (n- количество узлов, не клеток!) два игрока по очереди отмечают один узел своим цветом. Проигрывает тот, чьи точки образуют хотя бы один квадрат (являются его вершинами). При этом квадрат может располагаться под любым углом и быть любого размера. Возможна ли ничья при:
а) n=5
б) n=6
в) n=7
г) любых n> 7 ?
д) существует ли выигрышная стратегия в данной игре? Если да, то, для каких n и для кого из игроков?

4. В квадрате провели диагонали и соединили середины противоположных сторон. Получилось 9 точек, соединенных 16-ю отрезками. Играют двое, у каждого по три фишки своего цвета. Игроки по очереди ставят свою фишку на свободную точку. Когда на решетке выложены все 6 фишек, игроки по очереди передвигают одну из своих фишек на соседнюю точку по одному из 16-ти отрезков. Цель: поставить свои фишки на одну прямую. Существует ли выигрышная стратегия (если да, то для кого) ?

5. Есть кучка из 2n+1 камня. Двое по очереди берут из нее любое количество камней от 1 до m. После того, как разобраны все камни, проигрывает тот, у кого окажется нечетное число камней. Существует ли выигрышная стратегия (если да, то для кого) при:
а) n= 30 m=3
б) произвольных значениях n и m
в) изменении условия поражения на обратное: проигрывает тот, у кого четное число камней

6. Двое играют в «Морской бой» на поле n х n. У каждого только по одному четырехпалубному кораблю, но у первого прямоугольный корабль 4х1, а у второго корабль произвольной формы. Какое минимальное количество выстрелов потребуется каждому игроку, чтобы гарантированно ранить вражеский корабль, если:
а) n=7 б) n=10

7. Есть набор из девяти карточек со словами : кит, пар, луг, рок, гнет, мат, улица, кум, грим. Двое играют в следующую игру: берут по очереди любую из карточек. Цель: набрать три карточки со словами, содержащими общую букву. Существует ли выигрышная стратегия (если да, то для кого) ?

8. Известно, что в классических крестиках-ноликах на доске 3х3 ни у одного из игроков нет выигрышной стратегии. Предположим, что доска может быть произвольной формы. При каком минимальном количестве клеток произвольной доски появляется выигрышная стратегия у одного из игроков? Привести пример доски, описать стратегию и обосновать минимальность при условии, что для победы надо выстроить ряд из:
а) трех крестиков или ноликов
б) четырех крестиков или ноликов

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


10. Двое играют в крестики-нолики на необычной доске, показанной на рисунке. Цель, как и в обычной игре: поставить на одной линии 3 крестика или нолика. Существует ли выигрышная стратегия (если да, то для кого) ?

Сообщение было отредактировано Крантец: 3.8.2012, 16:26

[panda-pandus]

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

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

[Крантец]

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

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

1. Доказательство приветствуется
2. Корабль связный, то есть прямой, Г-образный, квадрат или зигзаг. Как в тетрисе по диагонали не считается.
3. Чем меньше выстрелов- тем лучше.
4. Эта задача не на стратегию! Можно переформулировать: на доске находится...за какое мин. число...? То есть не учитываем очередность ходов !!! Это здесь неважно.

К задаче №8:
поле должно состоять из клеток, причем каждая из них имеет общую сторону минимум с одной другой !
Успехов!

[losse_narmo]

Вопросы по условию (далее цифры по номерам задач):
1) "убрать несколько фишек, стоящих строго подряд" = "убрать 1 или более стоящих строго подряд фишек"?

3) "Возможна ли ничья"
а) ничья - все узлы раскрашены и при этом не появилось ни одного квадрата?
б) возможна ли ничья при условии, что игроки в кооперативе хотят ее создать? или возможна ли ничья если оба игрока хотят выиграть/не проиграть?

4) Если в процессе выставления фишек сразу получается линия, то игрок победил за "0 ходов"?

8) отправил вопрос в личку

9) "Цель: соединить противоположные стороны доски линией своего цвета"
- имеется ввиду, что должно быть соединение либо по горизонтали либо по вертикали точек твоего цвета?
- пересечения запрещены?

Часть вопросов возможно покажется очевидной, но я для успокоения что нету подводных камней=)

[Крантец]

Вопросы по условию (далее цифры по номерам задач):
1) "убрать несколько фишек, стоящих строго подряд" = "убрать 1 или более стоящих строго подряд фишек"?

3) "Возможна ли ничья"
а) ничья - все узлы раскрашены и при этом не появилось ни одного квадрата?
б) возможна ли ничья при условии, что игроки в кооперативе хотят ее создать? или возможна ли ничья если оба игрока хотят выиграть/не проиграть?

4) Если в процессе выставления фишек сразу получается линия, то игрок победил за "0 ходов"?

8) отправил вопрос в личку

9) "Цель: соединить противоположные стороны доски линией своего цвета"
- имеется ввиду, что должно быть соединение либо по горизонтали либо по вертикали точек твоего цвета?
- пересечения запрещены?

Часть вопросов возможно покажется очевидной, но я для успокоения что нету подводных камней=)

1) Да. Одну можно, безусловно, убирать.
3) а) Да, хотя об этом я как раз и хотел умолчать изначально
б) ответ на этот вопрос, боюсь, таится в моем вопросе о наличии/отсутствии выигрышной стратегии. Поясню: в а) исследуется принципиальная возможность ничьей.
4) а игроки предоставят друг другу такую возможность?
8) тут никакого секрета: рассматривается именно плоское решение
9) пересечения запрещены, соединить надо любой непрерывной ломаной линией.
Спрашивайте, дабы не было никаких недоразумений

[losse_narmo]

4) а игроки предоставят друг другу такую возможность?

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

Например, после 3 ходов возникла ситуация, изображенная на левом рисунке. Если после 6 ходов возникнет ситуация на правом рисунке это "желтый проиграл" или "красный обязан сделать ход и разрушить выигрышную структуру"?

[Крантец]

Задачи каждого игрока:
1) не позволить противнику в предварительном выкладывании построить выигрышный ряд
2) выкладывать фишки с учетом последующих возможных перемещений, как своих, так и оппонента.

Ваш правый вариант невозможен, поскольку один бы уже выиграл(тот, кто первым построил ряд). То есть игра идет до первого ряда.

[losse_narmo]

То есть игра идет до первого ряда.

Вот=) именно так и надо было мне вопрос сразу формулировать) Все ясно, спасибо)

[Крантец]

Вот=) именно так и надо было мне вопрос сразу формулировать) Все ясно, спасибо)

Иначе было бы проще, по-моему Но и нуднее, правда...

[Крантец]

ставки повышаются- 15 мб минимум. Инфляция Никто не застрахован от дальнейшего повышения. Также продумываю сейчас альтернативные варианты реализации мегабаксов. Надеюсь, что в ближайшее время за данную валюту можно будет приобрести нечто более привлекательное, нежели только ВИП...

[Крантец]

У меня две новости, причем обе хорошие:
1. Призовой фонд увеличился до 40 МБ. Один из пользователей сайта перечислил деньги в турнирный фонд. К сожалению, он пожелал остаться неизвестным. Я обещал не выдавать его имя. Средств он перечислил больше, при этом оговорив, что я могу их использовать как в этом, так и в последующих турнирах.
2. Через несколько дней за МБ можно будет приобрести головоломки. Таким образом, за данную валюту можно будет купить и товары и услуги (ВИП). Подробности альтернативного использования сайтовской валюты чуть позже.

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

[Крантец]

Друзья! Первая партия головоломок у меня. Их, как я и обещал, можно будет приобрести за МБ. На данный момент имеются:
1. головоломки- расцепляйки из металла.
2. Шахматы карманные (размер 12 смх 12см)
3. Китайские шашки
Цена любой единицы- 3 МБ+ почтовые расходы. В ближайшее время можно будет реализовать ТОЛЬКО мегабаксы, полученные за участие в моих турнирах- далее посмотрим. Порядок такой:
1. Переводите на меня МБ, попросив Black`а
2. Пишите мне в личку, что переслали столько-то, хотите получить то-то. При этом указываете адрес доставки.
3. Получаете заказ, оплачиваете доставку на почте.

Смысл данного проекта: помочь сайту. И еще: через некоторое время проведу турнир для ВИП-пользователей. Детали сейчас продумываю. Предварительно: участвовать смогут все, но призы только ВИПам. Условия могу и пересмотреть, отчасти это зависит от итогов настоящего турнира. Однако призываю всех обзавестись статусом ВИП заблаговременно

Жду ответы !

[UNDEFEAT]

Эх, жаль что времени на задачи совсем нету

[Крантец]

Эх, жаль что времени на задачи совсем нету

Надо изыскивать ! Не успеешь оглянуться. еще один подоспеет

[MrArcimed]

1. Клетки, клетки, клетки - Как в метрополитене вагонетки.
2. Китайские шахматы.
3. Ну Вы и МегаМОЗГИ...

[Крантец]

1. Клетки, клетки, клетки - Как в метрополитене вагонетки.
2. Китайские шахматы.
3. Ну Вы и МегаМОЗГИ...

Вы о чем?

[Крантец]

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

[Крантец]

Итоги подведены. Победитель- panda-pandus . он получает обещанные 40 мозгобаксов. Однако, много заданий данного турнира не решил никто. Поэтому продолжаем решать следующие задания:

1. б) в)
2. б) в) г)
3. все пункты.
5. все пункты.
8. б)
9. участники доказали, что выигрышная стратегия существует, но никто не описал ее. Действуем!

Некоторые решения премирую мозгобаксами, как обычно Успехов!

[VitalyKolobkov]

Итоги подведены. Победитель- panda-pandus . он получает обещанные 40 мозгобаксов. Однако, много заданий данного турнира не решил никто. Поэтому продолжаем решать следующие задания:

1. б) в)
2. б) в) г)
3. все пункты.
5. все пункты.
8. б)
9. участники доказали, что выигрышная стратегия существует, но никто не описал ее. Действуем!

Некоторые решения премирую мозгобаксами, как обычно Успехов!

Я не решал турнир, но возник вопрос: почему ни одна из этих задач не на сайте?

[Крантец]

Потому что данные задачи интересны только мне из модераторов Так что у них нет шансов.

З.Ы. В смысле, у задач, конечно же, нет шансов, а не у модераторов Скоро уж совсем как Черномырдин буду изъясняться

Сообщение было отредактировано Крантец: 1.8.2012, 21:28