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 specic time instance or no two of them were both in the shop at any time instance.
Problem
Source: Balkan BMO Shortlist 2016 C2
Tags: combinatorics, Maximal
12.08.2019 12:08
Suppose there exist $\ell$ customers all of them were in the shop at the same time, but there do not exist $\ell+1$ ones with this property. Order the customers in a row the way they come out of the shop: $C_1,C_2,\dots, C_{2016}$ and $C_1$ is the first one that exits the store. It is not possible $C_1$ to be in the shop simultaneously with all $C_2,C_3, \dots, C_{\ell+1}$, hence some of them, say $C_{i_2}, i_2\leq \ell+1$ had entered the shop after $C_1$ has come out. We apply the same argument to $C_{i_2}$ and so on, and construct a sequence $C_1=C_{i_1}, C_{i_2},C_{i_3},\dots$ with $i_{j+1}-i_j\leq \ell$ and such that any two customers have not met each other inside the shop. Their number is at least $\left\lceil \frac{2016}{\ell} \right\rceil $. It means that any $k$ in question satisfies $$\displaystyle k\geq k_0:=\min_{1\leq \ell\leq 2016}\max \left\{\ell, \left\lceil \frac{2016}{\ell} \right\rceil \right\}$$ In fact, we can easily construct an example when the problem statement holds for $k=k_0$. Clearly $k_0$ is something around $\sqrt{2016}$, and straightforward check shows $k_0=45$.
18.03.2021 11:13
parmenides51 wrote: 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 specic time instance or no two of them were both in the shop at any time instance. Are there any graph-theoretic solutions? Something like: Find the maximum k such that there is a k-clique in a graph (of 2016 vertices or maybe n vertices for a generalization) or its complement (I don't actually know if a graph makes sense, as in, maybe some set of connections implies some other connection due to the formulation of the problem).