# Proofs: Combinatorial!

Andrei marked $$4n$$ points on the plane. He then connected with segments every pair of points which were $$1$$ cm apart. He found that amid every $$n+1$$ points there were at least two points connected by segments. Prove that Andrei drew at least $$7n$$ segments.

Note by Andrei Golovanov
3 years, 4 months 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:

What exactly does this statement mean:

"He found that amid every $$n+1$$ points there were exactly two points connected by segments"

- 3 years, 4 months ago

I think the word exactly should be replaced by atleast.

- 3 years, 4 months ago

Yes, that is correct. It should say "at least". Thanks for pointing it out. @Raghav Vaidyanathan @Sudeep Salgia

- 3 years, 4 months ago

Comment deleted

Comment deleted

Comment deleted

Comment deleted May 31, 2015

But you just said that it is not possible with n=1.

- 3 years, 3 months ago

The point is that with $$n=1$$, the conditions of the question cannot hold, and hence any given conclusion is true.

It's like "If $$a, b$$ are 2 positive reals such that $$a^2 + b^2 = 0$$, then $$a+b = 0$$" is a true statement. Because under all cases where the condition holds (which is no case), the result is true. Note that even though $$a+b = 0$$ can never be a true statement under the restricted condition that (a,b) are 2 positive reals. However, by adding additional conditions, we can make it a statement about nothing, which is trivially true.

Staff - 3 years, 3 months ago

That is, more or less, what the question asks. If this condition holds, he must have drawn $$7n$$ segments. Prove why.

- 3 years, 3 months ago

So you're basically saying that the condition will hold when pigs fly.

- 3 years, 3 months ago

That's an amusing way to think. But wait! Swine flu! So pigs flew! So the condition is true! :)

- 3 years, 3 months ago