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

[Крантец]

Правила:
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

[Крантец]

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

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

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

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

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

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

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

[losse_narmo]

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

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

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