Polygonous Party Games
You and other party-goers are lead to different places in a wood blind-folded. You’re instructed to remove your blindfold at the sound of a horn and read a letter you’ve been provided. When the bell sounds, you remove the blindfold and the letter reads thus:
You’ll notice around you that there are lengths of rope tied between hundreds of trees around you. You may notice that any tree with any rope tied to it has exactly two ends tied to it, each stretching to a different tree. In fact, these hundreds of treees form a giant concave polygon. Some of you are inside that polyon and others are outside. To win the game, you must be the first to reach the clubhouse at the top of the hill (which is outside of the polygon!) and report correctly whether you were initially inside the polygon or outside of it. You can pass under the ropes, but please don’t change them in any way. Good luck!
What strategy might you employ to determine your status and require as little time as possible to get back to the clubhouse?
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
Blaise Pascal said,
March 23, 2010 at 12:26 am
This one’s easy, assuming you know where the top of the hill is in relation to where you start.
Jonathan Harford said,
March 23, 2010 at 10:04 am
Assuming I could see the clubhouse, I’d head straight for it, counting the number of times I pass under (or over) a rope. If the count ends at an odd number, I was inside the shape. Otherwise, outside.
Krister Jonsson said,
March 23, 2010 at 11:41 am
I think I remember how to do this.
[spoiler]Go in a straight line as fast as possible towards the clubhouse, and keep count of how many ropes you pass. If you pass an even number of ropes you started outside of the polygon, and if you pass an odd number you started inside. [/spoiler]
Blaine said,
March 23, 2010 at 11:41 am
I think this would work: [spoiler]Just run straight to the clubhouse, as quickly as possible. Count the number of times you cross under a rope. Each rope crossing will toggle you from inside to outside or vice versa. If you count an odd number of crossings, you were inside. If you count an even number of crossings, you were outside.[/spoiler]
jyoak said,
March 23, 2010 at 12:26 pm
I remembered this one from when I was in college competing in the ACM programming competition. The idea was that your team was given a number of problems in terms of input and output required ranging from very simple to very hard and the team that could complete the most of them in a day won. The simplest was that your program would receive six arguments to be interpreted as three ordered pairs on the plane and determine whether or not they formed a triangle and output yes or no. For this one, you received an unknown number of ordered pairs and were assured that all but the last formed a polygon and you were to report whether the last was inside or outside the polygon. I happened to implement that solution for our team and did it essentially as all the comments above did. I projected a ray from that final point, ensuring that it didn’t pass through any previously provided point, and counted the number of segments it intersected.
strauss said,
March 23, 2010 at 4:12 pm
We use this trick all the time in Differential Topology class!