unfortunately you’re not necessarily cutting in a grid!

]]>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

]]>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

]]>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 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. ]]>