Question of 18.12 and 18.9 in 1.4.7

#1

Hi, I have a question of 18.12’s relationship with 18.9. in 18.9 it is asking element appear more than 1/2 times, so it is discarding 2 distinct elements. in 18.12 it is trying to figure out elements that appear more than 1/k times so using same theory it should discard k distinct items but in 18.12 it is saying discard k+1 items. is there a reason?

0 Likes
#2

Hey Pete,

Thanks for your question. Personally my gut tells me that your are right, and I have verified the solution when we discard k items at a time and the result is correct still. However, I need more time to verify that, and I will come back to you later.

0 Likes
#3

Hey Pete,

After our careful examination, we think you are right that we should discard k items at a time instead of k+1 items. A very simple proof can be easily derived from the proof of Solution 18.12. On the other hand, an interesting thing is that I found it is hard to get a counterexample of discarding k+1 items, and it might be a good exercise for people who are interested in this.

Thanks for your report, and I really appreciate that.

0 Likes
#4

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.

0 Likes