1.2.4 problem 22

(a)

Let us count the number of games in a round-robin tournament with $n+1$ participants in two ways.

Method 1: Since every player plays against all other players exactly once, the problem reduces to finding the number of ways to pair up $n+1$ people. There are $\left(\frac{n+1}{2}\right)$ ways to do so.

Method 2: The first player participates in $n$ games. The second one also participates in $n$ games, but we have already counted the game against the first player, so we only care about $n-1$ games. The third player also participates in $n$ games, but we have already counted the games against the first and second players, so we only care about $n-2$ games.

In general, player $i$ will participate in $n+1-i$ games that we care about. Taking the sum over $i$ we get

$$n+(n-1)+(n-2)+\cdots +2+1$$

Since both methods count the same thing, they are equal.

An Alternative Approach The RHS expression counts number of ways to pair two people from a group of $n+1$ people of different ages. Let’s say the eldest person in the subgroup of two is also the eldest person in the whole group. Then, we would have $n$ people to choose from as the second person of the sub group. If subgroup’s eldest is the second-eldest in the whole group, we’d have $n-1$ people to choose from, and so on all the way to $1$. By adding these cases, we get the LHS expression which covers all possibilities of pairing two people from group of $n+1$, and hence is equivalent to RHS.

(b)

LHS: If $n$ is chosen first, then the subsequent $3$ numbers can be any of $0,1,\dots ,n-1$. These $3$ numbers are chosen with replacement resulting in $n^3$ possibilities. Summing over possible values of $n$ we get $1^3+2^3+\cdots +n^3$ total number of possibilities.

RHS: We can count the number of permutations of the $3$ numbers chosen with replacement from a different perspective. The $3$ numbers can either all be distinct, or all be the same, or differ in exactly $1$ value.

Case 1: All $3$ numbers are distinct.

Selecting $4$ (don’t forget the very first, largest selected number) distinct numbers can be done in $\left(\frac{n+1}{4}\right)$ ways. The $3$ smaller numbers are free to permute amongst themselves. This gives us a total of $6\left(\frac{n+1}{4}\right)$ possibilities.

Case 2: All $3$ numbers are the same.

In this case, we have to select $2$ digits. The smaller digit will be sampled $3$ times and there are no ways to permute identical numbers, so the number of possiblities is $\left(\frac{n+1}{2}\right)$.

Case 3: Two of the $3$ numbers are distinct.

In this case, we have to select $3$ digits in total. One of the smaller $2$ digits will be sampled twice, giving us $3$ permutations. Since, there are $2$ choices for which digit gets sampled twice, we get a total of $6$ permutations. The total number of possibilities then is $6\left(\frac{n+1}{3}\right)$.

Adding up the number of possibilities in each of the cases we get a total of

$$6\left(\frac{n+1}{4}\right)+6\left(\frac{n+1}{3}\right)+\left(\frac{n+1}{2}\right)$$

possibilities.

Since the LHS and the RHS count the same set, they are equal.