Brainteaser about one set being a subset of another

Posted on 1 Sep 2025 by kjytay

Let S be a set of cardinality n. You uniformly and independently choose two subsets S_1, S_2 \subseteq S. What is the probability that S_1 \subseteq S_2?

Let’s solve this by counting the total possible number of pairs (S_1, S_2), and the number of pairs which satisfy the subset condition.

There are 2^n choices for each of S_1 and S_2, thus there are a total of 4^n possible pairs.

Now, fix S_1, and let n_1 = |S_1|. The sets which contain S_1 are exactly the 2^{n-n_1} sets which are the union of S_1 and some subset of S \setminus S_1. Thus,

\begin{aligned} \# \{ (S_1, S_2): S_1 \subseteq S_2 \} &= \sum_{S_1} 2^{n-|S_1|} \\ &= \sum_{n_1 = 0}^n \binom{n}{n_1} 2^{n - n_1} \\ &= \sum_{n_1 = 1}^n \binom{n}{n_1} 1^{n_1}2^{n - n_1} \\ &= (1 + 2)^n = 3^n. \end{aligned}

The required probability is (3/4)^n.

Posted in Uncategorized | Tagged , | Leave a comment

[Soln] Problem involving two coins

Posted on 18 Jan 2023 by kjytay

Let a, b, c \geq 0 such that a+b+c = 1. Assume we have two coins such that the probability of coin 1 landing on heads (after flipping it) is p_1 and the probability of coin 2 landing on heads is p_2.

    • For what values of (a, b, c) do there exist (p_1, p_2) such that the probability of getting 2 heads, 1 head and 1 tail, and 2 tails are a, b and c respectively?
    • What is the answer to the question above if we require p_1 = p_2?

Click for solution

Posted in Random | Tagged , | Leave a comment

Problem involving two coins

Posted on 17 Jan 2023 by kjytay

Let a, b, c \geq 0 such that a+b+c = 1. Assume we have two coins such that the probability of coin 1 landing on heads (after flipping it) is p_1 and the probability of coin 2 landing on heads is p_2.

      • For what values of (a, b, c) do there exist (p_1, p_2) such that the probability of getting 2 heads, 1 head and 1 tail, and 2 tails are a, b and c respectively?
      • What is the answer to the question above if we require p_1 = p_2?
Posted in Random | Tagged , | Leave a comment

[Soln] Carleman’s inequality

Posted on 15 Jan 2022 by kjytay

Prove Carleman’s inequality: for any sequence of positive real numbers a_1, a_2, \dots, we have

\begin{aligned} \sum_{k=1}^\infty (a_1 a_2 \dots a_k)^{1/k} \leq e \sum_{k=1}^\infty a_k, \end{aligned}

where e = 2.71828\dots is Euler’s number.

(Credits: I learnt of this inequality from J. Michael Steele’s The Cauchy-Schwarz Master Class.)

Click for solution

Posted in Uncategorized | Tagged | Leave a comment

[Hints] Carleman’s inequality

Posted on 14 Jan 2022 by kjytay

Click for hints for Carleman’s inequality

Posted in Uncategorized | Tagged | Leave a comment

Carleman’s inequality

Posted on 13 Jan 2022 by kjytay

Prove Carleman’s inequality: for any sequence of positive real numbers a_1, a_2, \dots, we have

\begin{aligned} \sum_{k=1}^\infty (a_1 a_2 \dots a_k)^{1/k} \leq e \sum_{k=1}^\infty a_k, \end{aligned}

where e = 2.71828\dots is Euler’s number.

(Credits: I learnt of this inequality from J. Michael Steele’s The Cauchy-Schwarz Master Class.)

Posted in Uncategorized | Tagged | Leave a comment

[Soln] Identifying the weight of one ingot

Posted on 11 Jan 2022 by kjytay

King Hiero II of Syracuse has 11 identical-looking metallic ingots. The king knows that the weights of the ingots are equal to 1, 2, …, 11 libras, in some order. He also has a bag, which would be ripped apart if someone were to put more than 11 libras worth of material into it. The king loves the bag and would kill if it was destroyed. Archimedes knows the weights of all the ingots. What is the smallest number of times he needs to use the bag to prove the weight of one of the ingots to the king?

(Credits: I discovered this problem on Tanya Khovanova’s blog, who in turn got it from the 2016 All-Russian Olympiad.)

Click for solution

Posted in Russia | Tagged , , , | Leave a comment

[Hints] Identifying the weight of one ingot

Posted on 10 Jan 2022 by kjytay

Click for hints for Identifying the weight of one ingot

Posted in Russia | Tagged , , , | Leave a comment

Identifying the weight of one ingot

Posted on 9 Jan 2022 by kjytay

King Hiero II of Syracuse has 11 identical-looking metallic ingots. The king knows that the weights of the ingots are equal to 1, 2, …, 11 libras, in some order. He also has a bag, which would be ripped apart if someone were to put more than 11 libras worth of material into it. The king loves the bag and would kill if it was destroyed. Archimedes knows the weights of all the ingots. What is the smallest number of times he needs to use the bag to prove the weight of one of the ingots to the king?

(Credits: I discovered this problem on Tanya Khovanova’s blog, who in turn got it from the 2016 All-Russian Olympiad.)

Posted in Russia | Tagged , , , | Leave a comment

2017/18 British MO Round 2 Problem 1

Posted on 26 Apr 2019 by kjytay

2017/18 BMO2 1. Consider the triangle ABC. The midpoint of AC is M. The circle tangent to BC at B and passing through M meets the line AB again at P. Prove that AB \times BP = 2BM^2.

(Credit: This problem was brought to my attention by Marko.)
Click for solution

Posted in Grade 12, UK | Tagged , , , | Leave a comment