Problem 9.6. At a ball, 29 boys and 15 girls arrived. Some boys danced with some girls (no more than once in each pair). After the ball, each person told their parents how many times they danced. What is the maximum number of different numbers the children could have mentioned?
Answer: 29.

Solution. The largest possible number that could have been named is 29 (in the case where there is a girl who danced with all the boys), and the smallest is 0. Thus, we have that the number of different numbers named is no more than 30.

We will prove that it cannot be exactly 30. Suppose the opposite, that all numbers from 0 to 29 were named. Then the numbers from 16 to 29 were named only by girls (this is already 14 numbers). The number 0 was definitely not named by a boy, since there is a girl who danced with all the boys. This means that the girls must have named exactly fifteen numbers: 0, 16, 17, 18, ..., 29.

At the same time, the number 15 was not named by any of the girls, since it is already known which numbers they named. If the number 15 was named by a boy, it would mean that he danced with all the girls. But there is a girl who named the number 0, who did not dance with anyone. Contradiction.

Now we will show how 29 different numbers could have been named. Let's number the girls from 1 to 15 and the boys from 1 to 29. Let boy $i$ dance with girl $j$ if and only if $i \geqslant j$.

We can illustrate this example with a $15 \times 29$ table: we will assign a column of the table to each boy and a row to each girl; if a boy danced with a girl, we will color the cell at the intersection of the corresponding row and column. In Fig. 4, above each column is written how many cells are colored in it; to the left of each row is written how many cells are colored in it.

![](https://cdn.mathpix.com/cropped/2024_05_06_6da73bfd3e09e8b55e3fg-36.jpg?height=448&width=779&top_left_y=1112&top_left_x=337)

Fig. 4: example for the solution to problem 9.6