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? 
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}$

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? 
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. 
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 2pi*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. 
September 29th, 2015, 06:31 AM  #6 
Global Moderator 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 NPOhard.

September 29th, 2015, 06:42 AM  #7  
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41  Quote:
Someone told me that in another forum. I`m trying new approach but I do not know yet where it will lead me.  
September 29th, 2015, 07:07 AM  #8 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  
September 29th, 2015, 07:22 AM  #9  
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41  Quote:
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.  
September 29th, 2015, 07:43 AM  #10 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  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?


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 piecewise integral?  LastXdeth  Calculus  6  February 13th, 2012 07:41 PM 