Q10 Matemática  (Balkan MO Shortlist 2016)

Há clientes de $2016$ que entraram em uma loja em um determinado dia. Cada cliente entrou na loja exatamente uma vez. (ou seja, o cliente entrou na loja, permaneceu lá por algum tempo e depois saiu da loja sem retornar.) Encontre o valor máximo de $k$ tal que o seguinte seja válido: Existem $k$ clientes tais que todos eles estavam na loja loja em uma instância de tempo específica ou dois deles não estavam na loja em qualquer instância de tempo.