1
$\begingroup$

$n$ friends get together and decide to play a game. Thankfully one friend has a deck of $n$ cards, numbered from $1$ to $n$.

How the Game Works

  1. The group splits into pairs (the game only works when $n$ is even)
  2. Everyone draws a card
  3. In each pair, the person who drew a card with a higher number wins (yay!)
  4. Winners are recorded and who drew which card is recorded
  5. Cards are collected and shuffled
  6. Repeat steps 1-5 for $m$ rounds
  7. Publish the final rankings in order of wins

The Question

My question is about looking at all the possible ways the game could have played out if people would have paired up differently. There are $(n - 1)!!$ possible ways people could have paired up in a given round. Which means that over $m$ rounds, there could have been $(n - 1)!!^m$ ways for the game to have played out

The next time the group plays the game, they decide that everyone has to pair up with each other roughly the same number of times. The maximum and minimum number of times two people can pair up is as follows

$$\text{max} = \left\lceil \frac{m}{n-1} \right\rceil$$ $$\text{min} = \left\lfloor \frac{m}{n-1} \right\rfloor$$

With this new rule, how many possible ways could the game have played out?

$\endgroup$
  • $\begingroup$ This is the flavor text that I was going to, but didn't add to the question: One of the people playing the game (let's call him Bob) starts to realize that one of his friends (let's call him Jimmy) is getting really lucky. Even though Jimmy is drawing really low cards, he seems to always be paired up with someone who draws a lower card. So Bob decides he is going to prove that Jimmy got lucky. Since all of the data from the rounds is recorded, Bob decides to create a simulation to show what the final rankings should have been in all permutations of pairings. $\endgroup$ – alexdriedger Feb 21 at 16:09
1
$\begingroup$

Let's call this number $P_n$. It is quite obvious, that $P_2 = 1$. Now, suppose $n > 2$. Then we know, that the $n$-th player paired with $m\%(n - 1)$ people $\left\lceil \frac{m}{n-1} \right\rceil$ times and with $n - 1 - (m\%(n - 1))$ people $\left\lfloor \frac{m}{n-1} \right\rfloor$ times (here $\%$ stands for remainder). He can do that in $C_{n-1}^{m \%(n-1)}$ ways. So $P_n = C_{n-1}^{m \%(n-1)}P_{n - 1} = \Pi_{i = 1}^{n - 1} C_{i}^{m \%i}$.That is the answer.

$\endgroup$
  • $\begingroup$ Awesome! I have taken some university math but I'm not sure what C or the 2 in Roman numerals mean. Could you add an example with numbers substituted in? $\endgroup$ – alexdriedger Feb 21 at 17:01
  • $\begingroup$ @alexdrieger, $\Pi$ stands for product in the same way, as $\Sigma$ stands for sum. $C_n^k$ stands for binomial coefficients: en.wikipedia.org/wiki/Binomial_coefficient $\endgroup$ – Yanior Weg Feb 21 at 17:04

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.