Maths Olympiad Prep

Library / /476 of 860

Combinatorics Difficulty 5.2 AIME, harder Find the answer

Suppose AA has nn elements, where n2n \geq 2, and CC is a 2-configuration of AA that is not mm-separable for any m<nm<n. What is (in terms of nn) the smallest number of elements that CC can have?

A number or a short expression. Spacing and $ signs are ignored.

Solution

We claim that every pair of elements of A A must belong to C C , so that the answer is (n2) \binom{n}{2} . Indeed, if a,bA a, b \in A and {a,b} \{a, b\} is not in the 2-configuration, then we can assign the other elements of A A the numbers 1,2,,n2 1,2, \ldots, n-2 and assign a a and b b both the number n1 n-1 , so that C C is (n1) (n-1) -separable. On the other hand, if every pair of elements of A A is in the configuration, then A A cannot be m m -separable for m<n m<n , since this would require assigning the same number to at least two elements, and then we would have a pair whose elements have the same number.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.