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

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?

## Comments

Sort by:

TopNewestSource: [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} \).

Log in to reply

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

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?

Log in to reply