# Cardinality of the subsets

Mathematics Asked by Rajat Taneja on October 24, 2020

Let $$S$$ be a collection of subsets of $${1,2,dots,100}$$ such that the intersection of any two sets in $$S$$ is non empty.

What is the maximum possible cardinality $$|S|$$ of set $$S$$?

It's possible to get to $$2^{99}$$ sets by taking the set of all subsets containing 1.

It's not possible to get to any more than $$2^{99}$$ sets because if we did, we'd have a set and its complement both in $$S$$.

Answered by Doctor Who on October 24, 2020

As $${1,2,...,100}$$ is a finite set, then we can say that all sets in $$S$$ has a common element. Let $$1$$ be the common element. Then each other element can either be in or not be in a given subset. So using basic combinatorics, the total number of possible subsets with $$1$$ as one of its elements is $$2^{99}$$, as there are 99 other elements to choose from. So that's your answer. Total of $$2^{99}$$ sets in collection $$S$$.

Sorry for bad formatting by the way.

Answered by 006 Delta on October 24, 2020

## Related Questions

### What is the solution of this summation?

4  Asked on February 12, 2021 by arko-chowdhury

### Number of fixed points of a random permutation

1  Asked on February 12, 2021 by aliba

### Find $a$, $b$ such that $x^2 – x -1$ is a factor of $ax^9 + bx^8 + 1$

6  Asked on February 12, 2021 by aniruddha-deb

### “Standard theorem on differential equations” that implies a function is analytic

0  Asked on February 12, 2021 by stannisba

### Identity up to isomorphism treated as identity in proof

1  Asked on February 12, 2021 by roland-salz

### Burnside’s Lemma bracelet with beads in 2 colours (uneven cardinality)

1  Asked on February 12, 2021 by patrycja

### Prove $2^{lceil lg (n-1) rceil} ge n-1$

1  Asked on February 12, 2021 by hiep

### Identify boolean function that satisfies some constrains

1  Asked on February 11, 2021

### How to show that the curve $ay^2=x(x-a)(x-b)$ has two and only two points of inflexion?

1  Asked on February 11, 2021 by theunixdisaster

### volume under a 3-d curve

0  Asked on February 11, 2021

### Groups of $3$ out of $23$ s.t. all students cooperate exactly once

2  Asked on February 11, 2021 by nikolaos-skout

### (Manifolds) Prove the following is a sufficient condition for a function to be a morphism between manifolds

0  Asked on February 11, 2021 by itamar-e-aharoni

### existence of countably additive measure for Borel subsets of $[0,1]$

1  Asked on February 11, 2021

### Are the two spans equal?

3  Asked on February 11, 2021 by martyna

### Simplifying iterated sums where the upper bound is the next index

1  Asked on February 11, 2021 by user196574

### Mathematical Writing: Can objects in a definition be assigned any name, even though this name is used elsewhere in the text?

1  Asked on February 11, 2021 by clapham

### $T:P_nlongrightarrow P_n : Tp(t)=frac{d}{dt}p(t)text{ Find the norm of the operator}$

1  Asked on February 11, 2021

### Method to solve an equation

1  Asked on February 10, 2021 by khosrotash

### Prove that $sum_{n=1}^infty frac{x^{2n}}{(n+x)^2}$ converges uniformly on $S=[0,1]$

0  Asked on February 10, 2021 by naturalmathlover

### Find moment generating function for $sqrt{n}(overline{X}-1)$

0  Asked on February 10, 2021 by diego-andres-gomez-polo

### Ask a Question

Get help from others!