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
    2016 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
    2016 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
    2016 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
    2016 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
    2016 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
    2016 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
    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:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Math Challenge by Erland #1
Loading...