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