Challenge Math Challenge by Erland #1

17,507
7,077
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:
406
63
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.
 
33,236
8,950
Length of original rectangle must also be an integer value.
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.
 
406
63
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.
Well I guess I'm gonna take the L on this one then :oldfrown:
 

Erland

Science Advisor
735
135
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
 
33,236
8,950
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.
 
849
145
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:
33,236
8,950
Sure.
Those two subrectangles don't cover the whole rectangle, however.
 

Erland

Science Advisor
735
135
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.
 
33,236
8,950
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:

Erland

Science Advisor
735
135
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:
33,236
8,950
Well, sure, the integral is obviously invariant under a shift of lower and upper limit together. I generalized the integration limits.
 
406
63
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?
 

Erland

Science Advisor
735
135
Well, sure, the integral is obviously invariant under a shift of lower and upper limit together. I generalized the integration limits.
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.
 

Erland

Science Advisor
735
135
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?
It does not represent anything in particular, it just can be used to prove the proposition. :smile:
 
33,236
8,950
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.
... 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.
 

Erland

Science Advisor
735
135
Now it is right! Very good! You'll have the credit mfb!
 

QuantumQuest

Science Advisor
Insights Author
Gold Member
858
436
Just a simple observation regarding the given of the problem. We can make the assumption

Each subrectangle has at least one side with integer length.
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:

Erland

Science Advisor
735
135
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.
 
73
4
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?
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.
 

Attachments

33,236
8,950
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)
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.
 
73
4
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.
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.
 
33,236
8,950
Individually the posts work, but you cannot combine them. With the sides from my previous post:

rectangles.png
 

Want to reply to this thread?

"Math Challenge by Erland #1" You must log in or register to reply here.

Related Threads for: Math Challenge by Erland #1

Replies
23
Views
2K
Replies
49
Views
4K
Replies
8
Views
1K
Replies
8
Views
2K
Replies
26
Views
3K
Replies
18
Views
1K
Replies
7
Views
1K
Replies
13
Views
1K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top