Showing that the number of queues is uniquely expresssed as the product of $2010$ positive integers.

50 Views Asked by At

This problem came from a friend in preparation for a contest.

There are $2011$ people in a queue lining up for a conference, and no two people have the same height. Bob is the $27$th tallest person in the group. Let $n$ be the number of queues that the group of $2011$ people can form such that in the queue, Bob is shorter than everyone else in front of him.

Prove that there are exactly one set $S$ of $2010$ distinct positive integers, such that $n$ is the product of all the elements of $S$.

My work:

Number the queue $1,2,\dots, 2011$. Let $b$ be Bob's position. Clearly, $b\leq 27$ since if $b=28$, there is guaranteed to be a person in front of him that's shorter.

If $b=27$, there are $26$ spaces in front of him, and $2011-27=1984$ places behind him. So the number of queues in this case is $26!\times 1984!$.

if $b=26$, we obtain similarly $25!\times 1985!$. Continuing down to $b=1$, we find that the total number of queues is $$n=\sum_{i=1}^{26}i!\times (2010-i)!$$ From here, I thought we could find the elements of $S$ by factoring something like $n=1984!\times (\dots)$ but I'm not quite sure how to continue.

1

There are 1 best solutions below

0
On

There are $2011!$ possible queues without restriction, but we count only those where Bob appears as first among the $27$ tallest people. By symmetry, this happens in precisely $\frac1{27}$ of all queues, so $$n=\frac{2011!}{27} $$ and this immediately suggests one possible way to write $n$ as product of $2010$ distinct positive integers, namely the integers $1,2,\ldots,2011$ except $27$.

Any other product of $2010$ distinct positive integers is either of the form $\frac{2011!}{k}$ with $1\le k\le 2011$ (and obviously no other $k$ tan $27$ will give the correct value), or has at least one factor $\ge 2012$ and the product of the remaining $2009$ distinct positive integers is $\ge 2009!$, so in total the result would be too big.