Skip to main content
OlympiadHQ

Browse · MathNet

Print

SAUDI ARABIAN MATHEMATICAL COMPETITIONS

Saudi Arabia counting and probability

Problem

A set is called neighboring if it has the following two properties: i) has exactly 4 elements, ii) for every element at least one of the or belongs to . Find the number of all neighboring subsets of the set .
Solution
Let be the smallest index and be the largest index of the neighboring set. Then our set consists of elements So the number of neighboring sets is equal to the number of pairs where . The number of such sets is equal to
Final answer
((n-3)(n-2))/2

Techniques

Recursion, bijection