Task list filter?

Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.

Task rankings

Difficulty level

Task tags

Task type
«
«
«

Ball

Task number: 3489

There are n couples at a ball. How many ways are there to divide everyone into pairs such that no couple dances together?

  • Solution

    Dividing everyone into pairs corresponds to a bijective mapping f from {1,,n} to the same set (e.g. the woman from the i-th couple will dance with the man from the f(i)-th couple).

    We are interested in the mappings without a fixed point; this corresponds to the hat-matching problem from the lecture.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email