Carpet Strategy in Geometry | Watch and Learn

Here is a video solution for a Problem based on Carpet Strategy in Geometry. This problem is helpful for Math Olympiad, ISI & CMI Entrance, and other math contests. Watch and Learn!

Here goes the question…

Suppose ABCD is a square and X is a point on BC such that AX and DX are joined to form a triangle AXD. Similarly, there is a point Y on AB such that DY and CY are joined to form the triangle DYC. Compare the area of the triangles to the area of the square.

We will recommend you to try the problem yourself.

Done?

Let’s see the solution in the video below:

Some Useful Links:

Related Program

Bijection Principle Problem | ISI Entrance TOMATO Obj 22

Here is a video solution for a Problem based on Bijection Principle. This is an Objective question 22 from TOMATO for ISI Entrance. Watch and Learn!

Here goes the question…

Given that: x+y+z=10, where x, y and z are natural numbers. How many such solutions are possible for this equation?

We will recommend you to try the problem yourself.

Done?

Let’s see the solution in the video below:

Some Useful Links:

Related Program

Vandermone's SRSWR | MStat 2017 PSB Problem 3

This is a beautiful problem form ISI MStat 2017 PSB Problem 3, where we use the basics of Bijection principle and Vandermone's identity to solve this problem.

Problem

Consider an urn containing 5 red, 5 black, and 10 white balls. If balls are drawn without replacement from the urn, calculate the probability that in the first 7 draws, at least one ball of each color is drawn.

Prerequisites

Algebrify the problem
Vandermone's Identity $${{n_{1}+\cdots+n_{p}} \choose m} = \sum_{k_{1}+\cdots+k_{p}=m} {n_{1} \choose k_{1}} \times {n_{2} \choose k_{2}} \times \cdots \times {n_{p} \choose k_{p}}$$

Bijection Principle

Solution

It may give you the intuition, there is atleast in the problem, so let's do complementing counting. Okay! I suggest you to travel that path to help you realize the complexity of that approach.

Nevertheless, let's algebrify the problem.

You want to select $x_1$ red balls, $x_2$ blue balls, and $x_3$ white balls so that $x_1 + x_2 + x_3 = 7$.

Now, $ 1 \leq x_1 \leq 5$, $1 \leq x_2 \leq 5$ and $1 \leq x_3 \leq 10$ represents our desired scenario.

$ 0 \leq x_1 \leq 5$, $0 \leq x_2 \leq 5$ and $ 0 \leq x_3 \leq 10$ denotes total number of cases.

Now, for each such triplet ($x_1, x_2, x_3$) of the number of balls of each colour we have selected, we can select them in $ { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3} $.

Let $ P = \{ (x_1, x_2, x_3) | x_1 + x_2 + x_3 = 7, 0 \leq x_1 \leq 5, 0 \leq x_2 \leq 5, 0 \leq x_3 \leq 10 \} $.

Total Number of Ways we can select the 7 balls =

$$ \sum_{(x_1, x_2, x_3) \in P} { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3} = { {5 + 5 + 10} \choose { x_1 + x_2+ x_3} } = { {5 + 5 + 10} \choose {7} }$$

$ Q = \{ (x_1, x_2, x_3) | x_1 + x_2 + x_3 = 7, 1 \leq x_1 \leq 5, 1 \leq x_2 \leq 5, 1 \leq x_3 \leq 10 \} $.

Total Number of Ways we can select the 7 balls such that at least one ball of each color is drawn =

$$ \sum_{(x_1, x_2, x_3) \in Q} { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3}$$

Let, $ R = \{ (z_1, z_2, z_3) | z_1 + z_2 + z_3 = 4, 0 \leq z_1 \leq 4, 0 \leq z_2 \leq 4, 0 \leq z_3 \leq 9 \} $.

Observe that $Q$ has a bijection with $R$. $ x_i = z_i +1$.

Total Number of Ways we can select the 7 balls such that at least one ball of each color is drawn =

$$ \sum_{(x_1, x_2, x_3) \in R} { 4 \choose z_1} \times {4 \choose z_2 } \times {9 \choose z_3} = { {4 + 4 + 9} \choose { z_1 + z_2+ z_3} } = { {4 + 4 + 9} \choose {4} }$$

Exercises

Prove the Vandermone's Identity.
Find the Probability.
Generalize the problem to general numbers and prove it.
Generalize the problem where the lower bounds of $x_i$ are $m_i$.
What if there are upper bounds on $(x_1, x_2, x_3)$? [ Hint: Generating Functions ].

Stay Tuned! Stay Blessed!

Counting Double Subsets | ISI MStat 2014 Sample PSB Problem 3

This problem is an extension of the bijection principle idea used in counting the number of subsets of a set. This is ISI MStat 2014 Sample Paper PSB Problem 3.

Problem

Let $ S = \{1,2, \ldots, n\} $
(a) In how many ways can we choose two subsets $A$ and $B$ of $S$ so that $B \neq \emptyset$ and $B \subseteq A \subseteq S$ ?
(b) In how many of these cases is $B$ a proper subset of $A$ ?

Prerequisites

Generalization of the idea of counting the total number of subsets of a set.

Solution

It is the same idea as counting the total number of subsets of a set. We used coding schemes.

Coding Scheme

We need three parameters to take note

$b$ if that element is in $B \subseteq A$.
$a$ if that element is extra in $A$ and not in $B$.
$0$ if that element is not included in $A$ hence not in $B$.

Example

For $ S = \{1,2, 3, 4, 5, 6\} $.

The coding scheme $ (1, 2, 3, 4, 5, 6) = (a, b, 0, 0, a, a) $ means

$ B = \{ 2 \}, A = \{ 1, 2, 5, 6\}$.

The total number of ssuch strings without any restrictions on number of $b$ or $a$ = $3^n$ since, for each of the $n$ elements of $S$, there are three options {$a, b$, 0}.

The total number of cases with $B = \emptyset$ = The total number of cases with zero $b$ = $2^n$, since for each of the $n$ elements of $S$, there are two options {$a$, 0}.

The total number of cases $B$ is not a proper subset of $A$ = The total number of cases {$ A = B$} = The total number of cases with zero $a$ = $2^n$, since for each of the $n$ elements of $S$, there are two options {$b$, 0}.

(a)

We need to count how many such strings are there using atleast one $b$.

The total number of strings using atleast one $b$ =

the total number of cases without any restrictions - the total number of cases with zero $b$.

= $3^n - 2^n$

(b)

We need to count how many such strings are there using atleast one $a$ and one $b$.

The total number of strings using atleast one $a$ and one $b$ =

The total number of strings using atleast one $b$ - The total number of strings using atleast one $b$ and zero $a$

= The total number of strings using atleast one $b$ - The total number of strings using atleast one $b$ out of {$b, 0$}

= $3^n - 2^n$ - $ 2^n - 1$ = $3^n - 2^{n+1} +1$

Other Methods

You can also do it by using methods of Conditional Expectation and Smoothing method, taking a uniform distribution over $S$. If you have done it in that way, let us know, we will add the solution to the post.

Stay Tuned! Stay Blessed!

Non-Consecutive Selection | ISI MStat 2019 PSB Problem 3

This problem is a beautiful and simple application of the bijection principle to count the number of non-consecutive selection of integers in combinatorics from Problem 3 of ISI MStat 2019 PSB.

Problem - Non-Consecutive Selection

Elections are to be scheduled for any seven days in April and May. In how many ways can the seven days be chosen such that elections are not scheduled on two consecutive days?

Prerequisites

$a < b$, then $a$ and $b+1$ are never consecutive.
Combination ( Choose Principle )
Bijection Principle

Solution

The problem is based on the first prerequisite mainly. That idea mathematicalizes the problem.

Out of the 61 days in April and May, we have to select 7 non-consecutive days. Let's convert this scenario to numbers.

Out of {$1, 2, 3, ... , 61$}, we have to select 7 non-consecutive numbers.

Lemma

$y_1 < y_2 < y_3 < ... < y_7$ are 7 non-consecutive numbers $ \iff$ $y_i$ is of the form $ x_i + (i-1) $ where $x_1 < x_2 < x_3 < ... < x_7$.

For example

You select {1, 3, 4, 5, 6, 8}. You change it to {1, 3 + 1, 4 + 2 , 5 + 3, 6 + 4 , 8 + 5} = { 1, 4, 6, 8, 10 , 13}, which are never consecutive.

Essentially, we are counting the non-consecutive integers in a different way, which helps us to count them.

So, we have to choose $x_1 < x_2 < x_3 < ... < x_7$, where the maximum $x_7 + (7-1) = x_7 + 6 \leq 61 \Rightarrow x_7 \leq 55$.

Hence, the problem boiled down to choosing $x_1 < x_2 < x_3 < ... < x_7$ from {$1, 2, 3, ... , 55$}, which is a combination problem.

We can have to just choose 7 such numbers. The number of ways to do so is $ {55}\choose{7}$.

Bijection Principle from I.S.I. Entrance

Try the problem

This problem of Bijection Principle is from B.Stat, B.Math Entrance.

How many natural numbers less that $ 10^8 $ are there, whose sum of digits equals 7?

Watch the first hint