|
Игра в камни | ☑ | ||
---|---|---|---|---|
0
Ненавижу 1С
гуру
29.07.11
✎
12:10
|
У Пети и Васи по N камней. Ходят по очереди, начинает Петя. За один ход разрешается передать противнику любое натуральное {больше нуля) число камней (разумеется, не больше, чем у игрока есть на данный момент), если только это число ещё не было передано одним из игроков. Проигрывает тот, кто не может сделать ход.
У кого из игроков есть выигрышная стратегия и как это зависит от N? |
|||
1
vicof
29.07.11
✎
12:11
|
угадал автора
|
|||
2
Ц_У
29.07.11
✎
12:14
|
Первый ход N/2
|
|||
3
Error pro
29.07.11
✎
12:15
|
Х\Ф Игры разума?
|
|||
4
Ненавижу 1С
гуру
29.07.11
✎
12:15
|
(2) если N -нечетное?
|
|||
5
Ненавижу 1С
гуру
29.07.11
✎
12:17
|
(2) если камней по 2
то по-твоему Петя отдает 1 камень, тогда Вася отдает 2, Петя вынужден только 3 отдать, Вася - 4, все Вася выиграл |
|||
6
Ц_У
29.07.11
✎
12:23
|
(5) Точно?
|
|||
7
Ненавижу 1С
гуру
29.07.11
✎
12:24
|
(6) для N=2 всегда выигрывает Вася
|
|||
8
Ц_У
29.07.11
✎
12:27
|
(7) так если у меня нет камней я не выиграл?
т.е. если ты мне отдал все свои камни и количество общее <> любому ходу, то я могу тебе их вернуть? |
|||
9
Wasya
29.07.11
✎
12:30
|
(0) Вася всегда выигрывает!
|
|||
10
vicof
29.07.11
✎
12:38
|
(9) +1
|
|||
11
otrix
29.07.11
✎
12:39
|
(9)не всегда.
например, n=3 П отдает 1 В. П=2, В=4 В отдает 4 П. П=6, В=0 П отдает 2 В. П=4, В=2. Вася проиграл |
|||
12
Ненавижу 1С
гуру
29.07.11
✎
12:39
|
(8) проиграл, если ход сделать не сможешь
|
|||
13
Ненавижу 1С
гуру
29.07.11
✎
12:41
|
(11) не согласен, после хода
П отдает 1 В. П=2, В=4 Вася делает ход В отдает 2 П. П=4, В=2 и в итоге Вася выиграл |
|||
14
Tatitutu
29.07.11
✎
12:41
|
||||
15
NS
29.07.11
✎
12:43
|
Ккакая-то слишком сложная задача. Она вообще решение (без перебора) имеет?
|
|||
16
otrix
29.07.11
✎
12:46
|
(9) Вася будет выигрывать всегда, если Петя отдает 1 камень в начале и Вася будет отдавать камни по-порядку - 2,4, 6 и т.д. Но вот это "если П отдает 1 камень сначала" - уже не стратегия(
|
|||
17
otrix
29.07.11
✎
12:48
|
(13) это понятно. говорилось о том, что Вася выигрывает при ЛЮБОМ раскладе. Я привела пример, что не при любом
|
|||
18
Ненавижу 1С
гуру
29.07.11
✎
12:50
|
(17) ты не понимаешь, у каждого из них есть желание выиграть и Вася просто таких ходов делать не будет
они играют ЖЕЛАЯ выиграть |
|||
19
otrix
29.07.11
✎
12:58
|
(18) (11) ответ на (9). что выиграть каждый хочет понятно. но выиграть может Вася - не всегда!
|
|||
20
Ненавижу 1С
гуру
29.07.11
✎
13:01
|
(19) Вася при N=3 выигрывает всегда, просто для случая (11) он не будет делать этот "дурацкий" ход после первого хода Пети, а сделает как в (13)
|
|||
21
otrix
29.07.11
✎
13:03
|
(20)без "дурацких" ходов - согласна. что-то я приципилась к слову всегда) а вообще задачка - супер! очень затягивает!
|
|||
22
Wasya
29.07.11
✎
13:11
|
Гипотеза. Если Вася будет отдавать минимально возможное число. Вроде как будет выигрывать. Надо тщательно проверить.
|
|||
23
otrix
29.07.11
✎
13:12
|
(22)+1!!!!
|
|||
24
Ненавижу 1С
гуру
29.07.11
✎
14:12
|
есть выигрышная стратегия для Васи, нашел!
но отличная от (22) |
|||
25
Wasya
29.07.11
✎
14:24
|
(24) Пусть N(i) количество камней у Васи после i хода Пети.
Тогда (по стратегии 22) N(i)>=N+i. При этом уже использовано 2*i-1 чисел. Так как N+i>2*i-1, тогда у Васи всегда будет в распоряжении хотя бы одно свободное число. |
|||
26
Ненавижу 1С
гуру
29.07.11
✎
14:26
|
Почему N(i)>=N+i ?
|
|||
27
Wasya
29.07.11
✎
14:29
|
(26) Вася отдает наименьшее возможное число, значит Петя на следующем ходе возвращает минимум на один камень больше.
|
|||
28
Ненавижу 1С
гуру
29.07.11
✎
14:40
|
(27) согласен, у меня сложнее решение
|
|||
29
Ненавижу 1С
гуру
29.07.11
✎
14:48
|
Второй выигрывает всегда. Его тактика:
Если первый передает 2k, то второй передает обратно 2k-1, если первый 2k-1, то второй 2k. То есть все ходы разбиваются по парам чисел (2k,2k-1), единственная проблема - всегда ли второй может походить? Это может случиться только в следующем случае: ему передали 2k-1, а он должен вернуть 2k. Когда он не сможет этого сделать? Когда у него до того как принял 2k-1 количество 0. Покажем, что такого быть не может при данной стратегии. За каждую пару ходов количество у второго игрока изменяется ровно на 1 (увеличиваясь или уменьшаясь). Первоначально было N, стало 0. Значит прошло минимум N пар ходов, то есть использовано 2N разных ходов, но их всего 2N, игра окончена после хода второго и первому попросту нечем ходить. |
|||
30
Jackman
29.07.11
✎
15:17
|
(0) В 8м классе в компьютерном кружке решал эту задачку на Фокале.
|
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |