My Math Forum  

Go Back   My Math Forum > High School Math Forum > Geometry

Geometry Geometry Math Forum


Thanks Tree1Thanks
Reply
 
LinkBack Thread Tools Display Modes
September 28th, 2015, 01:03 PM   #1
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Puzzle : piece of string and circle

Hi,

Let us draw a circle.
Let us compute the circumference of that circle : c=100. c is the circumference.
Now let us take a piece of string with a length equal to 100.
Let us cut it in 12 pieces of different lengths.
What we and I know is that the shortest piece measures : 5 and the longest 10.
I remove 1 out of 12 pieces and I give the 11 remaining pieces.
You are not supposed to know which piece I removed and the circumference c.
Can you find the radius of the drawn circle?
I do not want exactly the length but only the range : between x and x+y

Easy?
mobel is offline  
 
September 28th, 2015, 04:56 PM   #2
Global Moderator
 
Joined: May 2007

Posts: 6,707
Thanks: 674

L = sum of the pieces you have. L+5<c<L+10, r is radius and $\displaystyle \frac{L+5}{2\pi}\le r \le \frac{L+10}{2\pi}$
mathman is offline  
September 29th, 2015, 04:24 AM   #3
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Right! The puzzle is very easy to solve.
Can you imagine that this puzzle has a link with the the TSP problem which is NP complete?
mobel is offline  
September 29th, 2015, 04:31 AM   #4
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

What is fantastic in mathematics is that there are invisible bridges between the fields.
That is why attacking any problem alone is not the good approach.
Only teams could solve all the hard unsolved problems.
I will tell you what links this simple puzzle to the TSP problem.

Distances between cities are arcs (pieces of string)
Our circle circumference is equal to the length of the shortest path.
mobel is offline  
September 29th, 2015, 06:17 AM   #5
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

I`m going to illustrate by an example the link between my simple puzzle and the traveler salesman problem.

Let us start from a network of 5 cities A,B,C,D,E.
What we know are the distances between the cities :
AB,AC,AD,AE,BC,BD,BE,CD,CE,DE.
So 10 lines of different lengths each one corresponding to some arc.
Why arc?
As the shortest path is hamiltonian it will correspond to some circle with radius r and a circumference 2-pi*r where 2*pi*r is exactly equal to the shortest path.
We still do not know the value of r.
Now if we do not take into account the network configuration we could build a lower bound and an upper bound for radiuses.
If we sum the 5 lowest values of AB,AC,AD,.....DE (our 10 distances or arcs or pieces of string) we ill have have the lower radius.
We do the same computation for the 5 longest distances of the known ten we will obtain the longest radius.
We are now sure that our circle corresponding to the shortest path is bounded between the 2 values.
My question is : can we give more precise bounds knowing all what we know until now?
If we have to choose only 5 arcs to build our circle then we know that the average angle is = 360/5= 75 degrees.
I let you think a little bit then I will continue my illustration.

Thank you.
mobel is offline  
September 29th, 2015, 06:31 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
It sounds like you're talking about the Euclidean TSP, not the TSP. Euclidean TSP has a pretty good PTAS, but normal TSP is NPO-hard.
Thanks from mobel
CRGreathouse is offline  
September 29th, 2015, 06:42 AM   #7
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
Originally Posted by CRGreathouse View Post
It sounds like you're talking about the Euclidean TSP, not the TSP. Euclidean TSP has a pretty good PTAS, but normal TSP is NPO-hard.
I know but I`m looking for better solution.
Someone told me that in another forum.
I`m trying new approach but I do not know yet where it will lead me.
mobel is offline  
September 29th, 2015, 07:07 AM   #8
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by mobel View Post
I know but I`m looking for better solution.
Are you familiar with the Arora and Mitchell approximation algorithms?
CRGreathouse is offline  
September 29th, 2015, 07:22 AM   #9
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
Originally Posted by CRGreathouse View Post
Are you familiar with the Arora and Mitchell approximation algorithms?
Do you have question about what I`m talking about?
Let us focus on my approach now unless we are going to waste time.
There are 100s of algorithms known and unknown.
So please do not disturb my approach.
So I quit now because you make me angry.

You can lock this thread.

Mister Greathose you still have big big big problem.
You never take time to think what people are saying.
You act like robot by vomiting the googlized references without link whatsoever with the thread.
mobel is offline  
September 29th, 2015, 07:43 AM   #10
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by mobel View Post
Do you have question about what I`m talking about?
Yes, I do. I mentioned that there is a PTAS for Euclidean TSP and you said that you were looking for a "better solution". So I asked if you knew about the existing solutions -- otherwise, how could you know if something would be better?
CRGreathouse is offline  
Reply

  My Math Forum > High School Math Forum > Geometry

Tags
circle, piece, puzzle, string



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Piece wise limits Saralove996 Calculus 1 September 17th, 2014 04:26 PM
A piece of pi shunya Algebra 3 November 19th, 2013 09:03 PM
Determining continuity of a piece wise function frankpupu Real Analysis 0 February 14th, 2012 01:27 PM
How do I solve this piece-wise integral? LastXdeth Calculus 6 February 13th, 2012 07:41 PM





Copyright © 2019 My Math Forum. All rights reserved.