Open Journal of Discrete Mathematics, 2012, 2, 138-141
http://dx.doi.org/10.4236/ojdm.2012.24027 Published Online October 2012 (http://www.SciRP.org/journal/ojdm)
Structured Shuffles and the Josephus Problem
Shaun Sullivan, Thomas Beatty
Florida Gulf Coast University, Fort Myers, USA
Email: ssullivan@fgcu.edu, tbeatty@fgcu.edu
Received July 28, 2012; revised September 3, 2012; accepted September 18, 2012
ABSTRACT
The Australian Shuffle consists of placing a deck of cards onto a table according to this rule: put the top card on the
table, the next card on the bottom of the deck, and repeat until all the cards have been placed on the table. A natural
question is “Where was the very last card placed located in the original deck?” Card trick magicians have known em-
pirically for years that the fortieth card from the top of a standard fifty-two card deck is the final card placed by this
shuffle. The moniker “Australian” comes from putting every other card “Down Under”. We develop a formula for the
general case of N cards, and then extend that generalization further to cases involving the discard of k cards before or
after putting one on the bottom of the deck. Finally, we discuss the connection of the Australian Shuffle and its gener-
alizations to the famous Josephus problem.
Keywords: Josephus; Shuffling
1. Introduction
A colleague of ours who is an avid amateur magician in-
troduced us to the traditional version of the Australian
Shuffle, so named because a standard deck of cards is
dealt one at a time onto a table according to the rule that
after the top card is placed on the table, the next card is
to be moved down under to the bottom of the deck, and
then the process repeated until only one card remains...
the final discard. Our friend knew that the card located at
the fortieth position from the top in the original fifty-two
card deck would always be that last card, but wanted an
explanation. Here we consider a formula for a deck of
any size. The Tasmanian Shuffle is the generalization
where instead of placing one card on the table, we dis-
card a fixed number of cards.
The Tasmanian Shuffle is related to the classical prob-
lem [1] of Flavius Josephus. Josephus was part of a Jew-
ish military force that was battling the Romans in the
first century AD. Josephus and forty of his comrades
were trapped in a cave by the Romans, and rather than
surrender, they decided to commit suicide as a group.
The method chosen was for the soldiers to stand in a cir-
cle and, proceeding around the circle in a constant direc-
tion from a fixed starting point, every third soldier stand-
ing would be executed by the next temporarily surviving
fellow around the circle. The standing part is critical,
since any dead soldiers were ignored by this fatal algo-
rithm on subsequent passes around the dwindling circle.
Josephus and his friend were not keen on fully partici-
pating in this exercise, but they were reluctant to object
openly. Josephus managed to survive the fratricidal circle
by arranging to be the last soldier selected. He surren-
dered to the Romans, was adopted by a Roman family
(hence the name Flavius), and eventually became a noted
historian [2]. He relates that it was either luck or God’s
Hand that saved both him and his friend (amazingly, the
second-to-the-last soldier selected). Knowing where to
stand relative to the starting point in order to be the last
one selected is not an intuitively obvious proposition. We
suspect that Josephus, who by all accounts was a clever
fellow, perhaps engaged in a little experimental mathe-
matics with pebbles in the sand to be absolutely sure of
an empirical solution. By the way, if it ever comes up,
stand in the 31st position or the 16th position if you can
trust the guy in the 31st position.
The so-called Extended Josephus Problem [3] is a gen-
eralization of the suicide circle and considers N objects
arranged in a circle where we skip over m oects and
then remove the
bj
1m
st o
isry
bject around the circle in one
direction from a fixed starting point until only one object
remains. We want to know the position of the surviving
object relative to the starting point. A deeper question
involves the exact “kill sequence”, or the de- tailed order
in which the objects are eliminated. For arbitrary m and
N th is a vedifficult problem in the Extended Jose-
phus case. If instead of skipping over m objects and
removing the
1m
st, wee m objects and skip
over the
remov
1m
st, we problem that is in an ob-
vious sense complementary to an Extended Josephus
Problem with parameters m and . We ill recog-
nize the complementary problem as a

,Nm T
have a
ma-
Nw
as
C
opyright © 2012 SciRes. OJDM
S. SULLIVAN, T. BEATTY 139
nian Shuffle. If we save the first object and then remove
m objects iteratively, we have a Texas Shuffle. Note
that the simplified version of the Josephus problem in
which there are Nobjects and the elimination rule is
“skip one, kill one, repeat” is identical to the
,1N
Texas Shuffle. There is an elegant shortcut method [4]
for determining the survivor object in this case using
binary arithmetic, but the justification of the method re-
lies essentially on the details of Proposition 1. An inter-
esting variation in a different direction concerns the
study of patterns which emerge in sequences generated
by reducing by various moduli [5].
,1N
N
N

The Extended Josephus problem doesn’t have a simple
solution, but many have tried attacking it in different
ways [6]. Others have tried finding algorithms [7]. Re-
cently an interesting further generalization [8] was con-
sidered where, in the setting of Josephus, each person has
a set number of “lives” before they are eliminated. In this
paper, we find a very simple solution to our generaliza-
tion to the Josephus problem, and present it in terms of
shuffling cards. Here we describe each type of shuffle.
2. Types of Shuffles
2.1. The Australian Shuffle
Given a deck of cards numbered 1 to from the
top, we subject them to the Australian Shuffle by putting
the top card on the table, then putting the next card on the
bottom of the deck. This is repeated until all of the cards
have been placed in order, each on top of the preceding,
onto the table. We want a formula for the original posi-
tion of the th card placed on the table, which
would be the top card of the permuted deck. More mathe-
matically, we seek , where the permutation
N

1
π1
π:1, 1,NN affects the structured shuffle. Al-
though the Australian Shuffle formula is a sub-case of
the result below for more general permutations of this
nature, we think a direct proof is worth presenting sepa-
rately. The Australian case lends itself to a simple proof
and it gives a hint as to what the extended result might
look like.
2.2. The Tasmanian Shuffle
A natural generalization of the Australian Shuffle would
be to repetitively discard an arbitrary but fixed number of
cards before putting one on the bottom of the deck. Since
we go further south with discards before the “Down Un-
der” move, let us call permutations of this type Tasma-
nian Shuffles. This introduces a complication not present
in the original problem. If at some point during the exe-
cution of the Tasmanian Shuffle there are fewer cards in
the surviving packet than in the number to be placed on
the table, then the very next down move eliminates that
surviving packet completely, and we have to decide
which card is to be regarded as the last discard. Let us
adopt the convention that the card on the bottom of any
such final discard packet is the “last one standing”. We
refer to a Tasmanian shuffle that progressively eliminates
$m$ cards and saves the
1mst card by transferring it
to the bottom of the deck as an
Tasmanian
Shuffle. Then the Australian Shuffle is an
,Nm
,1N Tas-
manian Shuffle. It will also be convenient to denote by
,Nm the last card dealt in a Tasmanian Shuffle,
subject to the convention above. If ,Nm
then
,Nm N
. Otherwise, we have cards. Nm
2.3. Example 1
For an example of the Tasmanian Shuffle, consider a
deck with 24 cards (a standard Euchre Deck), numbering
the cards 1 through 24, and with a skip factor of 2. The
elimination order would then be 1, 2, 4, 5, 7, 8, 10, 11, 13,
14, 16, 17, 19, 20, 22, 23, 3, 6, 12, 15, 21, 24, 9, and the
last card would be the 18th.
3. Main Results
The purpose of this paper is to find the last card in each
of the different shuffles proposed. The following two
propositions give a simple formula for the last card.
3.1. Proposition 1 (Australian Shuffle Last Card)
With the preceding setup, the last card of the Australian
Shuffle is
22
k
N where k is maximal subject to
2N.
Alternatively, .


lg
22
N
N
3.2. Proposition 2 (Tasmanian Shuffle Last
Card)
Let
,Nm be the original position in a deck of
cards of the last card dealt in an
N
,Nm Tasmanian
Shuffle. Then:
1) If Nm
, then
,Nm N
N.
2) If , then can be put in the form
Nm

1,mm
t
where
1,modmN m

 , and
is as large as
possible, in which case
 
,1Nmm t.
Clearly the Australian Shuffle is a special case of the
Tasmanian Shuffle where
1.m
4. Proofs of the Main Results
4.1. Proof of Proposition 1
Note that the first pass of the shuffle through the N
cards produces a surviving deck of 2N cards if N is
Copyright © 2012 SciRes. OJDM
S. SULLIVAN, T. BEATTY
140
even and

12N cards if N is. In any case the
survivors r original order. This surviving deck
is then shuffled according to the rule if N is even, since
the first card of the surviving deck is placed down. But if
N is odd, the parity of the rule is reversed and the first
card of the surviving deck is placed under. We prove this
formula using strong induction on .k If 0,k
odd
are in thei
then
2N and the shuffle puts the second card last on the
which a with the formula. Assume that the
formula is correct for all kk
table, grees
so

1
22,
k
N
 
for N satisfying 1
22
kk
N
.
is eveand 2
k
N pC
thr
a
c
se (1): N
ck
s
n 1
2.
k One
,nN
he rema
1, 3
ith t
ass
in
ough the de places cards w,1 on
the table and creates a surviving decking
cards 2,4,,nN in their original order. The surviv-
ing de
ith
w
k ha2N cards, hence 1
222,
kk
N
 and
the induction hthesis gives theypo position
of the
last card as

1
222 2.
kk
NN
  Now each
card in the surv in front of it iving deckw
d
ha
en
d a do
.
1,
n
he
card
2.
k
On
,
rem
originally, so

22 2,
k
N
  and the formula is
verified for k
Case (2): odd an1
2
k
N

with N ev
Ne pass through
N
ainin
the deck places cards with non the table
and creates a surviving deck with g cards
2, 4,,1 nN in their original order. The surviving
deck
3,
t
has

12N cards, so

1
21 22
kk
N
 .
The induction hypothesis doey immediately to
ince the parity of the shuffling rule
is reversed. We remedy this by adding a ghost card on
the top of the surviving deck and applying the usual shuf-
fling rule to the augmented surviving deck, which has

s not appl
the survivcking de, s
12N cards. The induction hypothesis still applies,
since

12 2
k
N if The ghost card is im-
mediately removed from having a
the shuffle, since the down under step is initialized on it.
The remaining first actual card in the surviving deck is
put under, and the cards that are passed to subsequent
surviving decks will be identical to those that the re-
versed-parity rule would have passed acting on the sur-
viving deck without the ghost card. Now the strong in-
duction hypothesis applies and gives the position
2k. N
y
n further influence on
of
the last card relative to the augmented surviving deck as


2122 21
k
NN
  . Since the ghost
card was put on top of the actual surviving deck, the po-
1k
sition of the last card relative u
ne.
ng our result agai
Comparing to the Taposition 2)
k,
to thenaugmented deck is
1.
 As in Case (1), the position of the last card rela-
tive to the original deck is twice the position relative to
k that survives the first round, so


2122,
k
N
  which again establishes the
formula for k with N odd, and we are
nst the magician’s empirical
knowledge, we have 52, so 5k and
the dec
do
Checki N

252 2540 . Nothing up our sleeve.
4.2. Example 2
smanian Shuffle case (Pro
with a standard dec52, 1,Nm
hence 1.
Then
5,
and we have 52 32,t
so 20t, and
52,12 2040, as previously calculated.
roof of Propo
om the comments above. F
4.3. Psition 2
The first case is evident fror
se strong induction on
then the only con-
the second case, we fix m and u
N. For the base case, set N1,m
sistent parameters are 1, 0,
and 1,t so the
formula returns
,1Nm m
, as expected. Now
ume that the proposed fue for all .NNassormula is tr
Putting cards numbered 1 tesults in
a reduced deck of
h
Nm
ru m
Non the table r
ca
at
w
rds remaining. If we
immediately appeal to the induction hypothe
would be ignoring the fact thrunning a Tasmanian
shuffle on the reduceould not conform to the
permutation of cards induced by the Tasmanian shuffle
on the original deck. We need to “initialize” the reduced
deck by putting the card now on top of the reduced deck
sis, we
d deck
1m
th card in the original deck) on the bottom of the
reduced deck of Nm
cards. The induction hypothe-
sis applies to the reduced and initialized deck, so we have
meters ,,
the para
and t such that

1,Nm mmt


where 1,m

modNm m

 and
is as
large as possible. Now since
dNm m

 mo
clearly
dNm Also, mo

is maxi since mal,
any


would require NN
,m conary to
specification. By assumption we hav
tr
e
,mmm tN
1.

ing the r
deck, so to find
 Note that the process of ini-
tializeduced deck (savinard down un-
der) moved each other card one posit
g the top c
ion higher in that
m,N
we must add one position
back to
,Nmm
 . And since we removed the first
m cards to get to the reduced deck of Nm
cards,
we finally have

,,1NmN mmm
mt m

 


11
11 1mt mt

 
.
But

111Nm mtm m
 
,t


se for N

and the ca
is established.
5. The Texas Shuffle
uts the down under,
of the elimination step. To
ll it a Texas (Chainsaw) Shuf-
fle. So in brief, Tasmanian means eliminate first, then
A variant of the Tasmanian Shuffle p
or preservation step, ahead
distinguish this case, we ca
Copyright © 2012 SciRes. OJDM
S. SULLIVAN, T. BEATTY
Copyright © 2012 SciRes. OJDM
141
If
t
w,
and
skip, and Texas means save first, then eliminate. This
variant is due to the authors attacking this problem (un-
knowingly) in different ways. Fortunately, this difference
results in a trivial change in the formula for the last card.
5.1. Corollary 1 (Texas Shuffle Last Card)
Let

,Nm
be the original position in a deck of N
cards of the last card dealt in an

,Nm Texas Shuffle.
Then:
1) If ,Nm then

,1.Nm

2) , then N can be put in the form

1,mm


Nm
here

1,modmN m


is as large as
po
1.
f: The first case is evident f
ider ghost cards put in front
of the sequence of cards. Renumug-
mented deck of cardoulove the onal cards
po
and Then
and since
we have
that once
ssible, in which case

,1Nmm t

Proo rom the algorithm gen-
erating the shuffle. Cons m
d m
e
N
s w
bering the a
rigi m
sitions higher. Now run the Tasmanian algorithm on
the augmented deck. After thfirst m ghost cards are
removed, the situation is indistinguishable from the Tex-
as Shuffle of just N cards. In this case,
 
,,,NmNmmm
 subject to the parameter
conditions in Proposition 2. Evidently

,1111.Nmmm mtm mt  
Hence

,11.Nmm t

5.2. Example 3
6. Conclusion
che find a simple
st card, and each proof uses a strong
t. Thus, in the Josephus analog we can
[1] R. L. Graham, D. E. Knuth and O. Patashnik, “Concrete
Mathematics: uter Science,” Ad-
dison-Wesley ston, 1989.
ephus
Inoue and S. Tatsumi, “Josephus Prob-
Institute, 2001.
For ea type of shuffle considered, w
formula for the la
induction argumen
find out where to stand so as to be eliminated last. Jose-
phus supposedly knew not only the last position, but also
the second to last. We think that in our case we can do
even better than that. We should be able to find a formula
for when each card will be discarded, that is, a formula
for the permutation of the cards. The generalize- tion in
[8] could also be considered in our case.
REFERENCES
A Foundation for Comp
Publishing Company, Bo
[2] F. Josephus and B. Radice, “The Jewish War,” Revised
Edition, Penguin Books, New York, 1985.
[3] A. Shams-Baragh, “Formulation of the Extended Jos
Problem,” National Computer C onference 2002, Mashhad,
December 2002.
[4] M. Lerma, “Josephus Problem,” Northwestern University,
Evanston, 2004.
[5] T. Yamauchi, T.
lem under Various Moduli,” Kwansei Gakuin University,
Nishinomiya, 2009.
[6] L. Casburn and T. Phan, “The Orthogonal Josephus Prob-
lem,” Journal of the Summer Undergraduate Mathemati-
cal Science Research
[7] A. M. Odlyzko and H. S. Wilf, “Functional Iteration and
the Josephus Problem,” Glasgow Mathematical Journal,
Vol. 33, No. 2, 1991, pp. 235-240.
Suppose
605
605N7.kdoi:10.1017/S0017089500008272
[8] F. Ruskey and A. Williams, “The Feline Josephus Prob-
lem,” Theory of Computing Sy stems,
pp. 20-34.

mod 73
2

6053 717

59 ,

Vol. 50, No. 1, 2012,
-9343-6doi:10.1007/s00224-011
 
605,759 73.
  Note7 114 
is
fixed,
is forced to be 2, even though 3
8 605.