Một "trò chơi Markov"
Tôi gọi các trò chơi tương tự như trò chơi mà tôi mô tả dưới đây là trò chơi Markov. Tôi chỉ đang chọn một hoặc đúng hơn là một loạt trò chơi 1 tham số. Thử thách mở là tìm ra người chơi nào$\ 0\ $ hoặc là $\ 1\ $ có chiến lược chiến thắng cho mỗi thông số nhất định $\ W.$
LƯU Ý $\ n\%2=0\ $ cho $\ n\ $ thậm chí, và $\ n\%2=1\ $ cho $\ n\ $ lẻ;
Để cho $ d(0)=J(0)=0.\ $ Đối với số nguyên dương tùy ý $\ n,\ $ người chơi $\ n\%2\ $ chọn một số nguyên dương $\ d(n)\le d(n-1)+1;\ $ sau đó $\ J(n)=J(n-1)+d(n).$
Khi người chơi cạnh tranh trong trò chơi $\ M(W),\ $ Ở đâu $\ W\ $ là một số nguyên dương cố định tùy ý, sau đó người chơi nhận được chính xác $J(n)=W\ $ chiến thắng.
Để cho $\ \omega(W)=0\ $ nếu người chơi $0$ có một chiến lược chiến thắng tại $M(W);\ $ nếu không hãy để $\ \omega(W)=1\ $ nếu người chơi $1$ có một chiến lược chiến thắng tại $M(W)$.
VẤN ĐỀ: Tính toán hàm$\ \omega:\mathbb N\to\{0\ 1\}.$
Ví dụ: $\ \omega(1)=1;\ \omega(2)=\omega(3)=0;\ \omega(4)=1, $ vv Tuy nhiên, $\ \omega(120)\ $ hoặc là $\ \omega(5553)\ $ khó hơn một chút (và tôi không biết).
Trả lời
Câu trả lời không thay đổi nhiều với những con số lớn hơn.
Câu trả lời đầy đủ là $$ \omega(W)=\left\{ \begin{array}{ll} 1, & W\%5=1,4\\ 0, & W\%5=0,2,3 \end{array}\right. $$
Hãy để chúng tôi nói vị trí đó $(W-J,d)$ chiến thắng nếu người chơi $n\%2$ có một chiến lược chiến thắng cho trò chơi $M(W)$ đến lượt anh ấy $n$ với $d(n)=d,J(n)=J$. Mặt khác nó đang mất đi. Rõ ràng, nó thực sự chỉ phụ thuộc vào sự khác biệt$W-J$.
$(i,d)$ có thắng không, có tồn tại thua không $(j,f)$ st $j+f=i,f\le d+1$. Chúng tôi quan tâm đến việc$(W-1,1)$ đang chiến thắng.
Đối với điều này, chỉ cần xem xét là đủ $(i,d)$ với $d\le 3$.
Mẫu trông như thế này:
$ \begin{array}{ccc} - & - & -\\ + & + & +\\ + & + & +\\ - & + & +\\ + & + & +\\ - & - & -\\ \vdots & \vdots & \vdots \end{array} $
Để xem nó, hãy chú ý:
- $(0,d)$ đang thua cho tất cả $d$, tức là hàng đầu tiên được lấp đầy bởi $-$'S
- nếu $(i,d)$ đang chiến thắng, sau đó $(i,d+1)$ đang chiến thắng, tức là bên phải $+$ luôn luôn là một $+$
Chúng tôi đã có câu trả lời đầy đủ từ @JosephGordon, người đã chứng minh tính chu kỳ của $\ \omega,\ $ độ dài của khoảng thời gian là 5. Joseph - cảm ơn rất nhiều!
Hãy để tôi viết một giải pháp mà ít nhất đối với tôi là dễ thực hiện hơn.
Hãy nhớ rằng người chơi $\ \omega(n)\ $ là người có chiến lược chiến thắng trong trò chơi Markov $\ M(n).$
Định lý Với mọi số nguyên dương$\ n\ $ hai thuộc tính sau giữ:
Người chơi $\ \omega(n)\ $ có thể thắng mọi trò chơi của $\ M(n)\ $ bằng cách chọn tất cả các động thái của riêng họ sao cho $\ d(k)\le 3;$
$\ \omega(n+5) = \omega(5).\ $
Proof chơi$\ \omega(n)\ $, khi chơi trò chơi $\ M(n+5)\ $, có thể đến vị trí $\ n\ $ trong khi sử dụng các bước di chuyển như vậy $\ d(k)\le 3\ $mỗi lần. Đặc biệt,$\ d(t)\le 3\ $ khi nào $\ J(t)=n.\ $ Vì vậy, bây giờ chúng tôi chỉ có bốn phần mở rộng của trò chơi:
$\ d(t+1)=4.\ $ Sau đó, người chơi $\ \omega(n)\ $ vở kịch $\ d(t+2)=1\ $ và chiến thắng (kể từ khi $\ J(t+2)=n+5\ \text{and}\ t+2\equiv t\mod 2)$;
$\ d(t+1)=3.\ $ Sau đó, người chơi $\ \omega(n)\ $ vở kịch $\ d(t+2)=2\ $ và chiến thắng;
$\ d(t+1)=2.\ $ Sau đó, người chơi $\ \omega(n)\ $ vở kịch $\ d(t+2)=3\ $ và chiến thắng;
$\ d(t+1)=1.\ $ Sau đó, người chơi $\ \omega(n)\ $ vở kịch $\ d(t+2)=1;\ $ sau đó người chơi khác chơi $\ d(t+3)= 1$ hoặc là $2\ $và người chơi $\ \omega(n)\ $ vở kịch $\ 2$ hoặc là $1\ $ và thắng.
Phần còn lại chính thức của lập luận là hoàn toàn thường xuyên và hiển nhiên. Kết thúc PROOF.
Mô tả bằng số hoàn chỉnh về $\ \omega\ $ được cho bởi định lý trên và ban đầu $5$ giá trị:
$$ \omega(1)=1;\,\ \omega(2)=\omega(3)=0;\,\ \omega(4)=1, \,\ \omega(5)=0 $$
Ví dụ, $\ \omega(5)=0\ $ bởi vì J (1) = 1, thì trình phát $0$ có thể chơi d (2) = 1, tức là J (2) = 2, sau đó - sau khi người chơi di chuyển $0$ -- người chơi $\ 0\ $ sẽ chơi $\ J(4)=5.$