Don Zagier, born in 1951, is an American mathematician whose main a...
Here's a link to [Levasseur's original paper](https://fermatslibrar...
A game path in Levasseur's paper is determined by the position of $...
To understand the expected wins for both the kid (πΆπ») and the paren...
A way to prove that $\sum_{n=0}^{\infty} \binom{2n}{n} x^n = \frac...
This integral is called the Gaussian integral. To solve it we not...
There's an interesting variation of this problem in which the numbe...
VOL. 63, NO. 2, APRIL 1990
89
How
Often Should You Beat Your Kids?
DON ZAGIER
University
of
Maryland
College Park,
MD 20742
A
result is proved which
shows, roughly speaking, that one should beat one's
kids every day except Sunday.
This note is a follow-up to the
note "How to Beat Your Kids at Their Own Game,"
by
K.
Levasseur
[1],
in
which the
author
proposes
the
following game to be played
against
one's
two-year-old
children:
Starting
with a
deck consisting of
n
red cards and
n
black cards (in typical
applications,
n
=
26), the cards are turned up one at a time,
each
player
at each
stage
predicting
the color of the card which is
about to appear.
The kid is supposed to guess "Red"
or
"Black"
randomly
with
equal probability (this
solves the
problem
of
constructing
a
perfect
random number
generator),
while
you
play what is obviously the optimal
strategy-guessing randomly (or,
if
you prefer,
always saying "Black")
whenever
equal
numbers
of
cards of both colors remain
in
the
deck
and
otherwise
predicting
the color
which
is
currently
in
the
majority.
Levasseur
analyzes the game
and shows that
on
the
average you
will
have a score of
n
+
(VFW
-
1)/2
+
O(n- 1/2),
while the
kid,
of
course,
will
have
an average score
of
exactly
n.
We, however, maintain that
only
the
most
degenerate parent
would
play against
a
two-year-old
for
money,
and
that
our concern
must therefore
be,
not
by
how much
you
can
expect
to
win,
but
with
what
probability you
will win
at all.
Our
principal
result is that this
probability tends
asymptotically to 85.4% (more precisely: to
1/2
+
1/
F8)
as
n
tends to
infinity.
This
shows
with
what unerring instinct Lev-
asseur's mother selected the
game-the
high
85%
loss rate
will
instill
in
the
young
progeny
a
due respect
for the
immense superiority
of
their parents,
while
the
15%
win
rate will
maintain
their
interest
and
prevent them
from
succumbing
to
feelings
of
hopelessness
and
frustration.
The
analysis begins
as
in
Levasseur's article:
each of
the
(2n)
possible
orderings
of
the cards
into
red and black elements
corresponds
to
a
path p moving
downwards
and leftwards from
an initial value
(R, B)
=
(n, n)
to a
final value
(R, B)
=
(0, 0)
of
the
pair (R, B),
where
R
and
B
denote the numbers
of red and
black
cards
remaining, respectively.
If this
path
meets the
diagonal
R
=
B
a
total
of
m(p)
times,
where the initial
point
at
(n, n)
is counted but the final
point
at
(0, 0)
is
not,
then the
expected
win of
the
parent
is
m(p)/2. Indeed,
at each
meeting point
the
parent
guesses randomly,
with
an
expected
score
of
1/2
and
hence an
expected
win
over
his
child of
0;
between each
pair
of
meeting points,
the
parent
will
consistently guess
"Red" or
consistently "Black,"
depending
on whether
p
is
now
below or above
the
diagonal,
and
will
be
right exactly
one more time than he is
wrong, gaining exactly
half a
point
over
his
randomly
guessing
child. Levasseur shows
that the
average
value
of
m(p),
as
p ranges
over the set
;n
of
paths
as described
above,
is
exactly
4f/(2n )- 1, leading
to the result
on the
expected
win
stated above. To solve
the
problem
we have set
ourselves,
we
must
answer two
questions:
-(i)
for a
given
value of
m(p),
what
is
the
probability
of
winning?
and
-(ii)
with what
probability
will
m(p)
take
on a
given
value
m,
1
<
m
<
n?
We
answer the second
question
first.
90 MATHEMATICS
MAGAZINE
Let Nm(ln) denote the number of paths p
E
9)n with m(p) = m. For
n =
0
this
equals 1
if m =
0 and 0 otherwise, but for positive n we must have m >
1 since the
initial point
of the
path
is
counted
as a
meeting
with the
diagonal.
If a
path p
e
9n
meets the diagonal more than once, i.e.,
if
m(p)
>
1, then the first meeting
point
will
be at
some
value (k, k)
of
(R, B)
with
1
<
k
<
n - 1.
Conversely,
if we
pick
such a
k,
then the number of
paths
p
e
9Zn
with
m(p)
m
and
having (k, k)
as their first
meeting point
will
be equal to the product of N1(n
-
k) (the number
of ways of
descending from (n, n) to (k, k) without meeting the diagonal on the
way)
and
Nm
-(k)
(the
number of
ways of descending from (k, k) to (0,0) with
exactly
m
-
1
further meetings). Hence
n-1
Nmf
n)
Y2, N(
ni-k)
Nm( k) (m
>
1).
k=1
It follows that the generating function
X,4'(x)
=
l
,NmNm(ln)x'
is the
product of
Xl(x) and
X,' -I(x),
and hence that
X,,j(x)
=
Xl(x)'.
This formula holds
also for
m
=
0 since
NO(n)
=
0
for all positive n. On the other hand, the sum
of all the
functions
X,4'(x)
is the generating function whose nth coefficient is the total
number
of
paths
in
,n,
i.e.,
(
an
) Hence
1
00
00
1
i ,/~(x) -
E 1 X(X)=
X.(x)
(2n)Xn=
-4
m=O
rn=O
n=O
n
r
so
Xj(
x)
=
1
-
14~x,
Xm(
x)
= (
-
Fl
1-4x
)
Using the well-known Taylor expansion of this function, we find:
Nm( n)
=
2m
m r--
(
l
<
m
<
n)
.
Therefore,
the
probability for a random path p
e
gn
to have
m(p)
=
m
is given by
N
(n)
m
(1 n)
n
...
n
)
prob{
m(p)m}
N()
=
jmr
(n ) 1
2n) 2n)
...
2n)
For m
of
the order of
VW
(the right order according to Levasseur's analysis),
this will
Distribution of m
for
n
large
m
O
n
2 n
3
n
4
n
5FG 6UR
FIGURE
1
VOL.
63,
NO.
2,
APRIL
1990
91
be
asymptotically
equal
to
(m/2n)e-m
/4n
(cf.
FIGURE
1).
As a
test,
when
n
is large
we
have
for
the
total
probability
00
00
L
prob{m(p)=m}
E
m
e-m2/4n
m}=O
m=O
2n~~~~~~~~~o
00
00
x
eX
dx
-
- ex2/4n
= 1
n
~~~~~~~0
and
for the expected
value
of
m
the value
00
00
E prob{m(p)=m}
m
m
m
e-
m2/4n
n1=0
M=~~~00
x--
I
x
e-/4n
dx
44
t2-
dt=Vn,,
in
accordance
with Levasseur's
result.
We
now
turn
to
the first
of
the
two questions above. For the reasons
already
explained,
for
an
ordering
of
cards given by a path
p
e
;n
with m(p)
=
m, of
the
2n
-
m
turns
corresponding
to
points
on p not
on the diagonal one will
guess
correctly
exactly
n times
and
incorrectly
exactly
n
-
m times, while the probability
of
guessing
correctly
at
one
of
the
m
turns
corresponding
to points on the diagonal
is
50% each time.
Hence
one's
total
number
of correct guesses will be described
by
a
bell-shaped
curve
centered
around
the
expected value n
+
am and with
a width
of
the
order of x4m,
or
(for
almost
all
paths
p)
VW (cf. FIGURE
2). On the other hand,
if
one
guesses
correctly
n +
k times,
then
one's
chance of beating
the
randomly
playing
kid is
2n nk-1 k
22n
L 2rn
-
+
2-2n
(2n)
and
since
2
-2n(
X2nX))
1/rn
e
r/n
by
Stirling's
formula,
this is
approximately
equal
to
1
1
k
2
1 1
k
2
_1
lk/#n
2
2?+
7
Y.
e-r
/n
+
feu
/ndu
+
-
e
u
du.
2r =O
2
Probability
Probability
distribution
distribution
of
kid's
of one's
own
number
of
number
of
correct
guesses
correct
guesses
O(r4m)
n-2V2A
n-VC
n
tn+Vn
n+2Vn
(distributed
according
to
Fig.
1)
FIGURE
2
92
MATHEMATICS
MAGAZINEE
Since
k/
xn
is
almost
always
very
near
to
'm/
x/W,
the
probability
of
winning
when
m(p)
=
m
is
very
nearly equal to
1
+
1
m/2F
2
?
Ie-u
du.
Multiplying this
by
the
probability
that
m(p)
=
m
as
computed
above,
we
find
finally
probability
of
winning
?
-f
1 f
m/2r
e
du)
P
Y
g
2
mE-O~0
x
2n
x(
F
-
U2
2+
| 2x
e
X
/4
n(
l/
Ee-
du)
dx
1 fx/2
2~
2
+2
xe-
x
/4(-
e-u
du
dx
2
2 n/
l
j 0)
1 1
00
2(fOO2
\
I +e-uI
xe-x/4dxl
du
2
2/
O
I
(2u)d
-
+
le-U2(2e-u
)du
1
1
2+
2 /'
as claimed. This is
very
nearly
6/7,
so the
result
of
our
paper
can be
conveniently
implemented
by
beating
one's kids on
weekdays
and
Saturdays,
but
never
on
Sunday.
R E F E R E N C E
1. Kenneth M. Levasseur, How to Beat Your Kids at Their
Own
Game,
this MAGAZINE
61
(1988), 301-305.
A
Note
on the
Five-Circle
Theorem
JORDAN
B. TABOV
Institute of
Mathematics
Bulgarian
Academy of Sciences
P.O.
Box
373
1090
Sofia,
Bulgaria
In
his paper
[1]
H.
Demir stated and
proved
THE
FIVE-CIRCLE THEOREM.
Let
P
and
Q be two points on the side BC
of
a
triangle
ABC in the
order B, P,
Q, C. If the
triangles ABP,
APQ, AQC have
congruent
incircles, then the
triangles
ABQ,
APC
have
congruent
incircles.
He also
asked for a
geometric proof of
this
theorem.
Here we
give such a proof
for the
following
more
general
Here's a link to [Levasseur's original paper](https://fermatslibrary.com/p/dd99acba).
A game path in Levasseur's paper is determined by the position of $n$ red cards in a $2n$ card deck, which means there here are ${2n\choose n}$ possible game path combinations.
Don Zagier, born in 1951, is an American mathematician whose main area of work is number theory. He was a child prodigy and got a bachelor's and master's degree from MIT at the age of 16 and a PhD from the University of Bonn at the age of 20.
A way to prove that $\sum_{n=0}^{\infty} \binom{2n}{n} x^n = \frac{1}{\sqrt{1-4x}}$ is to start with:
$$
(1+ax)^m=\sum_{n=0}^{\infty} \binom{2n}{n} x^n
$$
and derive it on both sides
$$
ma(1+ax)^{m-1}=\sum_{n=1}^{\infty} n\binom{2n}{n} x^{n-1}
$$
Then derive it again
$$
m(m-1)a^2(1+ax)^{m-2}=\sum_{n=2}^{\infty} n(n-1)\binom{2n}{n} x^{n-2}
$$
For $x=0$ we get
$$
ma = 2\\
m(m-1)a^2=12
$$
The solution for these equations is $a=-4$ and $m=-1/2$
There's an interesting variation of this problem in which the number of red and black cards are different (m,n). For this case the probability of winning is:
$$
\frac{1}{2}+\frac{1}{\sqrt{8}}-\frac{1}{2\sqrt{m\pi}}-\frac{7\sqrt{2}}{64m}+\frac{1}{16\sqrt{\pi}m^{3/2}}+O(m^{-2})
$$
If you want to read more about this variation [click here](http://www.kurims.kyoto-u.ac.jp/EMIS/journals/EJC/Volume_8/PDF/v8i2r13.pdf).
This integral is called the Gaussian integral. To solve it we notice that
$$
\left(\int_{-\infty}^{\infty} e^{-x^2}\,dx\right)^2 = \int_{-\infty}^{\infty} e^{-x^2}\,dx \int_{-\infty}^{\infty} e^{-y^2}\,dy = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} e^{-(x^2+y^2)}\, dx\,dy.
$$
Using polar coordinates:
$$
\int_{\mathbf{R}^2} e^{-(x^2+y^2)}\,d(x,y)
= \int_0^{2\pi} \int_0^{\infty} e^{-r^2}r\,dr\,d\theta \\
= 2\pi \int_0^\infty re^{-r^2}\,dr\\
= 2\pi \int_{-\infty}^0 \tfrac{1}{2} e^s\,ds \\
= \pi \int_{-\infty}^0 e^s\,ds \\
= \pi (e^0 - e^{-\infty}) \\
=\pi
$$
where the factor of $r$ is the Jacobian determinant of the coordinate transformation and $s = -r^2$.
Combining the expressions:
$$
\left ( \int_{-\infty}^\infty e^{-x^2}\,dx \right )^2=\pi
$$
so
$$
\int_{-\infty}^\infty e^{-x^2}\,dx=\sqrt{\pi}
$$
To understand the expected wins for both the kid (πΆπ») and the parent (π΄π») let's consider the following diagram where each point represents a state of the deck of cards, starting with n red cards and n black cards.
In the first draw the expected value for both is 1/2.
$$
(n,n) \rightarrow (n,n-1)
$$
E(πΆπ»)=E(π΄π»)=1/2
In the next draws the parent knows there are more black cards than red ones so he will always bet black until the path intersects the line R=B again (there are the same number of black and red cards). In this case for the path to intersect the R=B line, 2k-1 cards will have to be drawn, k of which will be black and so the parent will be correct k times and miss k-1 times. On the other hand, the kid will be right in half of the times: (2k-1)/2. As a result, the expected values are
$$
(n,n-1) \rightarrow (n-k,n-k)
$$
E(πΆπ»)=(2k-1)/2=k-1/2
E(π΄π»)=k
As we can see, every time the path crosses the line R=B, the parent's expected win over the kid increases 1/2! More generally, if the game path $p$ crosses the R=B line $m(p)$ times the expected win is $m(p)/2$.