Tag Archive

You are currently browsing the tag archive for the ‘inclusion-exclusion principle’ tag.

Solution to POW-2: Diagonal slicing through squares

May 22, 2008 in Elementary Math Problem Solving, Problem Corner, Problem of the Week (POW), Puzzles | Tags: inclusion-exclusion principle | by Todd Trimble | Leave a comment

The solutions are in! We had a good response to last week’s problem:

Consider a rectangle with sides of integer lengths $a$ and $b$ , subdivided into $ab$ unit squares, and a diagonal line from corner to corner. Show that the number of unit squares that the line crosses is $a+b-\gcd(a,b)$ . (Count only those cases where the line crosses the interior of a square.)
What would be the $n$ -dimensional analogue of the previous problem? How would you prove it?

The solution below is due to Paul Shearer (University of Michigan):

Solution to POW-2: We’ll solve part 2, which subsumes part 1.

Let $a = (a_1, ... , a_n)$ be the vector of box sidelengths, and $n(a)$ the number of boxes crossed by the diagonal going from 0 to a. Then we claim

$n(a) = \sum_{S \subseteq [n], S \neq \emptyset } (-1)^{|S| - 1} \gcd(\{a_i\}_{i \in S})$

where $|S|$ denotes the cardinality of a set $S$ . [Note that for $n=2$ , this simplifies to $n(a) = a_1 + a_2 - \gcd(a_1,a_2)$ , the result of part 1.]

Proof: Parametrize the diagonal by the function $f(t) = ta$ for $t \in [0,1]$ , and let $f_i(t)$ denote the $i^{th}$ coordinate of $f(t)$ . Defining [ $n$ ] $= \{1,2, \ldots, n\}$ , we have

$n(a) = | \{t \in [0,1) : f_i(t) \in \mathbb{Z} \mbox{ for some } i \in [n]\} |.$

[Proof: let $T = \{t_0 = 0$ < $t_1$ < … $t_n$ < $1\}$ be the set on the right-hand side. Each $t_i$ corresponds to an interval $(t_i, t_{i+1})$ where the line is in the interior of exactly one box, since a point in a box is interior if none of its coordinates is an integer. Hence there is a bijection between $t_i$ ‘s and boxes crossed.]

For $i = 1, \ldots, n$ , let $A_i = \{t \in [0,1) : f_i(t) \in \mathbb{Z}\}$ . Then

$n(a) = | T | = | \bigcup_{i \in [n]} A_i | = \sum_{S \subseteq [n]} (-1)^{|S| - 1} | \bigcap_{i \in S} A_i |$

by the inclusion-exclusion principle, so we need only verify that $| \bigcap_{i \in S} A_i | = \gcd(\{a_i\}_{i \in S})$ . Indeed, given $t$ , $ta_i$ will be an integer for all $i \in S$ if and only if $t = k/gcd(\{a_i\}_{i \in S})$ for $k = 0, 1..., \gcd(\{a_i\}_{i \in S})-1$ , i.e. for $\gcd(\{a_i\}_{i \in S})$ different values of $k$ . $\Box$

Remarks: Philipp Lampe notes that the case $n = 3$ is given by Andreescu and Feng, A Path to Combinatorics for Undergraduates: Counting Strategies (Birkhäuser, 2004). He also gave a solution from which a proof of the inclusion-exclusion principle (which involves binomial coefficients) can be extracted. A number of people gave the correct formula for general $n$ , but full credit was given only for complete proofs.

Also solved by Sune Jakobsen, Philipp Lampe. Solutions to part 1. were given by Jimbo Doe, Jason Dyer, and Marni Sheppeard.

Inclusion-Exclusion Principle: Counting all the objects outside the oval regions!

March 20, 2008 in Exposition, Some theorems | Tags: inclusion-exclusion principle, Polya, Szego | by Vishal | 18 comments

Part 2:

After having understood the inclusion-exclusion principle by working out a few cases and examples in my earlier post, we are now ready to prove the general version of the principle.

As with many things in mathematics, there is a “normal” way of doing proofs and there is the “Polya/Szego” way of doing proofs. (Ok, ok, I admit it’s just a bias I have.) I will stick to the latter. Ok, let’s state the principle first and follow it up with its proof in a step-by-step fashion.

Inclusion-Exclusion Principle: Let there be a set of $N$ objects. Suppose out of these $N$ objects, there are $N_a$ objects of type $a$ , $N_b$ objects of type $b, \ldots ,$ $N_k$ objects of type $k$ and $N_l$ objects of type $l$ . Also, suppose $N_{ab}, N_{ac}, \ldots , N_{abc}, \ldots , N_{ab \ldots kl}$ denote the number of objects that are simultaneously of type $a$ AND $b,$ $a$ AND $c, \ldots , a, b$ AND $c, \ldots , a, b, c, k$ AND $l,$ respectively. Then, the number of objects that are NOT of type $a, b, c, \ldots , k, l$ is

$N - (N_a + N_b + \ldots + N_k + N_l)$

$+ (N_{ab} + N_{ac} + \ldots + N_{kl})$

$- (N_{abc} + \ldots ) + \ldots$

$\pm N_{abc \ldots kl}$ .

— Notation —

Let $U$ (finite or infinite) be the universe of discourse. Suppose $A \subset U$ . Then, the characteristic function $1_A: U \to \{ 0, 1 \}$ of $A$ is defined as

$1_A (x) = 1$ if $x \in A$ ,

and $1_A(x) = 0$ otherwise, for all $x \in U$ .

For example, suppose $U = \{ 1, 2, 3, 4, \ldots , 29, 30 \}$ . Let $A = \{ 2, 4, 6, \ldots , 28, 30 \}$ (i.e. even integers.) Then, $1_A(2) = 1_A(26) = 1, 1_A(3) = 1_A(29) = 0$ , and so on.

Note: $1_U (x) = 1$ and $1_{\emptyset}(x) = 0$ for all $x \in U$ . Here, $\emptyset$ denotes the empty set. Due to this, we will use $1$ and $1_U$ interchangeably from now.

—

Lemma 1: $A \subset B$ iff $1_A(x) \le 1_B(x)$ for all $x \in U$ .

Proof: We first prove the “only if”part. So, suppose $A \subset B$ . Let $x \in U$ . If $x \in A$ , then $1_A(x) = 1$ . But, we also have $x \in B$ , in which case, $1_B(x) = 1$ . If, on the other hand, $x \notin A$ , then $1_A(x) = 0 \le 1_B(x)$ . Hence, in either case, $1_A(x) \le 1_B(x)$ for all $x \in U$ .

We now prove the “if” part. So, suppose $1_A(x) \le 1_B(x)$ for all $x \in U$ . Let $x \in A$ . Then, $1_A(x) = 1$ , which forces $1_B(x) = 1$ , which implies $x \in B$ . Hence, $A \subset B$ , and this completes our proof.

Note: If $U$ is finite, then $\displaystyle |A| = \sum_{x \in U}1_A(x)$ .

Lemma 2: $1_{A^c}(x) = 1 - 1_A(x) ,$

$1_{A \cap B}(x) = 1_A(x) 1_B(x),$ and

$1_{A \cup B}(x) = 1 - (1 - 1_A(x))(1 - 1_B(x))$

for all $x \in U$ . (Here, $A^c$ is the complement of $A$ .)

Proof: The proof for each case is elementary.

Lemma 3: Suppose $U$ is finite. If $A, B, C, \ldots \subset U$ , then the characteristic function of $A \cup B \cup C \cup \ldots$ is $1 - (1 - 1_A)(1 - 1_B)(1 - 1_C) \ldots$ , i.e.

$1_{A \cup B \cup C \cup \ldots}(x) = 1 - (1 - 1_A(x))(1 - 1_B(x))(1 - 1_C(x)) \ldots$ for all $x \in U$ .

Proof: Note the above is an extension of the third part of lemma $(2)$ . A simple induction on the number of subsets of $U$ proves the result.

— Proof of the inclusion-exclusion principle —

Now, suppose $A, B, C, \ldots, K, L$ are subsets of objects of type $a, b, c, \ldots, k, l$ , respectively. Observe that the set of objects that are NOT of type $a, b, c, \ldots , k, l$ is simply the region outside of all the oval regions! (Look at the previous post to see what this means.) And this region is simply the subset $(A \cup B \cup B \cup \ldots \cup K \cup L)^c$ . Using the first part of lemma $(2)$ , we see that the characteristic function of this outside region is $1 - 1_{A \cup B \cup B \cup \ldots \cup K \cup L}$ , which from lemma $(3)$ is the same as

$(1-1_A)(1-1_B)(1-1_C) \ldots (1-1_K)(1-1_L)$ .

Expand the last expression to get

$1 - (1_A + 1_B + 1_C + \ldots)$

$+ (1_A1_B + 1_A1_C + \ldots)$

$- (1_A1_B1_C + \ldots) + \ldots$

$\pm 1_A1_B\ldots 1_L$ .

Now, sum over all the elements of $U$ and use the second part of lemma $(2)$ to obtain the desired result. And this completes our proof.

Inclusion-Exclusion Principle: Counting all the objects outside the oval regions!

March 18, 2008 in Exposition, Some theorems | Tags: inclusion-exclusion principle, venn diagram | by Vishal | 2 comments

Part 1:

A couple of weeks ago, my friend John (from UK) asked me if I could explain the Inclusion-Exclusion Principle to him. Wikipedia contains an article on the same topic but John felt that it wasn’t a very helpful introduction. So, as promised, here is the post on that topic, though I managed to finish it only after some delay. (Sorry, John!)

As the title of this post suggests, the inclusion-exclusion principle can simply be described as counting all the objects outside the oval regions! We will use Venn diagrams to explain what that means.

Note: $\lfloor x \rfloor$ denotes the greatest integer less than $x$ .

Ok, let’s now “build” the principle step by step.

1. Suppose there are $N$ objects out of which there are exactly $N_a$ objects of type $a$ . How many objects are NOT of type $a$ ? The answer is obvious: $N - N_a$ . The Venn diagram below depicts the answer pictorially. The rounded rectangular region (with the orange border) is the set of all $N$ objects, and the oval region (with the blue border) is the set of all $N_a$ objects of type $a$ . Then, the remaining white region that is outside the oval region denotes the set of all objects that are NOT of type $a$ , and clearly, there are $N - N_a$ of ’em.

Indeed, let us take a simple example. Consider the set of first thirty natural numbers: $\{ 1, 2, \ldots , 30 \}$ . So, $N = 30$ . Now, out of these thirty integers, let $N_2$ be the number of integers divisible by $2$ . Then, $N_2 = \lfloor 30/2 \rfloor = 15$ . It is easy to see that the number of integers NOT divisible by $2$ equals $N - N_2 = 30 - 15 = 15$ , which is what we would expect if we were to list all the integers not divisible by $2$ . Indeed, those integers are $1, 3, 5, \ldots , 29$ .

2. Now, suppose there are $N$ objects out of which there are exactly $N_a$ objects of type $a$ and $N_b$ objects of type $b$ . Also, suppose there are exactly $N_{ab}$ objects that are of both type $a$ AND $b$ . Then, how many objects are NOT of type $a$ OR $b$ ? The Venn diagram below illustrates this case.

Again, we are counting the number of objects outside the two oval regions. To answer the above question, we first need to determine the number of objects inside the two oval regions, and then subtract this number from the total, which is $N$ . Now, one might be tempted to think that the number of objects inside the two oval regions is simply $N_a + N_b$ . But this is only true if the two oval regions don’t intersect (i.e. they have no objects in common.) In the general case, however, the expression $N_a + N_b$ counts $N_{ab}$ twice! And so, we must subtract $N_{ab}$ from the expression to get $N_a + N_b - N_{ab}$ as the exact number of objects inside the two oval regions. We can now see that the number of objects outside the two oval regions equals $N - (N_a + N_b - N_{ab}) = N - (N_a + N_b) + N_{ab}$ , and we are done.

Continuing with our example used earlier, let $N_3$ be the number of integers divisible by $3$ . Also, let $N_6$ be the number of integers divisible by $2$ AND $3$ (i.e. we count multiples of $6$ .) Now, note that $N_3 = \lfloor 30/3 \rfloor = 10$ , and $N_6 = \lfloor 30/6 \rfloor = 5$ .

Thus, using the formula derived above, the number of integers that are NOT divisible by $2$ OR $3$ equals $N - (N_2 + N_3) + N_6 = 30 - (15 + 10) + 5 = 10$ . In fact, we can list these ten integers: $1, 5, 7, 11, 13, 17, 19, 23, 25$ and $29$ ; and this confirms our answer.

3. Now, suppose there are $N$ objects out of which there are exactly $N_a$ objects of type $a$ , $N_b$ objects of type $b$ and $N_c$ objects of type $c$ . Also, let $N_{ab}$ denote the number of objects of type $a$ AND $b$ , $N_{bc}$ the number of objects of type $b$ AND $c$ , $N_{ca}$ the number of objects of type $c$ AND $a$ , and $N_{abc}$ the number of objects of type $a, b$ AND $c$ . Then, how many objects are NOT of type $a, b$ OR $c$ ? This case is illustrated by the Venn diagram shown below.

Once again, let us ask, what is the number of objects inside the three oval regions. A possible answer is $N_a + N_b + N_c$ . Now this will only be true if the three oval regions are pairwise disjoint. In the general case, however, we will have to take care of overcounting, just as we did in $(2)$ earlier. A brief thought will reveal that in the above expression, we have counted each of $N_{ab}, N_{bc}$ and $N_{ca}$ twice and $N_{abc}$ thrice! To take care of this overcounting, we subtract each of $N_{ab}, N_{bc}$ and $N_{ca}$ once from the expression, but in doing so, we also end up subtracting $N_{abc}$ thrice! We thus need to add $N_{abc}$ back into the expression to get $N_a + N_b + N_c - N_{ab} - N_{bc} - N_{ca} + N_{abc}$ , and this expression yields the exact number of objects inside the three oval regions. Therefore, the number of objects outside the three oval regions equals $N - (N_a + N_b + N_c) + (N_{ab} + N_{bc} + N_{ca}) - N_{abc}$ . And, we are done.

Again, continuing with our earlier example, let $N_5$ denote the number of integers divisible by $5$ . Then, $N_5 = \lfloor 30/5 \rfloor = 6$ . Also, let $N_{15}$ denote the number of integers divisible by $3$ AND $5$ (i.e. we are counting multiples of $15$ ); then, $N_{15} = \lfloor 30/15 \rfloor = 2$ . Again, let $N_{10}$ denote the number of integers divisible by $2$ and $5$ ; then $N_{10} = \lfloor 30/10 \rfloor = 3$ . And, finally, let $N_{30}$ denote the number of integers divisible by $2, 3$ and $5$ ; then $N_{30} = \lfloor 30/30 \rfloor = 1$ .

So, the number of integers NOT divisible by $2, 3$ OR $5$ equals $N - (N_2 + N_3 + N_5) + (N_{6} + N_{15} + N_{10}) - N_{30}$

$= 30 - (15 + 10 + 6) + (5 + 2 + 3) - 1 = 8$ . Indeed, those eight integers are $1, 7, 11, 13, 17, 19, 23$ and $29$ .

It isn’t very hard to deduce the formula for the general case when we have a set of $N$ objects, out of which there are $N_a$ objects of type $a$ , $N_b$ objects of type $b$ , and so on. The proof of the general formula will follow in the next post, which may include a couple of problems/solutions involving this principle.

	Strong equidistribut… on Platonic Solids and Euler…
	m.s.mohamed ansari on The 54th Carnival of Math…
	Convictions ·… on Continued fraction for e
	Wayne J. Mann on Solution to POW-12: A graph co…
	erneststephen on The 54th Carnival of Math…
	anhtraisg on p^q + q^p is prime
	prof dr drd horia or… on My first post
	prof drd horia orasa… on My first post
	prof dr mircea orasa… on Inequality with log
	notedscholar on Self-referential Paradoxes, In…
	prof dr mircea orasa… on Inequality with log
	prof dr mircea orasa… on Inequality with log
	prof dr mircea orasa… on 2010 in review
	kenji on Basic category theory, I
	prof dr mircea orasa… on Solution to POW-10: Another ha…

Tag Archive

Solution to POW-2: Diagonal slicing through squares

Inclusion-Exclusion Principle: Counting all the objects outside the oval regions!

Inclusion-Exclusion Principle: Counting all the objects outside the oval regions!

Our other blog

Visitors to this blog

Blog Stats

Wikio Ranking

Current Online Readers

Recent Comments

Top Posts

Archives

Categories

Blogroll

chess

Computers and Technology

Elementary Math Problem Solving

Fun, Humor

Higher Mathematics

Math Education

Non-technical

Opinions

People in Computer Science

People in mathematics

Philosophy & Logic

Physics

Politics, News

Sciences

Useful general links

Useful Math Links

Tag Cloud

Admin/Users Login

Pages