My Math Forum Puzzle : piece of string and circle

 Geometry Geometry Math Forum

 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,770 Thanks: 700 L = sum of the pieces you have. L+5
 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 Im 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.
 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 NPO-hard. Thanks from mobel
September 29th, 2015, 06:42 AM   #7
Banned Camp

Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
 Originally Posted by CRGreathouse 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 Im looking for better solution.
Someone told me that in another forum.
Im 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
Quote:
 Originally Posted by mobel I know but Im looking for better solution.
Are you familiar with the Arora and Mitchell approximation algorithms?

September 29th, 2015, 07:22 AM   #9
Banned Camp

Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
 Originally Posted by CRGreathouse Are you familiar with the Arora and Mitchell approximation algorithms?
Do you have question about what Im 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.

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
Quote:
 Originally Posted by mobel Do you have question about what Im 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?

 Tags circle, piece, puzzle, string

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Saralove996 Calculus 1 September 17th, 2014 04:26 PM shunya Algebra 3 November 19th, 2013 09:03 PM frankpupu Real Analysis 0 February 14th, 2012 01:27 PM LastXdeth Calculus 6 February 13th, 2012 07:41 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top