0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.