Combinatorics › Combinations and selections

Choosing with gaps

Solve the first problem 17 problems

These are 8 of the 17 problems. Sign in for free to see them all. Sign in

1. Subsets with a gap pattern ●●○○○ 20 ptsDetermine the number of subsets $S$ of $\{1,2,3,\ldots,10\}$ with the following property: there exist integers $a<b<c$ with $a \in S$, $b \notin S$, $c \in S$.
2. Expected consecutive pairs in a subset ●●○○○ 20 ptsA 25-element subset is chosen uniformly at random from $\{1,2,\ldots,100\}$. Find the expected number of pairs $(i,i+1)$ of consecutive integers for which both $i$ and $i+1$ lie in the subset.
3. Four-element set from its triple sums ●●○○○ 20 ptsLet $A=\{a_1, a_2, a_3, a_4\}$ be a set of four numbers. The set $B=\{-1, 3, 5, 8\}$ consists of the sums of the elements of all the three-element subsets of $A$. Find the four elements of $A$, in increasing order.
4. Non-negative elements of a closed set ●●●○○ 50 ptsLet $S$ be the smallest subset of the integers such that $0 \in S$ and, for any $x \in S$, both $3x \in S$ and $3x+1 \in S$. Determine the number of non-negative integers in $S$ that are less than $2008$.
5. Spacy subsets of twelve integers ●●●○○ 50 ptsCall a set of integers "spacy" if it contains no more than one out of any three consecutive integers. How many subsets of $\{1, 2, 3, \dots, 12\}$, including the empty set, are spacy?
6. Expected count of numbers exceeding a neighbor ●●●○○ 50 ptsThe numbers $1$ to $10$ are written in a circle in a random order. Find the expected number of numbers that are at least $2$ larger than at least one of their two adjacent numbers. Round to two decimal places.
7. Minimum number of 7-subsets covering all triples ●●●●○ 100 ptsLet $S=\{1,2,\ldots,15\}$. Choose $n$ subsets $A_1,A_2,\ldots,A_n$ of $S$ such that: (i) $|A_i|=7$ for each $i$; (ii) $|A_i\cap A_j|\leq 3$ for all $1\leq i<j\leq n$; (iii) for every 3-element subset $M$ of $S$, there is some $k$ with $M\subset A_k$. Find the minimum possible value of $n$.
8. Subsets with smallest element m ●●●●○ 100 ptsDetermine all values of $m$ with $1 \leq m \leq 47$ for which there are exactly $2^{15}$ subsets $X$ of the set $\{1,2,3,\ldots,47\}$ such that $m$ is the smallest element of $X$, and for every $x \in X$, either $x+m \in X$ or $x+m>47$.

More in Combinations and selections

CommitteesPairs and matchingsPascal's triangleSplitting into groupsTeams and lineupsnCr and nPr formulas