This week the #puzzle is: Can Your Team Self-Organize? #permutations #LongestIncreasingSubsequence

In a recent team building exercise at work, a group of people (including myself) was asked to quantify themselves in various ways. For example: “What outdoor temperature do you prefer?” No one reveals their answer at first. Instead, each person places a card with their name on an unmarked line, one at a time. In this example, folks who prefer higher temperatures would place their names farther right; folks who prefer lower temperatures would place their names farther left. However, the line is unmarked and doesn’t have any units.

Once all the names are placed on the line, their values are revealed. For example, a group of six might have generated the following numbers, in order from left to right on the line: 60, 67, 65, 74, 70, 80.

The team’s score is the length of the “longest increasing subsequence.” In other words, it’s the maximum number of elements in the list you can keep such that they form an increasing subsequence. In the example above, you can remove the 67 and the 74 to get the following increasing subsequence with four numbers: 60, 65, 70, 80. There are a few other ways to get an increasing subsequence of length four, but there’s no way to get a sequence of length five or more, so the team’s score is four.

Suppose a total of four people are participating in this team building exercise. They all write down different numbers, and then independently place their names at random positions on the line.

On average, what do you expect the team’s score to be?

And for extra credit:

Instead of four people, now suppose there are 10 people participating in the team building exercise. As before, they all write down different numbers, and then independently place their names at random positions on the line.

On average, what do you expect the team’s score to be?

Can Your Team Self-Organize?

Highlight to reveal (possibly incorrect) solution:

Spreadsheet Program Image

Method 1: Write out all the permutations, measure the longest increasing subsequence for each, calculate the average. This is what I did in the spreadsheet. Result: 2.41667.

Method 2: Create an image, a graph, with all the permutations and how one can move between them moving just 1 number. This gives me the number of permutations with subsequences of length 1, 3 and 4 (1, 9 and 1). For length 2 it gets messy. For them the number is “the rest” (24 – 1 – 9 – 1 = 13). Do the same calculation as above.

Method 3: Write a program to go through all the permutations. This replicates method 1. Same result.

And for extra credit:

Theorem

Do method 3, just with 10 members instead of 4. Result: 4.33496.

Apparently the Baik–Deift–Johansson theorem says something about this situation as well.