Search problems

10 problems match “subsets”. Clear

Visitors search a sample. Sign in for free to search every problem. 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. Subsets contained in neither of two sets ●●○○○ 20 ptsFind the number of subsets of $\{1, 2, 3, 4, 5, 6, 7, 8\}$ that are subsets of neither $\{1, 2, 3, 4, 5\}$ nor $\{4, 5, 6, 7, 8\}$.
3. 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.
4. Sizes of two sets from subset counts ●●○○○ 20 ptsLet $A$ and $B$ be two finite sets. The number of subsets of $A$ minus the number of subsets of $B$ is $112$. Find the number of elements in $A$ and in $B$.
5. 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.
6. 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?
7. Counting topologies on three points ●●●○○ 50 ptsLet $X$ be a set with $3$ elements. How many topologies can be defined on $X$? Equivalently, how many subsets of the power set $\mathcal{P}(X)$ are topologies on $X$?
8. Ten numbered coins sum at least 45 ●●●○○ 50 ptsYou have 10 coins. Coin $i$ shows the number $i$ on one side (for $i = 1, \dots, 10$) and $0$ on the other side. You toss all the coins and add up the values that face up. Find the probability that the sum is greater than or equal to $45$. Give your answer as a decimal.
9. 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$.
10. 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$.