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