In a standard deck of cards, there are $n=13$ numbers, each of which appears $k=4$ times. Suppose the cards are distributed to $2k=8$ piles that are laid in an array of $k$ rows, 2 piles in each row. In each pile, there is at most one card of each number. Can you always select $k$ piles, one pile from each row, such that at least one card of each number remains on the table?
In this case the answer is yes: the number of possible selections is $2^k=16$. The number of possible selections that do not leave some number on the table is at most $n=13$ (since each such selection must take exactly the $k$ piles that contain some number). Hence, by the pigeonhole principle, there is at least one selection that leaves all numbers on the table. In general, whenever $$2^k>n$$ there exists a selection that leaves at least one card of each number on the table.
MY QUESTION IS: in what conditions on $n$ and $k$, does there exist a selection that leaves at least two cards of each number on the table?
NOTE: I feel it is somehow related to the probabilistic method, but could not find the correct argument.
Let $k > 2$. If I want to remove at least $k - 1$ cards with the same number, I will have to select $k - 1$ rows among the $k$ rows we have, and then I will be able to select the pile I want in the last row. For one card number, I can then have at most $2k$ selections. I then have at most $2nk$ selections such that there is less than 2 cards for a particular card number. The condition you want is then: $$ 2^{k-1} > nk. $$