Maths Olympiad Prep

Library / /218 of 377

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:

Suppose AA is a set with nn elements, and kk is a divisor of nn. Find the number of consistent kk-configurations of AA of order 1.

Solution

Solution:

Given such a kk-configuration, we can write out all the elements of one of the kk-element subsets, then all the elements of another subset, and so forth, eventually obtaining an ordering of all nn elements of AA. Conversely, given any ordering of the elements of AA, we can construct a consistent kk-configuration of order 1 from it by grouping together the first kk elements, then the next kk elements, and so forth. In fact, each consistent kk-configuration of order 1 corresponds to (n/k)!(k!)n/k(n / k)! (k!)^{n / k} different such orderings, since the elements of AA within each of the n/kn / k kk-element subsets can be ordered in k!k! ways, and the various subsets can also be ordered with respect to each other in (n/k)!(n / k)! different ways. Thus, since there are n!n! orderings of the elements of AA, we get
n!(n/k)!(k!)n/k \frac{n!}{(n / k)! (k!)^{n / k}}
different consistent kk-configurations of order 1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.