Call applicants to front

Let $n$ be a natural number, and we are given a sequence $a_1, a_2, \dots, a_{2n}$ whose elements are integers from 1 to $n$ inclusive, such that each element in $(1, \dots, n)$ appears at least once.

Now, suppose there are $n$ job applicants $J_1, \dots, J_n$ waiting on a line, in any order. We call them in for interviews using $a_i$ as our "call list." More formally, for $i = 1, \dots, 2n$, we call $J_{a_i}$ one by one.

If a particular job applicant $J_x$ is called for an interview, he has to pay a fee of $y-1$ where $y$ is his position in the line. For example, if he was the second person when called, he pays a fee of 1. If he was the front person, he doesn't pay. After the interview, he returns to the front of the line, and the interviewer proceeds with the next one on the call list.

For a given call list and initial ordering of applicants, we define income as the total fees paid by the applicants. For a given call list, its potential income is the sum of all income over all possible initial ordering of applicants. Now, to make things more interesting, before the interview day, the call list itself was shuffled, such that any $(2n)!$ permutation is equally likely to appear.

If you are tasked with putting together a call list, knowing that it will eventually be shuffled, how should you structure it so that the expected potential income is maximized?

Shuffling Card

A deck of 31 cards is being shuffled, where at each point, the shuffler may perform the following operation:

1. Cut the deck in half and interleave each half to perform a new deck. The cards at position 1,2,3,...,15 now occupy position 2,4,6,...,30, and the cards at position 16,..., 31 now occupy position 1,3,...,31.

2. Similar to operation one, but with different "cut." The cards at position 1,2,3,...,16 now occupy position 1,3,5,...,31, and the cards at position 17,...,31 now occupy position 2,4,6,...,30.

3. Take $m$ cards from the top and move them to the bottom of the deck (a standard cut).

Starting from the original configuration, how many different configurations can be achieved by repeating the three operations above?

Solution

There are $5.31 = 155$ different configurations.
First, it's clear that the deck can be "rotated" in any amount along one direction, so we only consider rotational configurations.
Step 1 moves cards from position $m$ to $2m \mod 31$
Step 2 moves cards from position $m$ to $2m-1 \mod 31$
Step 3 moves cards from position $m$ to $m+k \mod 31$ for some $k$.

Now, step 3 does not change the rotational configurations. Step 1 and 2 both can be consolidated into the move from $m$ to $2m \mod 31$ and followed by a suitable number of step 3.

Thus, the number of different rotational configurations are the smallest number $n$ such that $2^n \equiv 1 \mod 31$, and that means $n=5$.

So there are 5 rotational configurations and 31 configurations within each rotational configuration, for a total of 155.

KBB2 Problem 10

Let $P$ be a permutation of the number $(1,2,\cdots,n)$. We apply a process as follows:

Start with the leftmost number and move to the right. Everytime we encounter a number that's bigger than the leftmost number, we swap that number and the leftmost number. Continue until we arrive at the rightmost number.

Define the rank of $P$ as the number of swaps that happened. For example, the permutation$(2,3,1,4)$ has rank 2 because:

$\displaystyle (2,3,1,4) \to (3,2,1,4) \to (4,2,1,3)$

Let$S_n$ be the sum of the ranks of all possible permutations of $(1,2,\cdots,n)$. Is there an $n$ for which$S_n > 2009n!$?