2014 dxdy logo

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

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




 
 Стратегия игры
Сообщение22.12.2008, 20:47 
Аватара пользователя
Три разумных игрока (каждый действует наиболее
выгодным для себя образом) Алекс, Боря и Витя берут камни
из кучи по кругу.Каждым ходом игрок может взять 1 или 2
камня. Вначале в куче 5769 камней. Алекс делает первый ход,
Боря второй, а Витя третий.
Игрок, забирающий последний камень, получает выигрыш в
размере 10 долларов, следующий за ним по кругу 1 доллар, а
оставшийся игрок ничего. (Например, если Алекс забирает
последний камень, он получает 10 долларов, а Боря получает
1 доллар.) Игрокам запрещено разговаривать перед игрой или
в процессе игры. Кто выиграет?

 
 
 
 
Сообщение23.12.2008, 02:46 
Аватара пользователя
Пусть $f(n)=0, 1$ или $2$ в зависимости от того, какой игрок по счету от начинающего выигрывает при оптимальной игре с $n$ камнями.
Тогда
$$f(n) = \begin{cases}
0, & \text{если}\, f(n-1)=2\, \vee\, f(n-2)=2;\\
2, & \text{если}\, (f(n-1)=1 \wedge f(n-2)\ne 2)\,\vee\,(f(n-2)=1 \wedge f(n-1)\ne 2);\\
1, & \text{иначе}
\end{cases}$$
с начальными значениями $f(1)=f(2)=0.$

Или вот чуть более простая формула:
$$f(n) = \max\{ f(n-1), f(n-2) \} + 1\bmod 3$$

Отсюда нетрудно получить, что функция $f(n)$ при $n\geq 2$ имеет период 4 так, что если $n\equiv 1,2\pmod4$, то выигрывает начинающий (Алекс); если $n\equiv 3\pmod4$, то выигрывает следующий за ним (Боря), и наконец если $n\equiv 0\pmod4$, то выигрывает последний (Витя).

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group