0
$\begingroup$

Each of two teams has seven players numbered 1 to 7. In the first game, the two players numbered 1 play each other. The loser of each game is eliminated and replaced by the next player of the same team, until all players from one team have been eliminated. Let $N$ be the number of possible sequences of games. Find the remainder when $N$ is divided by 1000.

I think I can solve this by laying out all the possible cases of $a_1,a_2,...a_7$ and $b_1,b_2,...b_7$ combinations — one such example would be $a_b,b_1,a_2,b_2,a_3,b_3,a_4,b_4,a_5,b_5,a_6,b_6,a_7,b_7$ (so team B wins). And even though I numbered each member, in truth, it really doesn't matter which exact number comes in, so we can say that all team members of A are $a$ and all team members of B are $b$. All games would start with $a,b,...$, so I think $\frac{12!}{6!6!}$ would do the trick, but I'm not completely confident if I'm over/undercounting. Any help would really be appreciated!

$\endgroup$
  • $\begingroup$ @Peter - then Player 1 of team A plays Player 2 of team B next $\endgroup$ – Henry Jan 28 at 8:32
  • $\begingroup$ OK, think I got this part. And what do we note ? $A1$ ? $\endgroup$ – Peter Jan 28 at 8:36
0
$\begingroup$

Hint:

$\frac{12!}{6!6!}=924$ would be the number of ways twelve games could be played with each team winning six of them. But here you need one team to win seven games, and the other to win fewer, for example team A could win its seventh match when B has won only four. So the number of possibilities is likely to be more than double $924$

A better approach might be to say that if team A wins overall then

  • team A must win the last game
  • team A must win $6$ other games while team B wins $n$ games, with these $6+n$ games in any order and $n \in \{0,1,2,3,4,5,6\}$

You then need to double this result since another possibility is that team B wins overall

Finally you have to do the remainder calculation

$\endgroup$
1
$\begingroup$

I think it should be $\frac{14!}{7!7!}$.

Each round one player gets eliminated. Write down in a list which team each eliminated player belongs to (A or B). Once one team is completely eliminated, you can pad the list with letters representing the still remaining players of the winning team. This will give you a list containing seven A's and seven B's. Every such list corresponds uniquely to such a series of rounds.

$\endgroup$
  • $\begingroup$ +1. That is a nice argument to show $2\sum\limits_{i=0}^n {n+i \choose i} = 2\sum\limits_{i=0}^n {n+i \choose n} = 2{2n+1 \choose n}={2n+2 \choose n+1}$ $\endgroup$ – Henry Jan 28 at 13:24
1
$\begingroup$

There is an ambiguity in the question.

If "sequence of games" means sequence of winning teams (or losing teams) then there are $\binom{14}{7}$ sequences, as Jaap Scherphuis shows.

But if "sequence of games" means sequence of pairing of players, starting with $(1,1)$ and ending with $(n,7)$ or $(7,n)$, then $\binom{14}{7}$ overcounts. This is because each sequence ending $(7,7)$ is counted twice (once when team A wins the final game, once when team B wins) whereas it should only be counted once. With this interpretation the number of sequences is $\binom{14}{7} - \binom{12}{6}$.

To illustrate the difference, consider the case of $2$ players on each team.

There are $\binom{4}{2}=6$ sequence of winning teams:

$AA\\ BAA\\ ABA\\ BB\\ ABB\\ BAB$

but only $\binom{4}{2}-\binom{2}{1}=4$ sequence of player pairs:

$(1,1),(2,1)\\ (1,1),(2,1),(2,2)\\ (1,1),(1,2)\\ (1,1),(1,2),(2,2)$

$\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.