Structured Shuffles and the Josephus Problem

doi:10.4236/ojdm.2012.24027

Paper Menu >>

Journal Menu >>

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: [email protected], [email protected]

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







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







st, wee m objects and skip

over the

remov







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-

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









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





π1











π:1, 1,NN 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





1mst 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





N where k is maximal subject to

2N.



Alternatively, .





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





,Nm Tasmanian

Shuffle. Then:

1) If Nm



, then





,Nm 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

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







22,

N

 

for N satisfying 1

.

is eveand 2

N pC

thr

se (1): N

n 1

k One

,nN

he rema



1, 3

ith t

ass

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

k ha2N cards, hence 1

222,

 and

the induction hthesis gives theypo position



 of the

last card as



222 2.





  Now each

card in the surv in front of it iving deckw

d a do

1,



card

rem

originally, so



22 2,



  and the formula is

verified for k

Case (2): odd an1

N



with N ev

Ne pass through

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

has



12N cards, so



21 22

 .

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

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



n further influence on





the last card relative to the augmented surviving deck as



2122 21



  . 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)

to thenaugmented deck is



 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,



  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



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





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 N1,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

ru m

Non the table r





 ca

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







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









,mmm tN





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 1mt mt





 



But





111Nm mtm m

 







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

S. SULLIVAN, T. BEATTY

141

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

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

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

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





605N7.kdoi:10.1017/S0017089500008272

[8] F. Ruskey and A. Williams, “The Feline Josephus Prob-

lem,” Theory of Computing Sy stems,

pp. 20-34.



mod 73



6053 717



59 ,



Vol. 50, No. 1, 2012,

-9343-6doi:10.1007/s00224-011

 

605,759 73.



  Note7 114 



fixed,



is forced to be 2, even though 3

8 605.