×

# 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
5 years ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

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}$$.

Staff - 5 years ago

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

- 5 years ago

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?

- 5 years ago