Waste less time on Facebook — follow Brilliant.

Can anybody explain to me the double counting method?

I was not able to understand it clearly in the brilliant blog, I want an explanation related to a real life situation. Can anybody explain it to me? Plzzzzzzzzzz

Note by Siddharth Kumar
4 years, 9 months ago

No vote yet
4 votes


Sort by:

Top Newest

Source: [IMO 1989/3]

Let \(n\) and \(k\) be positive integers, and let \(S\) be a set of \(n\) points such that :

a) No three points of \(S\) are collinear,

b) For every point \(P\) of \(S\), there are at least \(k\) points of \(S\) that are equidistant from \(P\).

Prove that \( k < \frac {1}{2} + \sqrt{2n} \).

Calvin Lin Staff - 4 years, 9 months ago

Log in to reply

Well..frankly Calvin..how on earth do you know soo many stuffs?

Soham Chanda - 4 years, 9 months ago

Log in to reply

Double Counting is a very subtle and yet useful method. I personally didn't understand how far its power reached until they made me face a difficult problem (I was told it was an IMO 3, but I have not confirmed it).

Let \(k,n\) be natural numbers, and \(S\) a set of \(n\) points such that:

a) No three points are collinear.

b) For every point \(P\), there are at least \(k\) points \( Q_1, Q_2, ..., Q_k\) such that the distance \(PQ_1 = PQ_2 = ... = PQ_k\).

Prove that \( k < \frac 12 + \sqrt{2n-1} \)*

(*) I don't remember very well whether it was \(2n-2\) or \(2n-1\) or something like that.

This problem seems extremely difficult at first sight, and might seem rather Geometric than Combinatoric. However, the problem can be solved through double counting, but what can you double count?

Esteban Gomezllata - 4 years, 9 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...