Counting Insights Vol 1.2 Applications of Pigeon-Hole Principle

Counting Insights Vol 1.2 Applications of Pigeon-Hole Principle

Guarantees in a Decimal Expansion

A rational number with decimal expansion of the form

has a non-empty list of digits () repeating, hence is denoted by

For example,

A careful study of long division method shows that digits in decimal expansion repeat because remainder repeats itself in the long division method. Therefore, exactly the same sequence of quotients and remainders are generated as before, causing the sequence of digits to repeat (in decimal expansion).
A natural question to ask is, why does the remainder repeat?

Theorem 2. is rational has repeating decimal expansion.
Proof:
Let for some and . Without loss of generality, we can assume .
By division algorithm, for every integers with unique integers and such that , where .
If , we have repeating zeros in decimal expansions.
If , then there are only possible non-zero values that can have. Considering the next steps in the long division as set and possible non-zero values of as set , we see that by contrapositive of Theorem 1, .
any map can’t be -. Hence at least one non-zero value of repeats itself in the next steps of long division.
has repeating decimal expansion.

Let denote the fractional part of a real number having repeating decimal expansion.
If the repeating list of digits has length and begins digits to the right of decimal, then


Clearly RHS is an integer and () is also an integer
. Since the fractional part is rational, entire real number (integral part + fractional part) will be rational too.
Note: Decimal expansion of irrational numbers grows indefinitely without repetition, because they are NOT ratio of two integers.


Existence of Divsior of a Sum of Integers

Theorem 3. Let . Given integers , there exist with such that is divisible by .
Proof: Consider the partial sums




There are two cases: Either some of these partial sums is divisible by or none of these partial sums is divisible by .
If partial sum is divisible by , then and and conclusion of the proof follows.
Assuming the other possiblity, suppose none of these partial sums is divisible by . Then, each partial sum leaves non-zero remainder, when divided by m. By division algorithm, there can be only non-zero remainders possible.
Consider set of partial sums as set and set of possible remainders as set . Then we have, . So by contrapositive of Theorem 1, at least two distinct partial sums have the same non-zero remainder.
such that and .

, where
with such that .


Guarantees in a Scheduling Decision

Case Study 4. The local hockey-league wants to schedule at least one game every day, during the -week summer season. To keep the fields in good condition, it is decided to schedule no more than (at most) games per week. Then, no matter how we arrange the games in the summer season, there will be a succession of days, during which exactly games are scheduled.
Analysis: Notice that there will be at least games per week. This suggests a surjection from set of games onto set of weeks . Further, cardinality of pre-image of each element of is at most 12. And . So, by contrapositive of Theorem 1, we have

Maximum number of games possible .
Minimum number of games possible .
But the above analysis is in terms of weeks; we are required to show that consecutive days such that sum of games scheduled on these days .
So, we define cumulative partial sums denoting total number of games scheduled from day to day .
number of games scheduled on day .
sum of games scheduled upto day

= sum of games scheduled upto (last) day
such that .
Now, we intend to find with such that on some duration (), we have .
Since, there is at least game scheduled per day, the sequence is strictly increasing (all terms distinct), i.e.,
.
On adding on both sides of the inequality, we get
.
Thus, we have terms, each of which is an integer between 1 and 153. By contrapositive of Theorem 1, this is possible only when at least two of the terms have same value.
However, first terms are distinct and last terms are also distinct. So, same value is possible only when by choosing term from first group and another from second group.

Days is the duration during which 21 games are scheduled.

Clearly, a total of games can be scheduled in at most (max.) days.
As an exercise, find the minimum number of days, in which games can be scheduled, i.e., a total of games can not occur in fewer than days. Find the .

Written with StackEdit.

Comments

Popular posts from this blog

Counting Insights Vol 1.0 K-to-1 Functions

Counting Insights Vol 1.1 Pigeon-Hole Principle