Tuesday, August 17, 2010

Search for Numbers

So I am not posting regularly, I suck. Moving on...
Some long while ago, while sharing puzzles with friends on lebgeeks.com, I posted a mathematical puzzle that I didn't know the answer for.

Writing quiz problems is not easy, especially when there are new concepts to explain.

Problem:
The explanation I made on the forum was kind of screwed, and I will have to describe it again.
There are n employees. They have numbers on their back from 1 till n. There is a bowl that has n papers, also with numbers from 1 to n. Each employee comes in after the other, to pick a number from bowl. An employee may pick himself.
Starting with any employee, checking the piece of paper and reading the number, and going to the employee whose number appears on that piece of paper and repeating, you will be stuck in a loop of k employees, where k is less than or equal to n. Whenever a bowl is consumed (a paper is picked by each employee), there will be a set of loops, each of different size.
You are required, given n, to determine first the possible loops and their sizes. Next you have to determine the probability of that partitioning of n into loops from a random set of draws from the bowl.

Example:
For n = 4, the result is:

1 - A single loop with 4 employees; probability: 3!/4!

2 - A loop with 3 employees, and an employee who drew his own number; probability: 8/4!
The single employee can be anyone of the four employees. For the loop of three, the first employee can pick between two other employees (2 options). The picked employee must pick the one that the first left out (no choice). The last one must pick the first one (no choice). As such, there are 4*2! ways.

3 - A loop with 2 employees, and another with 2 employees; probability: 3/4!
Two employees selected from four. That's 4!/2!/2!. Two employees can only be ordered in one way to make a loop of two. The left two employees have only one way to become a loop of two. It would appear that the probability should be 6/4!. You'd have to remember that the loops are symmetric, so a divide by two is in order.

4 - A loop with 2 employees, and two cases of an employee picking his own number; probability: 6/4!

5 - 4 cases of an employee picking his own number; probability: 1/4!

The probabilities sum up to 4!/4! = 1. (This was at first a pointer that there was a problem with my calculations for case 2).

So how did I learn that my calculations are not fubar? Taking this series we just calculated: 6, 8, 3, 6, 1. Searching on google for the phrase: "search for number series". I found this place. Plugging the series into it gave this result. Scrolling a little bit down, inside the "Triangle of multinomial coefficients read by rows", I found a link that read something relevant to what I was solving: Cycle classes of permutation. And there was it, I was reassured I wasn't doing this alone, and that my math is not fubar. I liked the brevity of the explanation, and the mathematical rigor, though I couldn't have used it to explain the problem to the layman, or at least make it more relevant to them.