Fun with Geometry II
You have a rectangle divided into smaller rectangles. You know that each smaller rectangle has integral length or integral width. Prove that the original rectangle also has integral length or integral width.
From http://study.haifa.ac.il/~oshapi03/html/think~1.htm.
unfortunately you’re not necessarily cutting in a grid!
We have to demonsrate that (ALL small rectangles have integral width OR length) => (big rectangle has integral length OR width).
Using [(A or B)=>(C or D)] [(not(D) and not(C))=>(not(A) and not(B))]
We have to demonstrate that (big rectangle has neither integral length nor width) => (one small rectangle has neither integral length nor width)
So, the width of the rectangle is not integral, meaning if you cut it up into segments, at least one of those segments has a non integral length. Let’s say the ”nth” segment isn’t integral.
Using the same reasoning on the length, the ”mth” segment isn’t integral.
So if we see the big rectangle as a grid, the smaller rectangle at the ”mth” line and the ”nth” row has neither an integral width, or an integral length. QED.. ? 🙂
the problem is it may not be split nicely like this ..s
Assume that the bigger rectagle is split into “m” lengthwise ( horizontal ) and “n” widthwise (vertical ) resulting in mxn smaller rectagles.
Go to the top left smaller rectangle. Assume its vertical side is “integer”. Then for the entire row from left to right of the bigger rectangle, all the smaller ones will have their vertical side “integer”. Hence all their horizontal side(top and bottom) is “non integer”.
Hence top side of the 2nd row of the smaller rectangles have “non-integer” as that side is common to both 1st row and second row. Hence their (of 2nd row) vertical side has to be integer. This continues till the end. The same reasoning can be applied length-wise.
I do not believe this induction is valid
The problem is imagine n is say 5. You don’t necessarily have one rectangle whose side is the length or width of the full
rectangle, or similarly you don’t know that n-1 form a rectangle that’s ‘full’.
The “it must be true that” part is when we use the inductive hypothesis.
To use mathematical induction to prove that a statement is true for all natural numbers, we have to:
1. Show that the statement holds when n is equal to the lowest value that n is given in the question. Usually, n = 0 or n = 1.
2. The inductive step: showing that if the statement holds for some n, then the statement also holds when n + 1 is substituted for n.
In this special case, the statement we are trying to prove is:
If R is a rectangle such that it is composed of n smaller rectangles (R1,…RN) such that each smaller rectangle has integral length or integral width then R also has integral length or integral width.
The first step was proving that the case when the original rectangle R is formed by exactly 2 smaller rectangles R1 and R2 (the case when R is formed by exactly 1 rectangle is trivial). I proved it like this:
The fact that R1 and R2 can be arranged to form the rectangle R means that R1 and R2 must share one side length “L” that will be either the length or the width of R. We know that R1 and R2 have integral length or integral width, so “L” could be an integer, in which case we are done, if “L” is not an integer, then the other side length of R measures the addition of the lengths of the integral sides of R1 and R2 and is therefore also an integer.
At this point, the mathematical induction allows me to assume that the statement is true up to some number n.
The next thing I did was explicitly show the inductive hypothesis:
We assume that the result is true if R is composed of n rectangles.
Therefore, if R is composed of n+1 rectangles, we can consider this n+1 rectangles in two different sets, one set consisting of n rectangles and the other one consisting only of 1 rectangle.
I am allowed to use the mathematical induction in the set that has n rectangles, and using it means that we can arrange those n rectangles to form a rectangle R1 that has integral length or integral width. This is the “it must be true that part”. Then, the general result follows from the fact that we already proved the case when the original rectangle R is formed by exactly 2 smaller rectangles R1 and R2.
I don’t see why ” it must be true that ” …. You need more detail here. //s
By induction:
We first prove the case when the original rectangle R is formed by exactly 2 smaller rectangles R1 and R2. The fact that R1 and R2 can be arranged to form the rectangle R means that R1 and R2 must share one side length “L” that will be either the length or the width of R. We know that R1 and R2 have integral length or integral width, so “L” could be an integer, in which case we are done, if “L” is not an integer, then the other side length of R measures the addition of the lengths of the integral sides of R1 and R2 and is therefore also an integer.
We assume that the result is true if R is composed of n rectangles.
If R is composed of n+1 rectangles, it must be true that we can arrange n of those rectangles to form a rectangle R1 that has integral length or integral width, by hypothesis, the remaining rectangle (we can call it R2) also has integral length or integral width. The general result is now proved since we already proved the case when R is formed by exactly 2 smaller rectangles R1 and R2.
I think you misread the problem. The problem states each smaller rectangle has EITHER integral length OR integral width; it might be both, but then again, it might not. Your method shows that the big rectangle MUST have both integral length and width, but that need not be true. Imagine a rectangle with length 2sqrt(2) and height 1; we can break this into two rectangles of width sqrt(2) and height 1; each smaller rectangle has one integral side and one non-integral side.
Take all the integral widths of each rectangle in one row of rectangles in the original rectangle. Once you add them all together, you will get the width of the original rectangle which will be an integral width.
Take the integral lengths of each rectangle in one collumn of rectangles in the original rectangle. Once you add them together, you will get the length of the original rectangle which will be an integral length.
I think you need more details — email me at [email protected]
Well, when you add together the integral widths it will add up to an integral number. Same with the integral length.
sure
Is it safe to assume that all shapes only have an integral width or length?
means they are integers, like 4 or 1701, not numbers like 4.5 or sqrt(2) or pi.
What is an “integral length” and “integral width”?
That’s a good start.
sum or product of intergers is an integer