SERVING THE QUANTITATIVE FINANCE COMMUNITY

vN
Topic Author
Posts: 53
Joined: May 12th, 2004, 5:05 am

### circle covering

I got this from a Chinese guy:Prove that one cannot cover a circle with a radius of 5 meters using 9 arbitrary-length stripes of width 1 meter.He claims that the proof requires no more than high school math and the proof goes as few as 5 lines.

gregoryv
Posts: 54
Joined: July 14th, 2002, 3:00 am

### circle covering

I think that it has to do with the fact that the widths of the strips don't add up to 10. Meaning that you cannot cover the diameter of the circle. So then one can argue that you can place a strip on a diagonal, but then you just rotate what you consider the diameter and the strip will only be covering 1 meter of it again.

vitieubaoldk
Posts: 36
Joined: November 8th, 2004, 6:54 pm

### circle covering

Sorry but Greg you got it wrong I've thought of 2 ways: 1) Calculate the area of the intersection of a stripe and the circle, multiply it by 9 and compare the result with the circle's area (Pi*25) 2) A,B,C,D on the circle, AB//CD, d(AB,CD)=1 meter, if (<AOC + <BOD)x9 < 360° then the 9 stripes cannot cover the circle. (2) works and (1) doesn't (I checked very fast on a small calculator so not 100% sure)

alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

### circle covering

vitieubaoldk,your argument is no good either;in the best case scenario, you have,AOC + <BOD = 9*2*ArcCos(4/5) wich is greater than 2 Pi. (or 360, if you prefer.)

mattcushman
Posts: 100
Joined: July 14th, 2002, 3:00 am

### circle covering

It's more than 5 lines but it works (and I think it rather pretty). Nice problem!If we can find a non-negative function f(x,y) such that the integral of f(x,y) over any strip intersected with the circle is equal to A, while f(x,y) integrated over the whole circle is B with B > 9A, we are done.How can we find such a function f? Note that if the function is such that the line integral of f(x,y) over any chord of the circle is the same (call this number A), then this function will have the property above (with A being the integral as well). This is because the integral over a strip intersected with the circle can be broken up (using essentially Fubini) into an integral along the radial direction and integrals along the chords. Since the strips are of width 1, this ends up being the integral from 0 to 1 of A, i.e. just A. (minor note: I assume here that the strip is such that along the radial direction you do get at least one whole unit in this integral; if not, it doesn't really affect the argument, as in that case the integral is less tjhan A, so 9 of them are still less than B).I find it easier to rescale everything here so that the circle has radius 1, and the strips have width 1/5.What specific function should we use. Try f(x,y) = 1/sqrt(1-x^2-y^2). This function is circularly symmetric, so we only need to evaluate its integral along a chord where we fix on the variables, say x. Note:This last term is a standard trig sub integral (u=sin), and evaluates to pi/2. This is half of a chord, so the whole chord is pi. Thus, A is pi/5 (remember the rescaling above).What is the integral over the whole circle? Put it in polar coordinates and you get 2pi * (integral 0 to 1 of 1/sqrt(1-r^2)). Put in polar coords and simplify, you get 2*pi*(integral of sin(theta) from 0 to pi/2). This is 2pi, which is our B.

chiron
Posts: 53
Joined: January 11th, 2004, 4:29 pm

### circle covering

i think simplistic solution (high school math, no more then 5 lines) to this is the following:the most optimal way of covering circle by strips (which in total width are <D) is to arrange them in 18-gonthen the width of each strip required is: 2R*sin(pi/9)>1same can be proved for other possible arrangements (square and hexagon)

mattcushman
Posts: 100
Joined: July 14th, 2002, 3:00 am

### circle covering

chiron,I don't see a proof there. Anyway, the most efficient way to cover the circle be to use strips side by side, and not arranged in any sort of polygon. That's the only way you can do it with 10 strips, as a simple extension of the proof below actually shows. There can be no overlap in the strips.

chiron
Posts: 53
Joined: January 11th, 2004, 4:29 pm

### circle covering

hi mattcushman1) poligon is optimal if total width, i.e. sum of widths of individual strips is less then diameter (i have mentioned this in previous message).2) if strips can't overlap then there problem doesnt make sense, we don't need any math to realise that 9m can't cover 10m.

mattcushman
Posts: 100
Joined: July 14th, 2002, 3:00 am

### circle covering

They can overlap in principle, but not in practice. I still don't follow your alleged proof.OK, let me ask you this then... applying your math with 10 strips, it seems that you can actually prove that 10 strips doesn't work either, as 2R*sin(pi/10)>1 as well. So, do you agree that you cannot do it with 10 strips?

vitieubaoldk
Posts: 36
Joined: November 8th, 2004, 6:54 pm

### circle covering

You're right AlexC, my argument doesn't work either , I'm trying to figure something else out.

chiron
Posts: 53
Joined: January 11th, 2004, 4:29 pm

### circle covering

hi mattcushman,i said twice that poligon is optimal IF TOTAL WIDTH IS LESS THEN DIAMETER. since total width of 10 strips is 10 = D, we align them one next to other.in other words by arranging in (overlapping) poligon we try to capitalise on length of strips (that is not limited).

mattcushman
Posts: 100
Joined: July 14th, 2002, 3:00 am

### circle covering

Chiron,Optimal in what sense? Why is this true, but only when the total width is less than the diameter? These statements are not obvious. I don't see how you have supplied a proof of anything.I'm doubtful that there is a shorter proof than mine, but would love to see one.

Fennek
Posts: 5
Joined: December 16th, 2004, 11:37 am

### circle covering

nice proof mattcushman,this more generally shows that a circle can only be covered by a number of stripes with arbitraty width if the total width of all stripes is at least equal to the diameter of the circle.Also, there is no solution with overlaps if the parallel solution does not work.

prospero
Posts: 47
Joined: March 16th, 2002, 4:00 am

### circle covering

1) suppose that such a covering exists, and pick a strip that covers the centre of the circle2) fix the line perpendicular to the strip, running thru the centre of the circle, andpick the eight points on the line at the distance n, n=1,2,3,4 from the centre of the circle(two points for each n)3) for a strip covering one of these points, the maximal length of the circle arc coveredis achieved when the strip is perpendicular to the line constructed in (2) and furthestaway from the centre (high school at most)4) the eight thus palced strips together and the strip picked in (1) are pairwise nonoverlaping, so, by the optimalityof the construction in (3), no other covering can cover longer piece of circumference5) On the other hand, this covering does not cover the entire circumference, so no other covering does.

Aaron
Posts: 6433
Joined: July 23rd, 2001, 3:46 pm

### circle covering

I agree with your argument as far as it goes. But why must eight separate strips cover your eight points? What if some strips cover more han one point? For example, I could cover all eight points with one strip through the center of the circle.But I think there is a simpler, variant. A strip cannot cover more than cos(0.8) = 0.6967 of arc. At least one strip must cover the center, that can cover no more than 4*sin(0.1) = 0.3993 of arc. 8*0.6967 + 0.3993 = 5.9730, which is less than 2*pi. So you cannot cover the center plus the circumference.
Last edited by Aaron on April 24th, 2005, 10:00 pm, edited 1 time in total.
 ABOUT WILMOTT

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...

 JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...

GZIP: On