Over a period of $k$ consecutive days, a total of $2014$ babies were born in a certain city, with at least one baby being born each day. Show that: (a) If $1014 < k \le 2014$, there must be a period of consecutive days during which exactly $100$ babies were born. (b) By contrast, if $k = 1014$, such a period might not exist.
Problem
Source: Irmo 2014 p2 q10
Tags: combinatorics
Kaskade
16.09.2018 12:45
Let $x_i$ refer to the cumulative number of babies born in the first $i$ days. So we would have $k+1$ distinct $x_i$, with $x_0=0,\ x_k=2014$ etc. We want to show that if $k\ge1015$ then there must be two $x_i,\ x_j$ which differ by exactly $100$. We will use the pigeon hole principle. Consider the following sets:
$\left\{0,\ 100,\ 200,\ ...\ ,\ 2000\right\}$
$\left\{1,\ 101,\ 201,\ ...\ ,\ 2001\right\}$
so just the numbers from $0$ to $2014$ mod $100$. The first $15$ of these sets will have $21$ elements and the remaining $85$ will have $20$. Suppose that there are not two $x_i,\ x_j$ which differ by exactly $100$. Then there can be at most $11$ $x_i$ in the first $15$ sets and $10$ $x_i$ in the remaining $85$ sets. So we get $k+1\le\left(11\cdot15\right)+\left(10\cdot85\right)$ and thus $k\le1014$.
For a counter example when $k=1014$, just have $1$ child be born on day $i$ if $i$ is not a multiple of $100$ and have $101$ children be born on day $i$ if $i$ is a multiple of $100$, so we would get the set of $x_i$ being $\left\{0,\ 1,\ 2,\ 3,\ ...\ 99,\ 200,\ 201,\ 202,\ ...\ 299,\ 400,\ ...,\ 2000,\ 2001,\ ...\ 2014\right\}$