Discrete Mathematics

Six different airlines fly from New York to Denver and seven fly from Denver to San Francisco. How many different pairs of airlines can you choose on which to book a trip from New York to San Francisco via Denver, when you pick an airline for the flight to Denver and an airline for the continuation flight to San Francisco?

Counting /

Relevant definitions for this exercise: THE PRODUCT RULE: “Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task, then there are

Six different airlines fly from New York to Denver and seven fly from Denver to San Francisco. How many different pairs of airlines can you choose on which to book a trip from New York to San Francisco via Denver, when you pick an airline for the flight to Denver and an airline for the continuation flight to San Francisco? Read More »

A multiple-choice test contains 10 questions. There are four possible answers for each question

Counting /

Let’s first write relevant definitions for this exercise: THE PRODUCT RULE: “Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task,

A multiple-choice test contains 10 questions. There are four possible answers for each question Read More »

Let(xi,yi),i = 1,2,3,4,5, be a set of five distinct points with integer coordinates in the xy plane. Show that the midpoint of the line joining at least one pair of these points has integer coordinates.

Pigeonhole principle /

The midpoint of the line joining the points (a,b) and (c,d) is ((a+c)/2,(b+d)/2). The coefficient for this midpoint will have integer coefficients if and only if both a and c, and b and d have the same parity. In other words, they are both odd, or both even. Notice that the sum of two odd

Let(xi,yi),i = 1,2,3,4,5, be a set of five distinct points with integer coordinates in the xy plane. Show that the midpoint of the line joining at least one pair of these points has integer coordinates. Read More »

Show that if f is a function from S to T, where S and T are finite sets with |S| > |T |, then there are elements s1 and s2 in S such that f(s1)=f(s2), or in other words, f is not one-to-one

Pigeonhole principle /

Let’s start this exercise with two definitions: the definition of function and the pigeonhole principle. Definition: “Let A and B be nonempty sets. A function f from A to B is an assignment of exactly one element of B to each element of A. We write f(a) = b if b is the unique element

Show that if f is a function from S to T, where S and T are finite sets with |S| > |T |, then there are elements s1 and s2 in S such that f(s1)=f(s2), or in other words, f is not one-to-one Read More »

Let d be a positive integer. Show that among any group of d + 1 (not necessarily consecutive) integers there are two with exactly the same remainder when they are divided by d

Pigeonhole principle /

Let’s start with the following definition. THE PIGEONHOLE PRINCIPLE: “If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.” Source: Discrete Mathematics and its Applications by Rosen. Let’s have d boxes numbered 0,

Let d be a positive integer. Show that among any group of d + 1 (not necessarily consecutive) integers there are two with exactly the same remainder when they are divided by d Read More »

A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random without looking at them

Pigeonhole principle /

Let’s start with the following definitions. THE PIGEONHOLE PRINCIPLE: “If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.” THE GENERALIZED PIGEONHOLE PRINCIPLE: “If N objects are placed into k boxes, then there

A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random without looking at them Read More »

Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n.

Pigeonhole principle /

To solve this exercise, we will use the fact of how many reminders of the division there can be when dividing by a certain number. If you divide by n, you can get n possible reminders. These are 0, 1, 2, …, n-1. If we have a certain set of n consecutive integers, we can

Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n. Read More »

A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at random in the dark.

Pigeonhole principle /

Let’s revisit the two principles that apply to this type of exercise. “THE PIGEONHOLE PRINCIPLE If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.” “THE GENERALIZED PIGEONHOLE PRINCIPLE If N objects are

A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at random in the dark. Read More »

A group contains n men and n women. How many ways are there to arrange these people in a row if the men and women alternate?

Permutations and combinations /

Relevant definitions to solve this exercise: “THE PRODUCT RULE Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task, then there

A group contains n men and n women. How many ways are there to arrange these people in a row if the men and women alternate? Read More »