Counting Insights Vol 1.2 Applications of Pigeon-Hole Principle

Guarantees in a Decimal Expansion

A rational number with decimal expansion of the form
$$0.d_1d_2\cdots d_nd_id_{i+1}\cdots d_nd_id_{i+1}\cdots d_n\cdots$$
has a non-empty list of digits ($d_id_{i+1}\cdots d_n$) repeating, hence is denoted by
$$0.d_1d_2\cdots d_{i-1}\overline{d_id_{i+1}\cdots d_n}$$
For example,
$\frac{102}{25} = 4.08000\cdots00\cdots = 4.08\bar{0}$
$\frac{2}{11}=0.181818\cdots1818\cdots = 0.\overline{18}$

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. $r$ is rational $\iff$ $r$ has repeating decimal expansion.
Proof: $\underline{Forward}$
Let $r \in \mathbb{Q} \implies r = \frac{m}{n}$ for some $m,n\in \mathbb{Z}$ and $n\neq 0$. Without loss of generality, we can assume $n>0$.
By division algorithm, for every integers $m,n$ with $n>0, \exists$ unique integers $q$ and $r$ such that $m=q\times n+r$, where $r<n$.
If $r=0$, we have repeating zeros in decimal expansions.
If $r\neq 0$, then there are only $n-1$ possible non-zero values that $r$ can have. Considering the next $n$ steps in the long division as set $A$ and $n-1$ possible non-zero values of $r$ as set $B$, we see that by contrapositive of Theorem 1, $\left|A\right|>1\times \left|B\right|$.
$\implies$ any map $f: A\to B$ can’t be $1$-$1$. Hence at least one non-zero value of $r$ repeats itself in the next $n$ steps of long division.
$\implies r=\frac{m}{n}$ has repeating decimal expansion.
$\underline{Backward}$
Let $r$ denote the fractional part $\in (0,1)$ of a real number having repeating decimal expansion.
If the repeating list of digits has length $k$ and begins $j$ digits to the right of decimal, then
$10^{j+k}\times r=\overline{d_id_{i+1}\cdots d_n}$
$\implies 10^{j+k}\times r\ - 10^k\times r=d_1d_2\cdots d_{i-1}.000\cdots00\cdots$
Clearly RHS is an integer and ($10^{j+k}\ - 10^k$) is also an integer
$\implies r\in \mathbb{Q}$. Since the fractional part is rational, entire real number (integral part + fractional part) will be rational too. $\space\blacksquare$
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 $m\in \mathbb{N}$. Given $m$ integers $a_1, a_2, \ldots, a_m$, there exist $k,l\in \mathbb{N}$ with $0\le k<l\le m$ such that $$a_{k+1}+a_{k+2}+\cdots+a_l$$ is divisible by $m$.
Proof: Consider the $m$ partial sums
$S_1=a_1$
$S_2=a_+a_2$
$\cdots$
$S_m=a_1+a_2+\cdots +a_m$
There are two cases: Either some of these partial sums is divisible by $m$ or none of these partial sums is divisible by $m$.
If $j^{th}$ partial sum $S_j$ is divisible by $m$, then $k=0$ and $l=j$ and conclusion of the proof follows.
Assuming the other possiblity, suppose none of these partial sums is divisible by $m$. Then, each partial sum $S_j$ leaves non-zero remainder, when divided by m. By division algorithm, there can be only $m-1$ non-zero remainders possible.
Consider set of $m$ partial sums as set $A$ and set of $m-1$ possible remainders as set $B$. Then we have, $\left|A\right|>1\times \left|B\right|$. So by contrapositive of Theorem 1, at least two distinct partial sums have the same non-zero remainder.
$\implies \exists\ S_i, S_j$ such that $S_i=q_i\times m$ and $S_j=q_j\times m$.
$\implies S_i - S_j=(q_i-q_j)\times m$
$\implies a_{i+1}+a_{i+2}+\cdots+a_j=k\times m$, where $k=q_i-q_j$
$\implies \exists\ k=i, l=j$ with $k<l$ such that $m|(a_{k+1}+a_{k+2}+\cdots+a_l)$. $\space\blacksquare$

---

Guarantees in a Scheduling Decision

Case Study 4. The local hockey-league wants to schedule at least one game every day, during the $11$-week summer season. To keep the fields in good condition, it is decided to schedule no more than (at most) $12$ 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 $21$ games are scheduled.
Analysis: Notice that there will be at least $7$ games per week. This suggests a surjection from set of games $A$ onto set of weeks $B$. Further, cardinality of pre-image of each element of $B$ is at most 12. And $\left|B\right|=11$. So, by contrapositive of Theorem 1, we have
$\left|A\right|\le 12\times \left|B\right|$
Maximum number of games possible $=12\times 11=132$.
Minimum number of games possible $=7\times 11=77$.
But the above analysis is in terms of weeks; we are required to show that $\exists\ k>1$ consecutive days such that sum of games scheduled on these days $=21$.
So, we define cumulative partial sums $S_i$ denoting total number of games scheduled from day $1$ to day $i$.
$S_1=$ number of games scheduled on day $1$.
$S_2=$ sum of games scheduled upto day $2$
$\cdots$
$S_{77}$ = sum of games scheduled upto (last) day $77$
such that $77\le S_{77}\le132$.
Now, we intend to find $i,j$ with $j<i$ such that on some duration ($i-j$), we have $S_i - S_j=21$.
Since, there is at least $1$ game scheduled per day, the sequence $<S_n>$ is strictly increasing (all terms distinct), i.e.,
$1\le S_1<S_2<\cdots<S_{77}\le132$.
On adding $21$ on both sides of the inequality, we get
$S_1+21<S_2+21<\cdots<S_{77}+21\le153$.
Thus, we have $2\times77=154$ 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 $154$ terms have same value.
However, first $77$ terms are distinct and last $77$ terms are also distinct. So, same value is possible only when by choosing $1$ term from first group and another $1$ from second group.
$\implies S_i=S_j+21\implies S_i - S_j=21$
$\implies$ Days $j+1, j+2,\ldots,i$ is the duration during which 21 games are scheduled. $\space\blacksquare$

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

Written with StackEdit.