Posted by: sandeepchrao | January 2, 2009

Applications of 152 in Secret Santa

I came across an interesting application of permutations during Secret Santa with my blocking group and some friends a couple weeks ago. In Secret Santa, you are assigned another member of your group whom you must secretly buy a gift for. After all the gifts have been bought and put under the tree, a person is randomly drawn and must pick up the gift with his/her name on it. After the person unwraps the gift, he/she must guess who bought the gift. Once the buyer is revealed, he/she goes next and picks up the gift with his/her name on it. The game goes on until all the gifts under the tree are gone. This year’s Secret Santa was especially interesting. The game was going on normally until the 5th individual guessed who had bought her gift. It happened to be the 1st person to pick a gift and the cycle was completed. A new one had to be started in order for the game to continue. This got me thinking immediately about permutations of thirteen elements and the game of Secret Santa. When all the gifts had been picked, the gift selecting cycle had a structure identical to this permutation…

(assuming you assign ever person a number)

(9  4  6  7  13)(2  12  3  5   11  1  10  8)         A permutation with 1 cycle of 5 and 1 cycle of 8

The previous year, we had a Secret Santa with the same group and the gift cycle structure had the same structure as this permutation

( 1  7  13 4  2  11  9  12 3  8  5  10  6)

One full cycle of 13 is rare among all the cycle structures possible with the 13! possible permutations. I think we were pretty lucky.

Anyway, thought this was interesting. Happy Holidays.

Advertisements

Responses

  1. I was reading your blogs with interest and came across this Secret Santa permutation question. At first I thought that, yes a full cycle was rare. Then I started quantifying it.
    For n people, there are n! permuations of slips of names they can get (allowing for the sad scenario of people getting presents for themselves).
    How many of these are complete cycles? WLOG assume the first number in the cyclic permutation is 1. Then we are left with n-1 remaining numbers in any order. So there are (n-1)! possible full-cycle permutations. Hence 1/n of the possible secret santa permutations is a full cycle. More if self-presenting is ruled out! I was surprised at how often these full cycles arose. I even hand worked a few examples to convince myslef I hadn’t made a silly mistake.
    Thanks for a thought provoking few minutes! Now to ponder the number of ways of getting various cycle-combinations…

  2. Gold bracelet am one of the itmportant pieces of jewelry for every woman. Known as the gold bracelet, unmistakably.
    Owner, gold bracelet, gold with 96.5%, with a deskard weight fluctuating
    from 3 to 25 satang half bath good value are up and down, as the cost of gold on the shop each day.
    Gold bracelet are a sarong generous of jewelry, gold cost,
    so it depends on the format, because the charge are wen the section of
    kamnet.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: