## C2.

There are 2016 costumers who entered a shop on a particular day. Every customer entered the shop exactly once. (i.e. the customer entered the shop, stayed there for some time and then left the shop without returning back.)

Find the maximal $k$ such that the following holds:

There are $k$ customers such that either all of them were in the shop at a specific time instance or no two of them were both in the shop at any time instance.


Solution. We show that the maximal $k$ is 45 .

First we show that no larger $k$ can be achieved: We break the day at 45 disjoint time intervals and assume that at each time interval there were exactly 45 costumers who stayed in the shop only during that time interval (except in the last interval in which there were only 36 customers). We observe that there are no 46 people with the required property.

Now we show that $k=45$ can be achieved: Suppose that customers $C_{1}, C_{2}, \ldots, C_{2016}$ visited the shop in this order. (If two or more customers entered the shop at exactly the same time then we break ties arbitrarily.)

We define groups $A_{1}, A_{2}, \ldots$ of customers as follows: Starting with $C_{1}$ and proceeding in order, we place customer $C_{j}$ into the group $A_{i}$ where $i$ is the smallest index such that $A_{i}$ contains no customer $C_{j^{\prime}}$ with $j^{\prime}<j$ and such that $C_{j^{\prime}}$ was inside the shop once $C_{j}$ entered it.

Clearly no two customers who are in the same group were inside the shop at the exact same time. So we may assume that every $A_{i}$ has at most 45 customers. Since $44 \cdot 45<2016$, by the pigeonhole principle there must be at least 45 (non-empty) groups.

Let $C_{j}$ be a person in group $A_{45}$ and suppose that $C_{j}$ entered the shop at time $t_{j}$. Since we placed $C_{j}$ in group $A_{45}$ this means that for each $i<45$, there is a $j_{i}<j$ such that $C_{j_{i}} \in A_{i}$ and $C_{j_{i}}$ is still inside the shop at time $t_{j}$.

Thus we have found a specific time instance, namely $t_{j}$, during which at least 45 customers were all inside the shop.

Note: Instead of asking for the maximal $k$, an easier version is the following:

Show that there are 45 customers such that either all of them were in the shop at a specific time instance or no two of them were both in the shop at any time instance.

