If , find the least value of .
will be minimum when will be minimum.
Now, ….call this equation I.
Hence, z will be maximum when is maximum but is the product of two factors whose sum is .
Hence, will be maximum when both these factors are equal, that is, when
. From equation I, maximum value of . Hence, the least value of .
Some basics related to maximum and minimum:
Let a and b be two positive quantities, S their sum and P their product; then, from the identity:
, we have
Hence, if S is given, P is greatest when ; and if P is given, S is least when . That is, if the sum of two positive quantities is given, their product is greatest when they are equal; and, if the product of two positive quantities is given, their sum is least when they are equal.
To find the greatest value of a product the sum of whose factors is constant.
Let there be n factors , and suppose that their sum is constant and equal to s.
Consider the product , and suppose that a and b are any two unequal factors. If we replace the two unequal factors a and b by the two equal factors , the product is increased, while the sum remains unaltered; hence, so long as the product contains two unequal factors it can be increased without altering the sum of the factors; therefore, the product is greatest when all the factors are equal. In this case, the value of each of the n factors is , and the greatest value of the product is , or .
Corollary to Basic 2:
If are unequal, ;
that is, .
By an extension of the meaning of the terms arithmetic mean and geometric mean, this result is usually stated as follows: the arithmetic mean of any number of positive quantities is greater than the geometric mean.
To find the greatest value of when is constant; m,n, p, ….being positive integers.
Solution to Basic 3:
Since m,n,p, …are constants, the expression will be greatest when is greatest. But, this last expression is the product of factors whose sum is , or , and therefor constant. Hence, will be greatest when the factors are all equal, that is, when
Thus, the greatest value is .
Some examples using the above techniques:
Show that where r is any real number.
that is, , which is the desired result.
Find the greatest value of for any real value of x numerically less than a.
The given expression is greatest when is greatest; but, the sum of the factors of this expression is , that is, ; hence, is greatest when , that is, . Thus, the greatest value is .
The determination of maximum and minimum values may often be more simply effected by the solution of a quadratic equation than by the foregoing methods. For example:
Divide an odd integer into two integral parts whose product is a maximum.
Let an odd integer be represented as ; the two parts by x and ; and the product by y; then ; hence,
but the quantity under the radical sign must be positive, and therefore y cannot be greater than , or, ; and since y is integral its greatest value must be ; in which case , or n; thus, the two parts are n and .
Sometimes we may use the following method:
Find the minimum value of .
Put ; then the expression
which in turn equals
Hence, the expression is a a minimum when the square term is zero; that is when .
Thus, the minimum value is , and the corresponding value of x is .
Problems for Practice:
- Find the greatest value of x in order that may be greater than .
- Find the minimum value of , and the maximum value of .
- Show that and .
- Find the maximum value of when x lies between 7 and -2.
- Find the minimum value of .
Reference: Discrete Mathematics and its Applications by Kenneth H. Rosen, Seventh Edition.
In many interesting applications of the pigeonhole principle, the objects to be placed in boxes must be chosen in a clever way. A few such applications will be described here.
During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games.
Let be the number of games played on or before the jth day of the month. Then, is an increasing sequence of distinct positive integers, with . Moreover, is also an increasing sequence of distinct positive integers, with .
The 60 positive integers are all less than or equal to 59. Hence, by the pigeonhole principle two of these integers are equal. Because the integers , are all distinct, there must be indices i and j with . This means that exactly 14 games were played from day to i.
Show that among any positive integers not exceeding 2n there must be an integer that divides one of the other integers.
Write each of the integers as a power of 2 times an odd integer. In other words, let for , where is a nonnegative integer and is odd. The integers are all odd positive integers less than 2n. Because there are only n odd positive integers less than , it follows from the pigeonhole principle that two of the integers must be equal. Therefore, there are integers i and j such that . Let q be the common value of and . Then, and . It follows that if then divides . QED.
A clever application of the pigeonhole principle shows the existence of an increasing or a decreasing subsequence of a certain length in a sequence of distinct integers. Some definitions will be reviewed before this application is presented. Suppose that is a sequence of real numbers. A subsequence of this sequence is a sequence of the form , where . Hence, a subsequence is a sequence obtained from the original sequence by including some of the original sequence in their original order, and perhaps, not including other terms. A sequence is called strictly increasing if each term is larger than the one that precedes it, and it is called strictly decreasing if each term is smaller than the one that precedes it.
Every sequence of distinct real numbers contains a subsequence of length that is either strictly increasing or strictly decreasing.
An example is presented below (before the proof) of the above:
The sequence contains 10 terms. Note that . There are four increasing subsequence of length four, namely, . There is also a decreasing subsequence of length four, namely, .
The proof of the theorem is presented below:
Let be a sequence of distinct real numbers. Associate an ordered pair with each term of the sequence, namely, associate to the term , where is the length of the longest increasing subsequence starting at , and is the length of the longest decreasing subsequence starting at .
Suppose that there are no increasing or decreasing subsequences of length . Then, and are both positive integers less than or equal to n, for . Hence, by the product rule there are possible ordered pairs for . By the pigeonhole principle, two of these ordered pairs are equal. In other words, there exist terms and , with such that and . We will show that this is impossible. Because the terms of the sequence are distinct, either or . If , then, because , an increasing subsequence of length , can be built starting at , by taking followed by an increasing subsequence of length beginning at . This is a contradiction. Similarly, if , the same reasoning shows that must be greater than , which is a contradiction. QED.
Quiz based on generalized pigeonhole principle:
Assume that in a group of six people, each pair of individuals consists of two friends or two enemies. Show that there are either three mutual friends or three mutual enemies in the group.
Note: This little quiz is a motivation for Ramsey theory. This theory deals with the distribution of of subsets of elements of sets.
Reference: Discrete Mathematics and its Applications by Kenneth H. Rosen, Seventh Edition.
The Pigeonhole Principle 1:
If k is a positive integer and or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.
Corollary: A function f from a set with or more elements to a set with k elements is NOT one-to-one.
Among any group of 367 people, there must be at least two with the same birthday because there are only 366 possible birthdays.
In any group of 27 English words, there must be at least two that begin with the same letter because there are 26 letters in the English alphabet.
How many students must be in a class to guarantee that at least two students receive the same score on the final exam, if the exam is graded on a scale from 0 to 100 points?
There are 101 possible scores on the final. The pigeon hole principle shows that among any 102 students there must be at least 2 students with the same score.
The pigeonhole principle is a useful tool in many proofs, including proofs of surprising results, such as that given in the example below:
Show that for every integer n there is a multiple of n that has only 0’s and 1’s in its decimal expansion.
Let n be a positive integer. Consider the integers 1, 11, 111, , (where the last integer in this list is the integer with 1’s in its decimal expansion). Note that there are n possible remainders when an integer is divided by n. Because there are integers in this list, by the pigeonhole principle, there must be two with the same remainder when divided by n. The larger of these integers less the smaller one is a multiple of n, which has a decimal expansion consisting entirely of 0’s and 1’s.
The Generalized Pigeonhole Principle:
The pigeonhole principle states that there must be at least two objects in the same box when there are more objects than boxes. However, even more can be said when the number of objects exceeds a multiple of the number of boxes. For instance, among any set of 21 decimal digits, there must be 3 that are the same. This follows because when 21 objects are distributed into 10 boxes, one box must contain more than 2 objects.
Statement of the Generalized Pigeonhole Principle:
If N objects are placed into k boxes, then there is at least one box containing at least objects.
Please see wikipedia for properties of ceiling function. You can prove the above theorem by contradiction. Give it a try!
A common type of problem asks for the minimum number of objects such that at least r of these objects must be in one of the k boxes when these objects are distributed among the boxes. When we have N objects, the generalized pigeonhole principle tells us there must be at least r objects in one of the boxes as long as . The smallest integer N with , namely, , is the smallest integer smallest integer satisfying the inequality . Could a smaller value of N suffice? The answer is no, because if we have objects, we could put of them in each of the k boxes and no box would have at least r objects.
When thinking about problems of this type, it is useful to consider how you can avoid having at least r objects in one of the boxes as you add successive objects. To avoid adding a rth object to any box, you eventually end up with objects in each box. There is no way to add the next object without putting an rth object in that box.
Examples 5-8 illustrate how the generalized pigeonhole principle is applied.
Among 100 people there are at least who were born in the same month.
What is the minimum number of students required in a discrete mathematics class to be sure that at least six will receive the same grade, if there are five possible grades A, B, C, D, and F?
The minimum number of students needed to ensure that at least six students receive the same grade is the smallest integer N such that . The smallest such integer is If you have only 25 students, it is possible for there to be five who have received each grade so that no six students have received the same grade. Thus, 26 is the minimum number of students needed to ensure that at least six students will receive the same grade.
(a) How many cards must be selected from a standard deck of 52 cards to guarantee that at least three cards of the same suit are chosen?
(b) How many must be selected to guarantee that at least three hearts are selected?
(a) Suppose there are four boxes, one for each suit, and as cards are selected they are placed in the box reserved for cards of that suit. Using the generalized pigeonhole principle, we see that if N cards are selected, there is at least one box containing at least cards. Consequently, we know that at least three cards of one suit are selected if . The smallest integer N such that is , so nine cards suffice. Note that if eight cards are selected, it is possible to have two cards of each suit, so more than eight cards are needed. Consequently, nine cards must be selected to guarantee that at least three cards of one suit are chosen. One good way to think about this is to note that after the eighth card is chosen, there is no way to avoid having third card of some suit.
(b) We do not use the generalized pigeonhole principle to answer this question, because we want to make sure that there are three hearts, not just three cards one sort. Note that in the worst case, we can select all the clubs, diamonds, and spades, 39 cards in all, before we select a single heart. The next three cards will be all hearts, so we may need to select 42 cards to get three hearts.
What is the least number of area codes needed to guarantee that the 25 million phones in a state can be assigned distinct 10 digit telephone numbers? (Assume that the telephone numbers are of the form NXX-NXX-XXXX, where the first three digits form the area code, N represents a digit from 2 to 9 inclusive, and X represents any digit).
There are eight million different phone numbers of the form NXX-XXXX. Hence, by the generalized pigeonhole principle, among 25 million telephones , at least of them must have identical phone numbers. Hence, at least four area codes are required to ensure that all 10-digit numbers are different.
Suppose that a computer science lab has 15 workstations and 10 servers. A cable can be used to directly connect a workstation to a server. For each server, only one direct connection to that server can be active at any time. We want to guarantee that at any time any set of 10 or fewer workstations can simultaneously access different servers via direct connections. Although we could do this by connecting every workstation directly to every server (using 150 connections), what is the minimum number of direct connections needed to achieve this goal?
(These set of problems and solutions are due Laszlo Lovasz, “Combinatorial Problems and Exercises, AMS-Chelsea Publishing:
Prove the identity:
when and is if .
Some basics of the inclusion-exclusion principle are in order (by the way, this is also known as the sieve theory, named after the Sieve of Eratosthenes):
One powerful tool in the theory of enumeration as well as in prime number theory is the inclusion-exclusion principle (sieve of Eratosthenes). This relates the cardinality of the union of certain sets to the cardinalities of intersection of some of them, these latter cardinalities often being easier to handle. However, the formula does have some handicaps: it contains terms alternating in signs, and in general, it has too many of them!
(a) The Sieve Formula:
Let be arbitrary events of a probability space . For each, , let
and let ,
(b) (Inclusion-Exclusion Principle)
Let where S is a finite set, and let ; .
Let , . Then, the number of those tmappings of X into Y which are onto Y is, obviously,
if , and , if .
On the other hand, let denote the set of mappings of X into and let S be the set of all mappings of X into Y. Then, we are interested in . By the inclusion-exclusion formula:
Here, is the set of mappings of X into , hence,
which proves the assertion.
If , the result of the same inclusion-exclusion procedure is the number of mappings of X onto Y, which is .
Prove the following Abel identities:
We prove (2a) by induction on n. For , it is trivial. Let . We have
The two right-hand sides here are equal by the induction hypothesis. To prove the identity, it suffices to show that (a) holds for any one value of n. Choose . Then, the right hand side vanishes while the left hand side is
Note: In the last step we have used the following:
The left hand side of (2a) can be rewritten as
Here, the second term is
by 2a. Hence,
Dividing by identity (b) follows.
Subtract from both sides of then we get,
Letting , we obtain (c).
Let . Prove that . Find other examples of such equations of polynomials.
The number of non-congruent triangles with circumference and integer sides is equal to the number of non-congruent triangles with circumference and integer sides. This number is also equal to the number of partitions of n into exactly three terms. Determine this number.
The first assertion is easy. If integers a, b, c are the sides of a triangle with circumference , then trivially also satisfy the triangle inequality, and so they are the sides of a triangle with circumference . Conversely, if a, b, c are the sides of a triangle with circumference , then
and since, is odd, we have
Hence, , , are the sides of a triangle with circumference .
To prove the second assertion, observe that if , where x, y, z are positive integers, then
, that is, are the sides of a triangle with circumference 2n. Conversely, if integers a, b, c are the sides of such a triangle then, setting , we have
, , and also
Thus, we have a one-to-one correspondence between partitions of n and triangles with circumference (and integer sides).
To determine the number of partitions of n into exactly three terms we observe first that the number of partitions of m into exactly two terms not exceeding a is
, if .
Hence, the number of partitions , where is
It is seen that the result depends on the residue of n mod 6, example, if , then the result is .
More conundrums coming soon …!
Find non-zero distinct integers a, b and c such that the following fourth-degree polynomial with integral coefficients, can be written as the product of two other polynomials with integral coefficients:
Hint: Of course, the natural thought that comes to mind is the method of undetermined coefficients, and perhaps, some more trial and error to obtain some coefficients, and if we find these, we can find the remaining through their relationship with other coefficients. That brings to mind, Viete’s relations also !! But, there will be two cases here: in one case, the polynomial is a product of two quadratic polynomials, and in the other case, the given fourth degree polynomial is a product of a first degree polynomial and a third degree polynomial.
For which integers , where these are all distinct, are the following polynomials with integral coefficients expressible as the product of two polynomials with integral coefficients?
Hint: This is seems to be related to the previous question of fourth degree polynomial ! But, I am not sure if my hint will work ! No spoon-feeding please ! Well, that said, I will think of a clever hint in a couple of days.
Prove that if the integers are all distinct, then the polynomial
cannot be expressed as a product of two other polynomials with integral coefficients.
Remark: What can be said if the polynomial were
Remark: It is too premature right now for math olympiad students, but polynomial factorization/decomposition has applications in a practical field called control systems.