Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 29 Jan '08 14:48
    You put on the table a paper disc with diameter D. Now you put on the table strips of paper (each strip has a constant width and infinite length, but each strip may have a different width) until you cover the disc.
    Prove: The sum of the widths of the strips is at least D.
  2. 30 Jan '08 03:49
    technically, you never said that the strips could not be folded, so, because one strip has infinite length, we only need one strip of ANY width to dover the circle....
  3. 30 Jan '08 04:49
    If the strips are placed horizontally one on top of the other (2 dimensions, so upward), then there exists a diameter D in a circle that is parallel to the wide side. I'll try to draw the diagram without the circle:
    ____________________
    __________|_________
    __________|_________
    __________|_________
    __________|_________
    __________|_________

    Ok, imagine that the vertical line is the diameter, and that there is a circle (not drawn). The diameter equals the sum of the widths of the strips.
  4. Standard member TheMaster37
    Kupikupopo!
    30 Jan '08 11:32
    Originally posted by bjpcomet
    technically, you never said that the strips could not be folded, so, because one strip has infinite length, we only need one strip of ANY width to dover the circle....
    With an infinite strip you don't need to fold, just go around the world a couple of times
  5. 30 Jan '08 11:57 / 2 edits
    Originally posted by David113
    You put on the table a paper disc with diameter D. Now you put on the table strips of paper (each strip has a constant width and infinite length, but each strip may have a different width) until you cover the disc.
    Prove: The sum of the widths of the strips is at least D.
    EDIT: sorry, didn't read the question properly.

    Surely the problem is arbitrary (assuming the strips cannot be folded and we are on an infinite plane)?

    Assume the sum of the widths of the strips is less than D. Then th best way of laying the strips is by putting them side by side touching, like ||||. But as their widths are less than D they can obviously never cover the entire circle.

    Or something like that?
  6. 30 Jan '08 12:02 / 1 edit
    Originally posted by Swlabr
    If you stack them, or let them overlap you could get any sum of their widths, surely?
    Of course, but that doesn't answer the question. You can get any sum greated than or equal to D; but you didn't prove a sum smaller than D is not possible.
  7. 30 Jan '08 12:03 / 1 edit
    Originally posted by twilight2007
    If the strips are placed horizontally one on top of the other (2 dimensions, so upward), then there exists a diameter D in a circle that is parallel to the wide side. I'll try to draw the diagram without the circle:
    ____________________
    __________|_________
    __________|_________
    __________|_________
    __________|_________
    __________|_________

    Ok, ...[text shortened]... nd that there is a circle (not drawn). The diameter equals the sum of the widths of the strips.
    And how does that answer the question? You only showed that a widths sum of D is enough. But you didn't show we can't do it if that sum is smaller than D.
  8. 30 Jan '08 12:03
    Originally posted by bjpcomet
    technically, you never said that the strips could not be folded, so, because one strip has infinite length, we only need one strip of ANY width to dover the circle....
    No tricks allowed!
  9. 30 Jan '08 12:04 / 1 edit
    Originally posted by David113
    Of course, but that doesn't answer the question.
    Duly edited - I missed the "at least" bit.
  10. 30 Jan '08 12:10
    Originally posted by Swlabr
    EDIT: sorry, didn't read the question properly.

    Surely the problem is arbitrary (assuming the strips cannot be folded and we are on an infinite plane)?

    Assume the sum of the widths of the strips is less than D. Then th best way of laying the strips is by putting them side by side touching, like ||||. But as their widths are less than D they can obviously never cover the entire circle.

    Or something like that?
    This is not a proof. How do you know that if the strips are not all parallel, and the sum of their widths is less than D, then their union (the area covered by at least one strip) can't cover a disc of diameter D?

    This problem DOES have a nice proof...
  11. 30 Jan '08 12:12
    Originally posted by David113
    You put on the table a paper disc with diameter D. Now you put on the table strips of paper (each strip has a constant width and infinite length, but each strip may have a different width) until you cover the disc.
    Prove: The sum of the widths of the strips is at least D.
    Just to make it clear - the edges of a strip are parallel to each other.
  12. 30 Jan '08 12:40 / 1 edit
    Originally posted by David113
    This is not a proof. How do you know that if the strips are not all parallel, and the sum of their widths is less than D, then their union (the area covered by at least one strip) can't cover a disc of diameter D?

    This problem DOES have a nice proof...
    The best way to lay the strips in an abstract world:

    Assume two strips are not parallel, and thus they overlap.

    Notice that the maximum area that any two strips of width a and b cover is when they are laid parallel and side by side with a diameter through (a+b)/2 (the centre of the "new" strip of width a+b.

    Then the area of the circle that they cover is STRICTLY less than the maximum area of the circle that they cover (when they are not parallel).

    Thus, parallel is obviously the best way to lay the first two strips. So, create a strange almost ellipse like shape, but with pointed corners, by removing the part of the circle covered by placing the two strips of largest width in the best starting way then removing these strips and the part of the circle that they cover and amalgamating the two parts of the circle left.

    Now, applying the same logic as before we can see that the best way too lay any two strips is through the centre as before and along the "wider" part of this ellipse-esq shape.

    Apply until we have used all the strips.

    What we have done has not changed the total width of the strips, we have just sort of displaced the way in which the width has been distributed. (Two strips of width a and b now each have with (a+b)/2 if they were two strips that we laid in the same "manouver", but (a+b)/2+(a+b)/2=a+b, and thus the total width of the strips we have lain is equal to the total width of the proper strips).

    Now, the way we have lain these strips covers more area on the circle than any other method of laying the strips. However, it does not cover the circle as the total width is less than D.

    Thus, it is impossible.
  13. 31 Jan '08 01:51
    Originally posted by Swlabr
    The best way to lay the strips in an abstract world:

    Assume two strips are not parallel, and thus they overlap.

    Notice that the maximum area that any two strips of width a and b cover is when they are laid parallel and side by side with a diameter through (a+b)/2 (the centre of the "new" strip of width a+b.

    Then the area of the circle that they cove ...[text shortened]... it does not cover the circle as the total width is less than D.

    Thus, it is impossible.
    You are assuming that the best way to cover the circle with n strips is to be greedy: first find the best way to lay 2 strips, then find the best way to lay the 3rd one, etc., where "best" means - covers a disc of maximum diameter.
    But you didn't prove this is the best way to cover the disc. How do you know that the best way to cover a disc with n strips is - lay n-1 strips in a way that covers maximum area, then lay the nth strip? maybe you can lay the first n-1 strips in a way that is not optimal if these were all the strips you have, but when you add the nth strip, the max disc covered will be bigger than if you layed the n-1 strips in optimal way and then added the nth strip?
  14. Standard member Agerg
    The 'edit'or
    31 Jan '08 03:48 / 4 edits
    Pedantry hat on...

    Lemma: the method of filling an area with strips of infinite length who's width sum is minimum is to lay them parallel

    Proof: Since the strips are of infinite length it is true that for an arbitrary partition P of an area A there exists a smallest line AB of length W such that a a strip of width W running perpendicular to AB will completely cover P.
    For such a partition Incline a strip of width W2 at an angle: 90 deg > theta > 0 deg to AB
    The width W2 required to completely cover P >= W/cos(theta) > W [1]
    Let there exist a line CD of length W3 such that a sum of widths of parallel strips equal to W3 is minimally sufficient to cover A
    let there exist contiguous partitions of A that run parallel to CD, then by [1] the width sum of any strips not all perpendicular to CD > W3 if A is to be covered completely.

    Hence laying strips parallel is the optimum method of covering an area A such that width sum is smallest.




    Assume for contradiction that you can lay strips on the circle such that the sum of widths is less than the circle's diameter D.
    Choose the method that will cover the greatest area with the least number of strips. (that where all strips being parallel)
    A circle being completely covered by strips implies that at no point along a line drawn from one point of a circle to another does it not coincide with a strip. a diameter D is such a line, therefore there exists no point on this line that doesn't coincide with a strip. The method we have chosen is such that all strips are parallel. Therefore the sum of widths >= D. This is a contradiction thus the assumption false.
    Hence the sum of strips covering a circle >= D
  15. 01 Feb '08 09:52
    Originally posted by David113
    You are assuming that the best way to cover the circle with n strips is to be greedy: first find the best way to lay 2 strips, then find the best way to lay the 3rd one, etc., where "best" means - covers a disc of maximum diameter.
    But you didn't prove this is the best way to cover the disc. How do you know that the best way to cover a disc with n strips i ...[text shortened]... will be bigger than if you layed the n-1 strips in optimal way and then added the nth strip?
    Not really-I found the best way to lay the first strip, then cut up the next two and layed the cuts in the best possible way thus meaning I've covered more than or equal to the best area possible by laying them without cutting them up. It is, in an abstract world, the best way of laying any number of strips.

    Then this is the best way of laying n-1 strips AND the best way of laying n strips. So laying n-1 strips in this way, and adding another strip would yield the same result as laying all n strips in one go.