1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Featured Challenge Math Challenge by Erland #1

Tags:
  1. Mar 18, 2017 #1
    Submitted by @Erland
    Solution Credit: @mfb

    RULES:

    1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
    2) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
    3) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
    4) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.

    CHALLENGE:
    A rectangle is divided into a finite number of subrectangles. The sides of the subrectangles are all parallell to sides of the large rectangle.
    Each subrectangle has at least one side with integer length.

    Prove that the large rectangle also has at least one side with integer length.
     
    Last edited: Mar 20, 2017
  2. jcsd
  3. Mar 18, 2017 #2
    upload_2017-3-18_19-50-2.png
    LW is original rectangle. Divide it into a finite number of subrectangles (4 are shown, but any number could work), each with a length Z, which is an integer value. Therefore...
    L = Z + Z + Z + Z
    L = 4(Z)
    Length of original rectangle must also be an integer value.
     
  4. Mar 18, 2017 #3

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    If you divide it like that. You have to show that there is no possible division for non-integer values. You can't do that by picking a single one and showing that this specific one does not work.

    The problem is not as easy as it might look.
     
  5. Mar 18, 2017 #4
    Well I guess I'm gonna take the L on this one then :oldfrown:
     
  6. Mar 19, 2017 #5

    Erland

    User Avatar
    Science Advisor

    The subrectangles might form a quite irregular pattern, like the attached one. All that is given is that each subrectangle has a side which has integer length. It could be the horizontal side, the vertical side, or both, and this might differ between the subrectangles.

    rectagle.png
     
  7. Mar 19, 2017 #6

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    I don't know if it leads to a proof, but if there is a solution, then there is also a solution where no two rectangles share exactly one side. This step is quite easy to prove.
    Unfortunately there are patterns with more than one rectangle where no two rectangles share exactly one side.
     
  8. Mar 19, 2017 #7
    A subrectangle has the integer side parallel to length of large rectangle and another subrectangle has the integer side parallel to breadth of larger rectangle. Those subrectangles have only one integer side.

    Is this possible ?
     
    Last edited: Mar 19, 2017
  9. Mar 19, 2017 #8

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    Sure.
    Those two subrectangles don't cover the whole rectangle, however.
     
  10. Mar 20, 2017 #9

    Erland

    User Avatar
    Science Advisor

    The only solution to this problem I know of is short, surprising, and beautiful, but almost impossible to find out if one doesn't already know it. Therefore, I'll give a hint:

    Consider the complex valued integral ##\int_a^b e^{2\pi i x}dx##, with ##a## and ##b## real. Under what conditions is this integral ##0##?

    If you think along these lines, you might find the solution.

    It this hint doesn't help, I'll elaborate on it in a few days.
     
  11. Mar 20, 2017 #10

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    That is amazing.

    Consider the integral $$\int_{x_{min}}^{x_{max}} dx \int_{y_{min}}^{y_{max}} dy e^{2 \pi i (x+y)} = \left(\int_{x_{min}}^{x_{max}} dx e^{2 \pi i x} \right) \left( \int_{y_{min}}^{y_{max}} dy e^{2 \pi i y} \right)$$
    It is zero if and only if xmax-xmin or ymax-ymin is an integer. It is an integral of a function over a rectangle, therefore we can write it as sum of several integrals over subrectangles. For each subrectangle, the same rules apply: The integral is zero if one of the side lengths is an integer. All our subrectangles satisfy this condition, therefore the large rectangle has to satisfy it as well (0+0+...=0): at least one side length has to be an integer.

    Edit: Generalized integration limits.
     
    Last edited: Mar 20, 2017
  12. Mar 20, 2017 #11

    Erland

    User Avatar
    Science Advisor

    Very good mfb, but you must fix the integration limits. Even if the large rectangle has a vertex at the origin, the subrectangles will not.

    Edit: mfb fixed this. The present solution is correct.
     
    Last edited: Mar 20, 2017
  13. Mar 20, 2017 #12

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    Well, sure, the integral is obviously invariant under a shift of lower and upper limit together. I generalized the integration limits.
     
  14. Mar 20, 2017 #13
    Oh dang I wish I knew what all of that meant :bow: I need to reattempt teaching myself calculus now. @Erland what does that integral you gave out even represent?
     
  15. Mar 20, 2017 #14

    Erland

    User Avatar
    Science Advisor

    This is not true in general. For example: ##\int_{-1/2}^0e^{2\pi i x} dx\neq \int_0^{1/2}e^{2\pi i x}dx##.
    You obviously understand the idea, but this detail is unclear in your solution.
     
  16. Mar 20, 2017 #15

    Erland

    User Avatar
    Science Advisor

    It does not represent anything in particular, it just can be used to prove the proposition. :smile:
     
  17. Mar 20, 2017 #16

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    ... for the question if it is zero or not. After your first comment I changed my previous post to take the more general integration limits into account.
     
  18. Mar 20, 2017 #17

    Erland

    User Avatar
    Science Advisor

    Now it is right! Very good! You'll have the credit mfb!
     
  19. Mar 20, 2017 #18

    QuantumQuest

    User Avatar
    Science Advisor
    Gold Member

    Just a simple observation regarding the given of the problem. We can make the assumption

    as "each subrectangle has at least one pair of sides with integer length", as we're talking about rectangles. Now, we can work for a random such subrectangle using the hint by Erland, with the function ## f(x,y) = e^{2\pi i x}e^{2\pi i y}## and integrate it over its sides i.e ##\int_a^b\int _c^d e^{2\pi i x}e^{2\pi i y}\,dx\,dy ##. Now, if we calculate this integral, it turns out that it equals zero, if and only if at least one of the differences of its sides is an integer i.e. if b - a or d - c is an integer (I have done the calculation but I omit it here). But according to the above (modified) assumption each subrectangle has at least a such pair, so the integral of ##f## over it is zero. So, the integral over the whole rectangle is also zero. Then, this whole rectangle must also have an integer pair of sides and a fortiori one integer side. Just wondering if it is correct way to solve it.
     
    Last edited: Mar 20, 2017
  20. Mar 20, 2017 #19

    Erland

    User Avatar
    Science Advisor

    Yes it's a correct solution, Quantum Quest. It is essentially the same solution as mfb's, but mfb came before you and gets the credit. Of course, for a rectangle, the conditions "at least one side has integer length" and "at least one pair of parallell sides have integer length" are equivalent.
     
  21. Mar 20, 2017 #20
    Did we already forget who came before mfb? :wink::wink::wink:
     
  22. May 31, 2017 #21
    For those of us who are not familiar with complex integrals (still in highschool...) I would like to present my own attemp. I can't assure my proof is 100% correct, but still, please, tell me what you think and how to improve it.
    -----------------------------------------------------------------------------------
    The intuition is to delete the subrectangles one by one according to some rules and leave bigger and bigger rectangles until only our external rectangle is left.
    First lemma:
    Given a rectangle which consists of two smaller rectangles, and they satisfy: "at least one side with integer length", thus, the big rectangle also satisfies this condition.

    Proof:
    upload_2017-5-31_23-55-13.png
    a is an integer ⇒ the big rectangle has at least one side with an integer length.
    a is not an integer⇒ b is integer and c is integer ⇒ b+c is an integer, the big rectangle has at least one side with integer length.
    q.e.d
    Second lemma:
    Given a rectangle which consists of three smaller rectangles, as showed in the sketch, and they satisfy: "at least one side with integer length", thus, the big rectangle also satisfies this condition.

    upload_2017-5-31_23-56-3.png
    proof:
    Use the first lemma twice.

    Third lemma:
    upload_2017-6-1_0-28-18.png
    Elongate bd to h.
    upload_2017-6-1_0-30-45.png


    Let abcd cefg be rectangles with an integer side. (assume ab is the integer, if ac is the integer, it is really the same, just rotate the sketch)
    Then, cghd and dhfe also have an integer side.
    proof:

    ab is an integer⇒ cd is an integer⇒cghd satisfies the lemma.
    If ef is an integer ⇒ dhfe satisfies the lemma.
    ef is not an integer⇒ ec is an integer ⇒ ec-dc is an integer ⇒ed is an integer⇒dhfe satisfies the lemma.
    q.e.d.
    According to the first lemma, we can draw:
    upload_2017-6-1_0-41-40.png
    --------------------------------------------------------------------------------------------------------------------
    rectagle-png.png
    Let's examine Erland's sketch:
    First, we should apply the first and the second lemmas to simplify the sketch.
    We get:
    upload_2017-6-1_0-48-59.png
    Wow! it simplified very well! each of these rectangles has an integer side.
    Here is where the third lemma comes to save us.
    Let's apply it to the middle rectangle. (I will show the option where the horizontal lines are the integers, but it works also to the vertical lines.)
    upload_2017-6-1_0-56-49.png
    Now, it's piece of cake...
    Just use the first and the second lemmas again, and you can prove that the original rectangle has an integer length.
    I believe it should always work. If you disagree, please explain your position, and try to correct the proof.
     

    Attached Files:

  23. May 31, 2017 #22

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    Let ac=1, ab=pi, cg=pi, gf=4. Splitting it into three rectangles fails, as you create a pi squared rectangle, no matter how you rotate it.

    I was at that point as well.
    There are other ways to rearrange rectangles, but you need a proof that you can simplify every possible pattern with these operations, and that is far from trivial.
     
  24. May 31, 2017 #23
    Actually, what I meant is that we can't say which of the sides is an integer. But the proof is the same, and it is enough to show that it works for one side, since we can always find in the rectangle:
    upload_2017-6-1_2-56-23.png
    I hope it is more convincing.
     
  25. May 31, 2017 #24
    I think I should have added this rule too: d is integer
    upload_2017-6-1_3-31-50.png
     

    Attached Files:

  26. May 31, 2017 #25

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    Individually the posts work, but you cannot combine them. With the sides from my previous post:

    rectangles.png
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted