# Alejandro Erickson

Low production value innovation.

Flash

## The Feline Josephus Problem

This is a flash app that I made for my advisor, Frank Ruskey and his former student, Aaron Williams, for their presentation of The Feline Josephus Problem at the FUN With Algorithms Conference 2010, Ischia Island, Italy.

From Wikipedia, the history of the original Josephus Problem is the following:

The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. According to Josephus' account of the siege of Yodfat, he and his 40 comrade soldiers were trapped in a cave, the exit of which is blocked by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves using a step of three. Josephus states that by luck or maybe by the hand of God (modern scholars point out that Josephus was a well educated scholar and predicted the outcome), he and another man remained the last and gave up to the Romans.

The two parameters in the above problem are the number of soldiers and the "step" size.  That is, instead of killing every third person left in the circle, every kth one is killed.  In the Ruskey-Williams variation the soldiers have the super powers of cats and may have more than one life.  The parameters of the problem are (n,k,l).  These are for the number of soldiers, the skip count and the number of lives.  The original problem is (40,3,1).

Ruskey and Williams published a paper on this.  Among their findings was that, rather curiously, the surviving soldier is always the same if the soldiers have a number of lives greater than the nth fibonacci number.  Even more interestingly, if you fix the number of soldiers n and you declare the survivor before beginning, you can find a skip count k that allows this to happen for any number of lives l.  What's more, is that the same skip count k works for all values of l!  How cool is that! :D.

Much of the paper is very accessible and would be a great read for undergraduate computer science or math students and fun for the rest of us too :).  It can be found on Frank Ruskey's webpage at this link.

Last Updated on Monday, 05 July 2010 11:28

## Listing combinations by making transpositions

Suppose you have an apple, an orange, a banana, a pineapple a grape and a screwdriver and you choose to take exactly 3 of these things.  This is called a 3-combination of a 6-set, because you chose 3 of the 6 things.  Now suppose you want a different set of 3 things by putting one thing back and taking another.  Easy, right?

For some inexplicable reason, however, you want to hold every set of three things exactly once and each time you change, you want to swap one item in your hand for one on the table.  Is this even possible?!?

The short answer is yes.  And I've animated it for you!  Look at it like this:  The colour of the balls in the animation indicates whether the thing in that position has been chosen.  Swapping a red ball in position 2 and a blue ball in position 6 simply indicates that the second item was swapped with the fifth item.

Without further ado, enjoy my first ever flash animation.

Last Updated on Saturday, 10 April 2010 10:45