Waste less time on Facebook — follow Brilliant.
×

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 ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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. Calvin Lin Staff · 2 years ago

Log in to reply

@Calvin Lin 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. Vishnu C · 2 years ago

Log in to reply

Hey use box principle and draw a hexagon and you are done with your solution Biswajit Barik · 3 months, 3 weeks ago

Log in to reply

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. ~~~ Samuraiwarm Tsunayoshi · 2 years ago

Log in to reply

@Samuraiwarm Tsunayoshi 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. Vishnu C · 2 years ago

Log in to reply

@Vishnu C 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. Calvin Lin Staff · 2 years ago

Log in to reply

@Calvin Lin Like? I really can't think of a more distributed set of points. Is there such a distribution? Vishnu C · 2 years ago

Log in to reply

@Vishnu C 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). Vishnu C · 2 years ago

Log in to reply

@Vishnu C 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. Calvin Lin Staff · 2 years ago

Log in to reply

@Calvin Lin 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. Vishnu C · 2 years ago

Log in to reply

@Vishnu C 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. Calvin Lin Staff · 2 years ago

Log in to reply

Comment deleted May 15, 2015

Log in to reply

Comment deleted May 15, 2015

Log in to reply

@Vishnu C 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. Vishnu C · 2 years ago

Log in to reply

@Vishnu C Ahh!Now I see it.At least I could say I had the right idea ... what a silly mistake! Arian Tashakkor · 2 years ago

Log in to reply

@Arian Tashakkor 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. Vishnu C · 2 years ago

Log in to reply

@Vishnu C Your guess is true.I just made something up in my mind. Arian Tashakkor · 2 years ago

Log in to reply

@Vishnu C 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. Arian Tashakkor · 2 years ago

Log in to reply

@Vishnu C You're right.I'll rethink my solution.Thanks Arian Tashakkor · 2 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...