MathDB
Problems
Contests
National and Regional Contests
India Contests
India LIMIT
2020 LIMIT
2020 LIMIT Category 2
8
8
Part of
2020 LIMIT Category 2
Problems
(1)
Independent sets and probability
Source: LIMIT 2020 Cat 2 Obj P8
5/25/2020
Let
S
S
S
be a finite set of size
s
≥
1
s\geq 1
s
≥
1
defined with a uniform probability
P
\mathbb{P}
P
( i.e. for any subset
X
⊂
S
X\subset S
X
⊂
S
of size
x
x
x
,
P
(
x
)
=
x
s
\mathbb{P}(x)=\frac{x}{s}
P
(
x
)
=
s
x
). Suppose
A
A
A
and
B
B
B
are subsets of
S
S
S
. They are said to be independent iff
P
(
A
)
P
(
B
)
=
P
(
A
∩
B
)
\mathbb{P}(A)\mathbb{P}(B)=\mathbb{P}(A\cap B)
P
(
A
)
P
(
B
)
=
P
(
A
∩
B
)
. Which if these is sufficient for independence?(A)
∣
A
∪
B
∣
=
∣
A
∣
+
∣
B
∣
|A\cup B|=|A|+|B|
∣
A
∪
B
∣
=
∣
A
∣
+
∣
B
∣
(B)
∣
A
∩
B
∣
=
∣
A
∣
+
∣
B
∣
|A\cap B|=|A|+|B|
∣
A
∩
B
∣
=
∣
A
∣
+
∣
B
∣
(C)
∣
A
∪
B
∣
=
∣
A
∣
⋅
∣
B
∣
|A\cup B|=|A|\cdot |B|
∣
A
∪
B
∣
=
∣
A
∣
⋅
∣
B
∣
(D)
∣
A
∩
B
∣
=
∣
A
∣
⋅
∣
B
∣
|A\cap B|=|A|\cdot |B|
∣
A
∩
B
∣
=
∣
A
∣
⋅
∣
B
∣
limit
Sets
probability