[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include(/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php) [function.include]: failed to open stream: No such file or directory
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include() [function.include]: Failed opening '/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php' for inclusion (include_path='.:/opt/php53/lib/php')
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include(/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php) [function.include]: failed to open stream: No such file or directory
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include() [function.include]: Failed opening '/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php' for inclusion (include_path='.:/opt/php53/lib/php')
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include(/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php) [function.include]: failed to open stream: No such file or directory
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include() [function.include]: Failed opening '/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php' for inclusion (include_path='.:/opt/php53/lib/php')
[phpBB Debug] PHP Warning: in file [ROOT]/includes/session.php on line 1042: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4786: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4788: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4789: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4790: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
BdMO Online Forum • View topic - Don't Intersect Please :D

Don't Intersect Please :D

For students of class 6-8 (age 12 to 14)
Facebook Twitter

Don't Intersect Please :D

Post Number:#1  Unread postby Thamim Zahin » Tue Feb 28, 2017 7:19 pm

Given $2n$ points in the plane with no three collinear, show that it is possible to pair them up in such a way that the $n$ line segments joining paired points do not intersect.
I think we judge talent wrong. What do we see as talent? I think I have made the same mistake myself. We judge talent by the trophies on their showcases, the flamboyance the supremacy. We don't see things like determination, courage, discipline, temperament.
User avatar
Thamim Zahin
 
Posts: 98
Joined: Wed Aug 03, 2016 5:42 pm

Re: Don't Intersect Please :D

Post Number:#2  Unread postby ahmedittihad » Sun Mar 05, 2017 4:43 pm

Take the convex hull and select two consecutive points and pair them up. Then take the next convex hull and do the algorithm. We eventually will get what we desire.
Frankly, my dear, I don't give a damn.
User avatar
ahmedittihad
 
Posts: 143
Joined: Mon Mar 28, 2016 6:21 pm

Re: Don't Intersect Please :D

Post Number:#3  Unread postby Thamim Zahin » Sun Mar 05, 2017 6:42 pm

Simple polygon will also do the trick. Isn't? If we put a super big rubber-band, it will result us a simple polygon.
I think we judge talent wrong. What do we see as talent? I think I have made the same mistake myself. We judge talent by the trophies on their showcases, the flamboyance the supremacy. We don't see things like determination, courage, discipline, temperament.
User avatar
Thamim Zahin
 
Posts: 98
Joined: Wed Aug 03, 2016 5:42 pm

Re: Don't Intersect Please :D

Post Number:#4  Unread postby Absur Khan Siam » Sun Mar 05, 2017 10:41 pm

Actually,@thamimzahin,the idea which you have is the main concept of convex hull.
http://mathworld.wolfram.com/ConvexHull.html
Last edited by Absur Khan Siam on Mon Mar 06, 2017 4:46 pm, edited 1 time in total.
Absur Khan Siam
 
Posts: 53
Joined: Tue Dec 08, 2015 4:25 pm
Location: Bashaboo , Dhaka

Re: Don't Intersect Please :D

Post Number:#5  Unread postby ahmedittihad » Sun Mar 05, 2017 11:41 pm

@thamimzahin I seem to remember to have taught you the concept of a convex hull. Did you forget already? :lol:
Frankly, my dear, I don't give a damn.
User avatar
ahmedittihad
 
Posts: 143
Joined: Mon Mar 28, 2016 6:21 pm

Re: Don't Intersect Please :D

Post Number:#6  Unread postby Absur Khan Siam » Mon Mar 06, 2017 12:03 pm

I think 70% or more are introduced to convex hull by this 'rubber-band' concept.:D
Absur Khan Siam
 
Posts: 53
Joined: Tue Dec 08, 2015 4:25 pm
Location: Bashaboo , Dhaka

Re: Don't Intersect Please :D

Post Number:#7  Unread postby ahmedittihad » Mon Mar 06, 2017 4:11 pm

Related Problem,
Given $2n$ points in a plane with no three collinear, with $n$ red points and $n$ blue points, prove that
there exists a pairing of the red and blue points such that the $n$ segments joining each pair are pairwise
non-intersecting.
Frankly, my dear, I don't give a damn.
User avatar
ahmedittihad
 
Posts: 143
Joined: Mon Mar 28, 2016 6:21 pm

Re: Don't Intersect Please :D

Post Number:#8  Unread postby Thanic Nur Samin » Mon Mar 06, 2017 6:13 pm

Thamim Zahin wrote:Given $2n$ points in the plane with no three collinear, show that it is possible to pair them up in such a way that the $n$ line segments joining paired points do not intersect.


Here is my take.

Take all possible pairings of the points, and select the one with minimum sum of the length of the segments. Due to the triangle inequality, the segments do not intersect.

The argument works in Ittihad's problem as well.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.
User avatar
Thanic Nur Samin
 
Posts: 176
Joined: Sun Dec 01, 2013 11:02 am


Share with your friends: Facebook Twitter

Return to Junior Level

Who is online

Users browsing this forum: No registered users and 4 guests