|
+ Show Spoiler +2) Let's use the same coordinates as blankspace:
Label all the vertices of the squares in the subdivision of the rectangle as v_0,v_1,v_2,...,v_n.
Consider the 45 degree line passing through (0,0) and let P be the projection map onto this line.
Let w_i denote P(v_i).
The image of P is a 1-dimensional real vector space which inherits a norm from the copy of the plane it sits in.
We have marked some elements w_i in this vector space. WLOG we can order these so that they weakly increase in norm.
In particular:
1) w_0 refers to 0 (corresponding to the lower-left corner of the rectangle)
2) w_n refers to the element with largest norm (corresponding to the upper-right corner)
The key is to note that every w_i for 0<i<n exists as the average of two other w_j.
It follows by induction on norm that the span of the w_i is a 1-dimensional Q-subspace of the image of P considered as a Q-vector space.
That should do it I believe...
|
United States24799 Posts
On September 06 2011 09:54 MrDonkeyBong wrote:Show nested quote +On September 06 2011 06:21 micronesia wrote:
Gar.... I hate math puzzles that you can't work on unless you studied higher math... XD
I have no idea how to show if things are or are not rational ._. We did rational numbers last year (9th grade). I think the curriculum changed on you
Um, I learned what a rational number is also. I'm talking about using proofs to show whether or not numbers will be rational in various situations.
|
Muirhead:
+ Show Spoiler +I like the idea but I'm not sure I follow the induction
|
On September 06 2011 12:43 sidr wrote:Muirhead: + Show Spoiler +I like the idea but I'm not sure I follow the induction
Nice puzzle  . Sorry I explain everything awkwardly...
maybe later I try to motivate it... I think it's always a good exercise to refine a proof or think why one does things, especially with a good problem like this
For now though the induction. Let's write it as lemma:
+ Show Spoiler +We are given a finite collection of real numbers which satisfies:
(1) 0 is its minimum member
(2) Each member strictly between 0 and the maximum member is the average of two other members.
I claim each member of the collection is a nonnegative rational multiple of the maximum member.
For this, it suffices to prove that each non-maximal member is a nonnegative rational combination of strictly larger members.
Suppose not. Then there is a smallest counterexample A. A is not 0, since 0 is a nonnegative rational combination of larger guys trivially. Thus, A is the average of two other members. Writing A as this average we can apply the minimality of A to massage the lower member of this average into a nonnegative rational linear combination of guys A or larger.
Since the part of this combination that is not a multiple of A is strictly positive, we cannot completely cancel out A and so have a contradiction.
|
Foolishness
United States3044 Posts
I have an idea...
For solving number 2) in the OP, say you already have a square (which is a rectangle by definition), then you satisfy the requirement (a/b is rational) trivially.
Take our rectangle with side lengths a and b with a < b. Observe the smallest square that is created when we partition our rectangle into squares. Call any side of this square s. I claim that there necessarily exists another square (created from our partitions) that has side of ms where m is some positive integer. I also claim that this square will be the next to smallest square. *
Let's suppose for now that my claim is true. Then we can recursively apply this fact to the next higher up square. For example, we know there exists a square with side ms. If this square is not the biggest square, then there exists another square with side mns, where n is some positive integer. We can keep doing this until every square is classified as such.
Now, when such a feat is accomplished, observe the lengths of a and b. Both of these lengths will necessarily be some multiple of s. For example we would expect something like b = s + 2ms + mns. Thus we can factor out an s, and when we divide we will be left over with all the m and n which are positive integers. Thus regardless of the rationality of s, a/b is rational.
* I am relatively certain my claim holds true, but I'm still working on the proof. The idea I have to verify my claim is with a proof by contradiction. If there did not exist another square with side of ms then it would be impossible to construct a rectangle using only squares. If this plan fails then I have another idea for a proof by contradiction which involves verifying that the area of all the squares equals the area of the whole rectangle. If there did not exist a side with length ms then the areas won't ever equal.
|
On September 06 2011 14:29 Foolishness wrote:
Take our rectangle with side lengths a and b with a < b. Observe the smallest square that is created when we partition our rectangle into squares. Call any side of this square s. I claim that there necessarily exists another square (created from our partitions) that has side of ms where m is some positive integer. I also claim that this square will be the next to smallest square. *
This is not true. Consider a 6x7 rectangle split into one 4x4, two 3x3, and two 2x2 squares.
Just something I noticed related to (2): the Euclidean algorithm provides an easy way to partition any rectangle with rational sides into squares.
|
Foolishness
United States3044 Posts
On September 07 2011 00:46 fasdaf wrote:Show nested quote +On September 06 2011 14:29 Foolishness wrote:
Take our rectangle with side lengths a and b with a < b. Observe the smallest square that is created when we partition our rectangle into squares. Call any side of this square s. I claim that there necessarily exists another square (created from our partitions) that has side of ms where m is some positive integer. I also claim that this square will be the next to smallest square. * This is not true. Consider a 6x7 rectangle split into one 4x4, two 3x3, and two 2x2 squares. Just something I noticed related to (2): the Euclidean algorithm provides an easy way to partition any rectangle with rational sides into squares.
Okay. Let me modify. Take the smallest square that is created by our partition and take the largest square created by our partition, and call the sides of these squares s and L respectively. I claim that the sides all other squares in the partition can be represented as a convex combination of s and L.
The rest of the proof should work out to be the same, although I may need to claim that s and L are both irrational or both rational.
|
ooh nice solution muirhead
|
m-m-math puzzles?....
I'm having flashbacks...
AARAARAHAGHHHAHGAHAHH E+ IN MATH OH GOD IM SO DISSAPOINTED IN MYSELF I HAVE TO END IT NOW AARGHAAAAHAHAAAAAh....
No... no math puzzles... I would like to forget
|
Good stuff Muirhead.
For anyone interested, here is a different solution to each puzzle:
1. + Show Spoiler +Orient the rectangle so that its sides are parallel with the x and y axes. Without loss of generality each smaller rectangle has an integer side length (scale by LCM of denominators). Then, consider Integral(exp(2*Pi*i*(x+y)) dx dy). This is 0 over a rectangle if and only if the rectangle has an integer side length. By additivity of the integral, we are done.
2. + Show Spoiler +Suppose the rectangle has side lengths 1,a with a irrational. We show a tiling of squares leads to a contradiction.
Suppose we have a tiling of squares and extend each line segment to the edges, creating a rectangular grid of our rectangle. Consider the set S={x: x is the side length of some rectangle in our rectangular grid}. Consider the vector space V over Q generated by S. As a is irrational, we may find a basis {1,a,b3,...,bk}. Define a linear functional f (a linear map from V to Q) by f(1) = 1, f(a) = -1, and f(bi) = 0 for i in {3,...,k}. Finally, define an "area" function on our subrectangles T by g(T)=f(c)f(d), where c, d are the side lengths of T. Then, note g is additive by linearity of f and g(S) is nonnegative for any square S, but g(R) = -1.
|
|
|
|
|
|
EPT
