I have a solution with discarding only k elements, the test seems to work.
Also i have a small proof that discarding k elements is sufficient:
Suppose there are m desired words out of n, so the ratio is m/n. If we discard x distinct words, the ratio will be at least (m-1)/(n-x). We need to find x such that (m-1)/(n-x) >= m/n =>
(m-1)n >= m(n-x) =>
mn - n >= mn - mx =>
mx >= n =>
x >= n/m.
From the problem description, m = ceil(n/k). =>
x >= n/(ceil(n/k))
ceil(n/k) >= n/k =>
n/ceil(n/k) <= n/(n/k) = k,
so it is sufficient to choose x >= k.