×

# Can you prove this one tree?

If 8 points are chosen to lie on or inside a circle of diameter 2 cm, then show that the distance between some two points will be less than 1 cm. Also, if you can, find the minimum no. of points to be chosen in this manner for this to be true.

Note by Vishnu C
2 years, 10 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:

Here's a proof that "Given any 8 points in a circle of diameter 2, then there exists two points which will be at most 1 cm apart".

Dissect the circle as follows: Use an inner circle of diameter 1, and then 6 equal regions / spokes from the center.

Claim: For any of the outer regions, if there are 2 points in there, then their distance is at most 1cm. (Prove this, there is a very simple way)

Hence, by the pigeonhole principle, if there are 8 points, then 2 of these points must lie in the same region, and thus be at most 1 cm apart.

Note: We can perform a similar argument with 7 points, with the "obvious" 6 region distribution. It could be tricky to prove that "any 2 points are at distance at most 1", and that could be why they gave the case of 8 points , which has a slightly easier argument.

I don't profess to speak for the intention of the test setters, but this is a good way to understand how rigorously one thinks.

Staff - 2 years, 10 months ago

Nice solution! It may well be that they expect rigour like you said. I was just thinking that maybe a more low scale approach would suffice because I have noticed that most of the questions in the paper are quite easy to solve as well as to overthink. But one should not make assumptions from trends like this, like I did.

- 2 years, 10 months ago

Hey use box principle and draw a hexagon and you are done with your solution

- 1 year, 1 month ago

Counterexample for 7 points:

Consider the locus of each 7 points of the counterexample such that the distance between 1 point and the other point is less than 1.

Now all loci of 6 points on the circumference covers all areas but the center of the circle.

The locus of the center of the circle covers all areas but the circumference of circle.

These loci 7 points all covers the entire circle, which means you cannot place 1 more point inside or lie on the circle. ~~~

- 2 years, 10 months ago

That's what I wrote in my comment to Arian. That's the worst case scenario and once you prove that the statement is true even for the worst case, you're done with your proof.

- 2 years, 10 months ago

You have to be careful with such a "worst case" scenario argument, as what you have done is only to show "if it follows this format, then ....". You have not really shown that you have indeed found the "worst case". There could be other scenarios that you have not yet considered.

Staff - 2 years, 10 months ago

Like? I really can't think of a more distributed set of points. Is there such a distribution?

- 2 years, 10 months ago

I know that a worst-case-scenario-contradiction proof is very risky because when you do use it, it's highly likely that you've missed a scenario or two that are even worse. But in this case and other simple cases, such proofs can come in handy (if you've got it right).

- 2 years, 10 months ago

Such proofs are often wrong / incomplete, as they presume an innate structure. It may offer you some insight into what the special conditions are, but such a "construction" proof rarely addresses the "existence" element of it. To be done properly, one must find an alternative argument.

Staff - 2 years, 10 months ago

Can we think of it in terms of charges of the same sign that have been forced to occupy the same space inside the circle? So naturally, the charges will try to get to a new position that's more distributed, so as to lower their energy. At least in theory, it should be possible. But this is also up to how good your imagination can be and how realistic your imaginations are. So I can't think of any better argument at the moment, except maybe coordinate geometry. Let me know if you've thought of one.

Note that this is a question that was asked in an entrance exam for a BSc. program in CMI, which means that 12th graders who were dragged from their vacation time or lack thereof, were the ones who were meant to answer this question. Although I cannot be sure because they haven't posted a solution for the paper in which this question was asked, I can say with some certainty that this logic would've also been appreciated to some extent.

- 2 years, 10 months ago

No, you cannot make the underlying assumption that "this system must be very nice, and that all of these points will want to be evenly distributed". Besides, how do you know what "evenly distributed" means? What is an "even distribution" for 8 points? or 6 points?

Assuming that the test is to determine the rigor of thought, then the intention of such a question (and those that are similar to it) is to filter out the candidates who have a clear rigorous mathematical argument that is properly substantiated.

Staff - 2 years, 10 months ago

Comment deleted May 15, 2015

Comment deleted May 15, 2015

It should be segment length =1 cm. So you can have a regular hexagon with unit sides inscribed in the unit circle which means 6 of the points are used up. Choose the 7 th one at the center. Now it's obvious that no matter where you place the last one, you will end up with at least one pair of points with distance less than1 cm.

- 2 years, 10 months ago

Ahh!Now I see it.At least I could say I had the right idea ... what a silly mistake!

- 2 years, 10 months ago

You had a nice approach. I don't think you drew the figure. Sometimes in geometry, drawing a proper rough figure is the best investment of time.

- 2 years, 10 months ago

- 2 years, 10 months ago

But wait if the arc length is 1 cm then the distance is definitely lower than 1 cm right?Hence I think I stand corrected.BUT using the right division might reduce the minimum number of dots needed.

- 2 years, 10 months ago

You're right.I'll rethink my solution.Thanks

- 2 years, 10 months ago