\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\Z}{\mathbb{Z}}
\begin{center}
\vskip 1cm{\LARGE\bf
A Probabilistic Take-Away Game\\
}
\vskip 1cm
\large
Tony W.\ H.\ Wong and Jiao Xu\\
Department of Mathematics\\
Kutztown University of Pennsylvania\\
Kutztown, PA 19530\\
USA\\
\href{mailto:wong@kutztown.edu}{\tt wong@kutztown.edu}\\
\href{mailto:jxu399@live.kutztown.edu}{\tt jxu399@live.kutztown.edu}\\
\end{center}
\vskip .2 in
\begin{abstract}
Alice and Bob are playing a very simple game. Each of them starts with a pile of $n$ chips, and they take turns to remove $1$ or $2$ chips from their own pile randomly and independently with equal probability. The first player who removes all chips from their pile is the winner. In this paper, we find the winning probability for Bob and analyze a new integer sequence. We also show that this game is highly disadvantageous to the second player, which is counter-intuitive. Furthermore, we study several variations of this game and determine the winning probability for Bob in each case.\\
\end{abstract}
\section{Introduction}\label{intro}
Take-away games are mathematical games that involve two players, who take turns to remove items from a pile or multiple piles of objects. The winner is the first player achieving a certain predefined goal.
Here is a classical single-pile take-away game: Alice and Bob take turns to remove $1$ or $2$ chips from a pile of finitely many chips, with Alice going first. Whoever removes the last chip is the winner. Such a game and many variations are well-studied, for example by Schwenk \cite{schwenk}.
Another similar take-away game is the game of Nim. It involves multiple piles, and each player may remove one or more chips from one of the piles. Again, whoever removes the last chip is the winner. Berlekamp, Conway, and Guy \cite{bcg} as well as Bouton \cite{bouton} thoroughly discussed the strategies of this game.
In recent years, mathematicians revisited many well-studied deterministic problems in a probabilistic setting. In this paper, we begin with a basic version of a probabilistic take-away game: Alice and Bob each have a pile of $n$ chips, and they take turns to remove $1$ or $2$ chips from their pile, with Alice going first. Whether to remove $1$ or $2$ chips is decided by flipping a fair coin. In other words, every move is independent, and the probability of removing $1$ or $2$ chips is $\dfrac{1}{2}$ each. If there is only $1$ chip left in the pile, then it is removed with probability $1$ in the next move. The first player who removes all chips from their pile is the winner. Equivalently, the game can be played in the following manner: Alice and Bob start with no chips, and they take turns to collect $1$ or $2$ chips randomly and independently with equal probability. The first person who collects at least $n$ chips is the winner. This model of the game avoids the complication when there is only $1$ chip left, thus it is preferred and will be adopted in this paper.
Let $p_n$ denote the probability that Bob wins by collecting at least $n$ chips before Alice does. At first glance, one may suggest that $p_n=\dfrac{1}{2}$ since the game seems to be fair to both Alice and Bob. With more thought, one may realize that $p_n\leq\dfrac{1}{2}$ since Bob is in a disadvantageous position by having one fewer move half the time. It is also reasonable to predict that $p_n$ converges to $\dfrac{1}{2}$ as $n$ goes to infinity. In this paper, we study precisely what $p_n$ is for each $n$, and how this sequence behaves.
It is apparent that $p_1=0$, since Alice wins on the first move. When $n=2$, Bob can only win if Alice collects $1$ chip in her first move and Bob collects $2$ in his first move, implying that $p_2=\dfrac{1}{4}$. To study $p_n$ in general, we need some formal definitions.
Let $X_1,X_2,\dotsc,X_n,Y_1,Y_2,\dotsc,Y_n$ be independent identically distributed random variables such that $\P(X_i=1)=\P(X_i=2)=\P(Y_i=1)=\P(Y_i=2)=\dfrac{1}{2}$, where $X_i$ and $Y_i$ represent the number of chips collected by Alice and Bob in the $i$-th move respectively.
Before we proceed to derive the formula, let us first study the initial terms of $p_n$. As mentioned, $p_1=0$ and $p_2=\dfrac{1}{4}$. The following calculations find $p_n$ when $n=3,4,5,6,$ and $7$.
When $n=3$,
\begin{align*}
p_3 &= \P\big((X_1,X_2)=(1,1)\big)\cdot\P\big((Y_1,Y_2)=(1,2),(2,1),\,\text{or }(2,2)\big)\\
&= \dfrac{1}{4}\cdot\dfrac{3}{4}=\dfrac{3}{16}.
\end{align*}
When $n=4$,
\begin{align*}
p_4&=\P\big((X_1,X_2)=(1,1),(1,2),\,\text{or }(2,1)\big)\cdot\P\big((Y_1,Y_2)=(2,2)\big)\\
&+\P\big((X_1,X_2,X_3)=(1,1,1)\big)\\
&\cdot\P\big((Y_1,Y_2,Y_3)=(1,1,2),(1,2,1),(2,1,1),(1,2,2),\text{ or }(2,1,2)\big)\\
&=\frac{3}{4}\cdot\frac{1}{4}+\frac{1}{8}\cdot\frac{5}{8}=\frac{17}{64}.
\end{align*}
When $n=5$,
\begin{align*}
p_5&=\P\big((X_1,X_2,X_3)=(1,1,1),(1,1,2),(1,2,1),\text{ or }(2,1,1)\big)\\
&\cdot\P\big((Y_1,Y_2,Y_3)=(1,2,2),(2,1,2),(2,2,1),\text{ or }(2,2,2)\big)\\
&+\P\big((X_1,X_2,X_3,X_4)=(1,1,1,1)\big)\\
&\cdot\P\big((Y_1,Y_2,Y_3,Y_4)=(1,1,1,2),(1,1,2,1),(1,2,1,1),(2,1,1,1),(1,1,2,2),(1,2,1,2),\\
&\hspace{108pt}\text{or }(2,1,1,2)\big)\\
&=\frac{1}{2}\cdot\frac{1}{2}+\frac{1}{16}\cdot\frac{7}{16}=\frac{71}{256}.
\end{align*}
When $n=6$,
\begin{align*}
p_6&=\P\big((X_1,X_2,X_3)\neq(2,2,2)\big)\cdot\P\big((Y_1,Y_2,Y_3)=(2,2,2)\big)\\
&+\P\big((X_1,X_2,X_3,X_4)=(1,1,1,1),(1,1,1,2),(1,1,2,1),(1,2,1,1),\text{ or }(2,1,1,1)\big)\\
&\cdot\P\big((Y_1,Y_2,Y_3,Y_4)=(1,1,2,2),(1,2,1,2),(1,2,2,1),(2,1,1,2),(2,1,2,1),(2,2,1,1),\\
&\hspace{108pt}(1,2,2,2),(2,1,2,2)\text{ or }(2,2,1,2)\big)\\
&+\P\big((X_1,X_2,X_3,X_4,X_5)=(1,1,1,1,1)\big)\\
&\cdot\P\big((Y_1,Y_2,Y_3,Y_4,Y_5)=(1,1,1,1,2),(1,1,1,2,1),(1,1,2,1,1),(1,2,1,1,1),(2,1,1,1,1),\\
&\hspace{125pt}(1,1,1,2,2),(1,1,2,1,2),(1,2,1,1,2),\text{ or }(2,1,1,1,2)\big)\\
&=\frac{7}{8}\cdot\frac{1}{8}+\frac{5}{16}\cdot\frac{9}{16}+\frac{1}{32}\cdot\frac{9}{32}=\frac{301}{1024}.
\end{align*}
When $n=7$,
\begin{align*}
p_7&=\P\big((X_1,X_2,X_3,X_4)\neq(1,2,2,2),(2,1,2,2),(2,2,1,2),(2,2,2,1),\text{ and }(2,2,2,2)\big)\\
&\cdot\P\big((Y_1,Y_2,Y_3,Y_4)=(1,2,2,2),(2,1,2,2),(2,2,1,2),(2,2,2,1),\text{ or }(2,2,2,2)\big)\\
&+\P\big((X_1,X_2,X_3,X_4,X_5)=(1,1,1,1,1),(1,1,1,1,2),(1,1,1,2,1),(1,1,2,1,1),\\
&\hspace{146pt}(1,2,1,1,1),\text{ or }(2,1,1,1,1)\big)\\
&\cdot\P\big((Y_1,Y_2,Y_3,Y_4,Y_5)=(1,1,1,2,2),(1,1,2,1,2),(1,1,2,2,1),(1,2,1,1,2),\\
&\hspace{125pt}(1,2,1,2,1),(1,2,2,1,1),(2,1,1,1,2),(2,1,1,2,1),\\
&\hspace{125pt}(2,1,2,1,1),(2,2,1,1,1),(1,1,2,2,2),(1,2,1,2,2),\\
&\hspace{125pt}(1,2,2,1,2),(2,1,1,2,2),(2,1,2,1,2),\text{ or }(2,2,1,1,2)\big)\\
&+\P\big((X_1,X_2,X_3,X_4,X_5,X_6)=(1,1,1,1,1,1)\big)\\
&\cdot\P\big((Y_1,Y_2,Y_3,Y_4,Y_5,Y_6)=(1,1,1,1,1,2),(1,1,1,1,2,1),(1,1,1,2,1,1),(1,1,2,1,1,1),\\
&\hspace{141pt}(1,2,1,1,1,1),(2,1,1,1,1,1),(1,1,1,1,2,2),(1,1,1,2,1,2),\\
&\hspace{141pt}(1,1,2,1,1,2),(1,2,1,1,1,2),\text{ or }(2,1,1,1,1,2)\big)\\
&=\frac{11}{16}\cdot\frac{5}{16}+\frac{6}{32}\cdot\frac{16}{32}+\frac{1}{64}\cdot\frac{11}{64}=\frac{1275}{4096}.
\end{align*}
From these calculations, it seems that the denominator of $p_n$ is $4^{n-1}$. As for the numerator, we observe that the sequence $3,17,71,301,1275$ satisfies the recurrence relation $x_{n+2}=4x_{n+1}+x_n$. However, when we use these two observations to project $p_{100}$, we get $p_{100}\approx64.4353$, which is absurd since $p_n\leq1$. In other words, the pattern developed from small cases is not helpful, so we need to generalize our calculations to obtain a formula for $p_n$. Nevertheless, the fact that these five terms satisfy an elegant recurrence relation is interesting.
In Section \ref{basic}, we present a complete solution for this basic probabilistic take-away game. In Section \ref{seq}, we discuss two integer sequences obtained from this result. In Section \ref{general}, we extend our calculations to some general versions of this probabilistic take-away game. Finally, in Section \ref{furtherandopen}, we discuss some numerical computations and approximations of the probabilities, as well as some open questions.
\section{Results for the basic version}\label{basic}
Let $S_k=\sum_{i=1}^kX_i$, and $T_k=\sum_{i=1}^kY_i$. It is clear that
\begin{equation}\label{pn1}
p_n=\sum_{k=1}^n\big(\P(S_k0$.
\begin{lemma}\label{rk}
The probability that Bob wins the game is $\displaystyle\frac{1}{2}-\frac{1}{2}\sum_{k=1}^{\lceil\frac{n}{a}\rceil}r_k^2$.
\end{lemma}
\begin{proof}
Since
$\{S_k\geq n\text{ and }S_{k-1}