Имя: Пароль:
IT
 
Игра в камни
, , ,
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м классе в компьютерном кружке решал эту задачку на Фокале.