VOL. 61, NO. 5, DECEMBER
1988
301
How to Beat Your
Kids at Their Own Game
KENNETH M. LEVASSEUR
University
of Lowell
Lowell, MA 01852
1.
Introduction. The first game that my children
learned, as two-year olds, was "Red
or Black,"
in
which
they
tried to
guess
the color of the
top card
in
a deck. The top
card is removed from the deck after each
guess
and the game ends when the deck is
empty.
Your score
is
the number of correct
guesses
that you make. We assume that a
child's
strategy
is that he or she
randomly
guesses
red or
black for each card, not
taking
into account
the colors of cards that have been removed
from the deck.
A
child
would then have
an
expected
score of 26 for a standard deck. The most elementary
form of card
counting
can be used to increase the
expected
score.
If
there
are more
cards
remaining
of one
color,
then that color should be
guessed next.
A
question
that
is immediately posed
is:
Using
card counting, what is the expected score for a
standard
52 card deck?
Or
more
generally:
Using
card
counting,
what is the
expected
score, S(n),
for
a
deck
of
n
red and
n
black cards?
2. Game paths, expected score, and diagonal
crossings. Each game of "Red or Black"
can be viewed as
a
decreasing path through
lattice
points starting
at
(n, n)
and
ending
at
(0, 0) (see
FIGURE
1).
At each
point
in
the
path,
the first coordinate
represents the
number of
red cards left
in
the deck and the second coordinate
represents
the number of black cards. Each
step
in
the
path corresponds to the
removal
of one card from the
deck;
therefore exactly one of the coordinates decreases
by
one
in
each
step. Any
such
path
will
be called a
game path.
A
paradoxical aspect
to
counting
cards
in
"Red or Black" is that the expected score
grows proportionally
with the number of times that card counting gives no informa-
tion. Those situations
occur on the
diagonal:
red
=
black.
Suppose
that we started at
(n, n)
and that the first card
in
the deck is black. We can
assume
that this first card
contributes
1/2
to our
expected
score. Now
suppose
that our
game path
meets the
black
/
if next card
is
red
(r- 1b)
(,
4
if next card is black
(r,b-
1)
, red
FIGURE
1
This content downloaded from 129.16.69.49 on Mon, 28 Dec 2015 08:34:58 UTC
All use subject to JSTOR Terms and Conditions
302
MATHEMATICS
MAGAZINE
diagonal
next at
(n
-
k,n
-
k). In the
course
of traversing this path we
would
continue
to guess
that the next
card is
red since
red
>
black
in that portion
of the
path;
therefore,
we
will be
correct
exactly
k times
and incorrect k
-
1 times
during
this
part
of
the
game.
In
the
path
from (n, n) to (n
-
k,
n
-
k), our expected
score
is
then
k +
0.5
of
a possible
2k.
A
child's strategy of
random
guessing
would yield
an
expected
score of
k between
(n, n) and
(n
-
k, n
-
k). Clearly,
the more
we visit the
diagonal,
the more
frequently
we will gain
this extra
0.5 in our
expected
score.
Example.
The game
path in
FIGuRE
2 is
randomly
chosen from
the C(52,
26) ways
in
which twenty-six
red
and twenty-six
black
cards can
be arranged
in a deck
of fifty-two.
This game
path
"visits" the
diagonal
5 times, not
counting
(0,0). At
each of these
visits,
we assume
that our guess
is made
at random.
Therefore,
our expected
score for
this game
is 28.5.
black
(26,26)
(0,0)
Xo
red
FIGURE 2
Let
P
be the set
of all
game
paths.
Since a
game
path
is determined
by
the
n
positions
of the red
cards
in
a
2n
card
deck,
there are
C(2n,
n)
different
game paths.
Let
p
be
any game
path;
and let
v(p)
be the number
of
diagonal
visits
by p.
Given
the observation
about
diagonal
visits,
the
expected
score
given
p
is
n +
0.5(v(p)
-
1).
We consider
visiting (0,0)
a diagonal
visit;
hence the
-
1
in
this
formula.
Since
we
assume
that the deck
of cards
is
randomly
shuffled,
each
of the
C(2n, n) paths
is
equally
likely;
thus
S(n)
=
E
(n
+
0.5(v(p)
-1))/C(2n,
n)
peP
n +
0.5
(
v(p)/C(2n,
n))
-I).
This
reduces our
problem
to the
calculation of the
average
number
of
visits
to
the
diagonal;
or
equivalently,
to the
calculation
of
the total
number of
diagonal
visits
in
all
game
paths.
3.
The
total number of diagonal visits.
We will use a combination
of
combinatorial
averaging
(as
in
[4])
and
generating
function
techniques (as
in
[1])
to
compute V(n),
This content downloaded from 129.16.69.49 on Mon, 28 Dec 2015 08:34:58 UTC
All use subject to JSTOR Terms and Conditions
VOL. 61, NO. 5,
DECEMBER 1988
303
the total number
of diagonal visits by
all game paths in
P. Let
X(P,
m)
=
I
if
p
visits
(m, m)
O otherwise.
n n1
V(n)
=
[
S
X(P,m)
=
E
E
X(P m)]
ep-Pm=O
m=O
Pep
n
=
E
the
number of paths that
visit (m, m)
m=O
n
=
E
C(2m,
m)C(2(n-m),
n
-
m).
m=O
The final equality
is derived as follows
(see FIGURE 3).
If p visits
(m, m),
then the
first 2(n
-
m) cards
in the deck consist
of exactly
n
-
m red cards and n
-
m black
cards,
which can be arranged
in
C(2(n
-
m), n
-
m) ways. Furthermore,
the
last 2m
cards contain
m
red and
m
black,
which can be
arranged
C(2m, m) ways.
Hence the
product C(2m,
m)C(2(n
-
m), n
-
m) is the total number
of game paths
that visit
(m, m).
black
(n, n)
.......g.fi.: 0
| SISg
.
/ .
C(2(n
-
ei),
n -
m)
..
,-""~~~~~~~~paths
here
C(2m,
m,)
paths
here
(0, 0)
red
FIGURE 3
At
this
point,
we
remind
the reader of some basic
properties
of
sequences
and
generating
functions.
If
A
is a
sequence
of
numbers,
then the
generating
function of
A
is
G(A; z)
=
A(O)
+
A(l)z
+
A(2)z2
+
A(3)z3
+
* *
.
For example, if A(n)
=
arn,
G(A; z)
is
a
geometric
series, which
has closed form a/(l
-
rz). The convolution
of
sequences
A
and
B
is a
sequence
A
*
B, where
n
(A
*
B)(n)
=
A(m)B(n -m).
m=O
One
of
the
most useful
facts about
generating
functions
is that G(A
*
B; z)
=
G(A; z)G(B;
z).
THEOREM. Let V be
the total number
of diagonal visits
by all game paths
in P.
Then G(V; z)
=
1(1
-
4z), which implies that V(n)
=
4nf
This content downloaded from 129.16.69.49 on Mon, 28 Dec 2015 08:34:58 UTC
All use subject to JSTOR Terms and Conditions
304 MATHEMATICS MAGAZINE
Proof The
key observation to be made is
that the Taylor series
expansion of
1/(
/1
-
4z
)
is
00
L C(2n,
n
)z'.
n=O
Let
D(n)
=
C(2n, n). Our final expression
for V(n) above is (D
*
D)(n); i.e.,
V
=
D
*
D.
Therefore,
G(V; z)
=
G(D
*
D; z)
=
G(D; Z)2
=
1/(1-4z).
The only sequence
having this generating
function is the geometric
sequence 4n;
therefore, V(n)
=
4nl
4.
Return to
the
original problem, asymptotic
estimates. With our
calculation of
V(n),
we
have
S(n)
=
n +
0.5((4n/C(2n,
n))
-
1).
(1)
The first term of
this expression represents the
portion of the expected score
that we
would
expect
from
making
random
guesses, while the
second
term
represents the
advantage
from
counting
cards. For
values of
n
such as 26 this second term is
difficult
to
calculate; hence we turn to
an asymptotic
estimate.
Recall that if
f, g,
and h are
sequences of real
numbers,
then
f(n)
=
g(n)
+
0(h(n))
means that there exist
integer
N
and real
number C such that
I
f(n)
-
g(n)
I
<
CIh(n)I
for
all
n
>
N.
If
lim
-,
.
h(n)
=
0, then
g(n)
can be
used as an
approxima-
tion of
f(n).
Of
course,
the
usefulness of the approximation
depends on
N
and
C.
Our
estimate of
S(n) is based on Stirling's
approximation of n-factorial,
n!
=
2_r
(
n/e
)
+
0( /2X/Tn
(
n/e)).
This formula
can be
substituted
into
(1) to
obtain
S(n)
=
n
+
0.5(Tn-1)
+
0(1/).
(2)
Since
limn
ooI/
n
=
0,
we can
approximate
S(n) with the first two terms
in (2).
5. Results of a
computer
simulation.
To
get
a
feel
for
how
good
our
approximation of
S(n) is,
a simulation of "Red
or Black" was run for
n
=
26
(the usual deck
size)
and
for n
=
100. The results
of the simulation
appear
in
TABLE 1.
They seem to indicate
that the
0(1/F)
term
in
(2)
is small
enough
to estimate
S(n)
to the nearest
integer,
at least.
TABLE
1. Results of a
Computer
Simulation
n
Games
Average
Score
Approximation
of
S(n)
26
300
30.007 30.019
100 200
108.290 108.362
6.
Acknowledgments
and
comment.
Thanks
go
to
my
mother
for
teaching
"Red
or
Black" to
my
children and to
D.
Knuth,
whose
study
of
the toilet
paper problem
in
[2]
led me
to
the
idea of
game paths.
This content downloaded from 129.16.69.49 on Mon, 28 Dec 2015 08:34:58 UTC
All use subject to JSTOR Terms and Conditions
VOL. 61,
NO. 5,
DECEMBER
1988
305
Several
persons have commented
that
with the
simple
form
of
V(n), a
simpler
derivation
might be
possible; but I
know
of none.
REFERENCES
1. A.
W.
Doerr and K. M. Levasseur, Applied Discrete Structures for Computer Science, SRA, Chicago,
1985.
2. D. E. Knuth, The toilet paper problem, Amer. Math. Monthly
91
(1984), 465-470.
3.
P.
W. Purdom
and
C. A.
Brown,
The
Analysis of Algorithms, Holt, Rinehart
and
Winston,
New
York,
1985.
4. Herbert S. Wilf, Some examples of combinatorial averaging, Amer. Math. Monthly
92
(1985), 250-261.
When Does the
Symmetry Property Hold?
GLORIA OLIVE
University
of
Otago
Dunedin, New Zealand
If a and b are integers,
the usual combinatorial
argument can be
used to show
that
the
symmetry property
for the binomial coefficients,
(a+b)
=
(a+b)
(A)
holds when
a0
and
b0.
(B)
Various students and
others have used (A)
more freely-and without
justification.
In
order to
determine
necessary conditions for
(A) to hold, we will first
let x represent
a
complex number and
n represent a positive
integer. Then the adoption
of the
usual
definition
x) - and
(x) x(x- 1) (x-
n
1)
(C)
and the usual
convention
(-n ) ?
(D)
help to reveal that
(A) may not hold. For
example,
(-n)
(
0)
when
n
is a
positive
integer.
We have
found
that the following problem
can lead students
and others to the
answer of the
question,
"When does
(A)
hold?"
This content downloaded from 129.16.69.49 on Mon, 28 Dec 2015 08:34:58 UTC
All use subject to JSTOR Terms and Conditions