Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Math Help - Problem 25

  1. #1
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9

    Problem 25

    1)Let S_1 be a square in the coordinate plane. Divide this square into 4 equal squares by drawing lines straight down the middle. Pick any one of the smaller squares, call it S_2. Now divide this square into 4 smaller squares, pick any one, call it S_3. And thus on. Let s_1,s_2,s_3,... be the sequence of points which represent the centers of S_1,S_2,S_3,... respectively. Show that (s_n) convergences to some point.

    2)Let U be a subset of \mathbb{R} which is closed under multiplication*. Let S \mbox{ and }T two disjoint sets whose union is U. With the property that the product of any three elements is again in the set. Show that one of the sets S,T must be closed under multiplication.

    3)Let x be a non-zero real number so that x+x^{-1} is an integer. Show that x^n + x^{-n} is an integer for every integer n.

    *)Meaning, if a,b\in U then ab\in U.
    Last edited by ThePerfectHacker; June 4th 2007 at 02:34 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jun 2007
    From
    Cambridge, UK
    Posts
    41
    How about this for Problem 1. It's not as formal as it could be, but I'm not a pure mathematician by a long way.

    - - -

    Consider a general square S_1 of dimension 2a, centred on co-ordinates s_1 = (x,y).

    Now, by inspection (see the figure), the four possible locations of the centre of S_2 are:

    s_2 = \left( x \pm \frac{a}{2}, y \pm \frac{a}{2}\right)

    ~~~~~~~~~~~~~~~~~ = \left( x + \lambda_{1} \frac{a}{2}, y + \mu_{1} \frac{a}{2}\right)

    where \lambda_{1} and \mu_{1} are just multipliers taking the value +1 or -1, depending on our choice.

    If we now split that square similarly to form S_3, the centre of that square will be at

     s_3 = \left( x + \lambda_{1} \frac{a}{2} + \lambda_{2} \frac{a}{4}, y + \mu_{1} \frac{a}{2} + \mu_{2} \frac{a}{4} \right)

    with \lambda_2 , \mu_2 defined similarly. Extend this principle to the Nth square, whose centre will be at

    s_N = (x + a \sigma_{xN}, y + a \sigma_{yN})

    with \sigma_{xN} = \sum_{i=1}^{N} \lambda_i \frac{1}{2^i} and \sigma_{yN} = \sum_{i=1}^{N} \mu_i \frac{1}{2^i}

    The problem of whether the squares' centres will converge, as N \rightarrow \infty, is now reduced to the convergence (or not) of these two series.

    It is not particularly troublesome that the sums contain the arbitrary sign-changing constants  \{ \lambda_i , \mu_i \}, because of a basic property of infinite series (assumed here) :

    "The series \sum u_n converges if the series \sum |u_n| does." (ref: Absolute convergence .)

    The series \sum_{i=1}^{N} \frac{1}{2^{i}} converges to unity. Hence, the x- and y- coordinates of s_N converge to definite values, regardless of our choices of sign along the way. (QED!)
    Attached Thumbnails Attached Thumbnails Problem 25-sketch2.gif  
    Last edited by Pterid; June 4th 2007 at 12:32 PM. Reason: cleanup
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Rebesques's Avatar
    Joined
    Jul 2005
    From
    At my house.
    Posts
    527
    Thanks
    7
    . It's not as formal as it could be, but I'm not a pure mathematician by a long way.
    Don't be so humble, I think the proof is really good.


    Now, about my attempt for 1. Consider the square to be ranging from -2 to 2 on every axis. The sequence of centers then satifies ||{\bf s}_{m+1}-{\bf s}_m||\leq \sqrt{2}\left(\frac{1}{2}+\ldots+\frac{1}{2^m}\rig  ht)\leq \frac{\sqrt{2}}{2}, so it is a Cauchy sequence.

    For 3, induction gives an answer, but I don't like that kind of proof Let me look if I can find something better.

    For 2, I am at a loss Hacker's love for algebra has ruined him!!
    Last edited by Rebesques; June 12th 2007 at 05:33 PM. Reason: being dumb in calculations
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Rebesques View Post
    For 2, I am at a loss Hacker's love for algebra has ruined him!!
    This is far from an algebra question. I try to keep these problems elementary.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Rebesques's Avatar
    Joined
    Jul 2005
    From
    At my house.
    Posts
    527
    Thanks
    7
    I try to keep these problems elementary.

    Like that's supposed to make me feel better
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jun 2007
    From
    Cambridge, UK
    Posts
    41
    Coincidentally, Problem 3 just came up in this thread...

    http://www.mathhelpforum.com/math-he...ion-proof.html
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jan 2006
    Posts
    56
    for probleme 1 i have got an idea that i don't know if i will be able to translate it in english

    topoligicaly speeking a square is a 'closed' part of the space (un 'espace fermé' or 'fermé' in french wich as a part of R*R admit the 'banach property "every infinite serie of point of it admit an convergent 'extraded' serie (a convergent infinite serie constructed by forgoting some points of the serie from wich it is extracted)
    it will be relatively easy to proove that every extracted series that you can build will converge to points not more distant that a predefinite epsilon of your choice
    that's just an idea i'm essentialy trying my english and if i would like to be a litle bit more rigourous i would need to take a sheet of paper and a boock
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jan 2006
    Posts
    56
    for problem 3 i should say that you can say anything you want about the empty set!!

    i made a knew post because i could not edit the latest one
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jan 2006
    Posts
    56
    i reply number two in order to correct my two previous thread (there is indeed a problem whith that if anyone has got a solution?)
    last one was stupid i could'nt cancel it
    the one before i was speaking about what we call in france and probably everywhere bolzano-weistrat property (banach is the nature of the 'closed' 'space' thath admit that property)nce you have extracted a one-at-least convergent serie you just have to proove that your serie Sn converge to the same point

    but lets try to do number two
    if S and T would not be steady by multiplication (excuse my poor memory)
    there would be As and Bs and Cs belonging to S
    and At and Bt and Ct belonging to T

    with As*Bs=Ct and At*Bt=Cs
    because all this number belongs to U wich is steady by multiplication and because S and T are forming a partition of U
    so in U were allowed to write As*Bs*Cs=At*Bt*Ct
    so if the property that the multiplication of tree elements of the two subset belongs to the subset S and T they therefor have a comon element and cannot form a partition!!!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    1)This problem was inspired from a proof I saw of a certain theorem. The proof was elegantly proven by enclosing a bounded set into a square and creating this nested sequence of squares. So I decided to make this a problem of the week.

    The trick is to think of Cauchy Sequences. That is what Rebesques was suggesting. Doing this the ordinary way, i.e. convergent sequences might be difficult.

    We can think of these sequence of points as complex numbers, if you want to. But that is not necessary. Let L be the length of the square. Then the maximum distance between any two points in S_1 is \frac{L\sqrt{2}}{2}, i.e. the diagnol. The length of the side of S_2 is \frac{L}{2} and hence the maximum distance between any two points in S_2 is \frac{L\sqrt{2}}{2^2}. By induction the maximum distance between any two points in S_n is \frac{L\sqrt{2}}{2^n}.
    Let s_1,s_2,s_3,... be the sequence of centers of these squares. It is necessary and sufficient to show that (s_n) is a Cauchy sequence. Let \epsilon >0 then it is possible to find such an N>0 so that \frac{L\sqrt{2}}{2^n} < \epsilon for all n>N because \lim \frac{L\sqrt{2}}{2^n} = 0. But if n,m>N then s_n,s_m all lie in the S_{N+1} square because S_{k+1} \subset S_k. But by above arguments the maximum distance between any two points in S_{N+1} is \frac{L\sqrt{2}}{2^{N+1}} < \epsilon. And so if n,m>N we have |s_n-s_m| < \epsilon. Hence (s_n) is convergent (eventhough we have no idea what it converges to).
    \mathbb{Q}uad \ \mathbb{E}ra \ \mathbb{D}emonstrandum.
    -----
    2)I found this nice problem in some book. The following is my argument. First if U = \{ \} the proof is immediate. And if S \mbox{ or }T = \{ \} then the proof is immediate again. Having desposed the trivial cases let us consider a non-empty subset U of \mathbb{R} which is closed. And we can safely say that S,T are non-empty subsets of U. We will argue by contradiction: assume that both are not closed. Hence, there exists s_1,s_2\in S \mbox{ and }t_1,t_2\in T with the property that s_1s_2 \not \in S \mbox{ and }t_1t_2 \not \in T. But since these are disjoint subsets with the condition that S\cup T = U and that U is closed we must have s_1s_2 \in U \mbox{ and }t_1t_2 \in U thus s_1s_2 \in T \mbox{ and }t_1t_2 \in S. We have shown that t_1,t_2,s_1s_2 \in T \mbox{ and }s_1,s_2,t_1t_2 \in S. Now we use the condition that the product of any three elements in again in the set and hence: t_1t_2(s_1s_2) \in T \mbox{ and }s_1s_2(t_1t_2)\in S. But that means S\cap T \not = \{ \} which is a contradiction. Which means one of these sets must be closed.
    \mathbb{Q}uad \ \mathbb{E}ra \ \mathbb{D}emonstrandum.
    -----
    3)This was fully answered before and a link was given. The nice thing about this problem is that ordinary induction does not work. This is a good time to learn Strong Induction.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Jun 2007
    From
    Cambridge, UK
    Posts
    41
    Quote Originally Posted by ThePerfectHacker View Post
    The trick is to think of Cauchy Sequences. That is what Rebesques was suggesting. Doing this the ordinary way, i.e. convergent sequences might be difficult.
    TPH,

    My argument above was not particularly difficult... is it wrong?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Pterid View Post
    TPH,

    My argument above was not particularly difficult... is it wrong?
    Did I say it was wrong? I did not read it. The solution I gave was just a different solution.
    You should remember the rule that there are sometimes many ways to prove a theorem.*



    *)For example, Quadradic Reciprocity, what a beautify law, there are more than 200 ways to prove it!!!
    Last edited by ThePerfectHacker; June 11th 2007 at 12:17 PM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Jan 2006
    Posts
    56
    for problem one i think my idea of usin bolzano-weistrass theorem is not so bad because it is probable that most of the theorem used to proove it other ways use need this theorem (may be even the cauchy sequence) and also because whathever strange and arbitrary you would had cut you square in pieces select one pieces and then cut it in up again ect...this theorem prooves that you got a convergent serie (it would be nice to try to proove the arbitrary cuting problem whithout using the bolzano_weistrass théorème anyway)

    for problem two i think it is useless to proove anything about U S and T when they are the empty set because they have no element so we cannot say anything about the product of two element of such set.
    usualy set closed by order are groups (which are none empty) or that sort of thing
    beter look to the definition of a set closedby multiplication to see if it admits empty set by definition but demonstration is useless about what do or do not elements of the empy set!

    for number 3 i found only one trivial (x=1) solution of the hypotesisis of recurence for n=1
    it would be nice to have an other exemple of x to have a concrete idea of what strong induction is
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Jan 2006
    Posts
    56
    i just read (qweqly ) the article about the cauchy sequence it seemed to be something usefull and direct to deal whith that sort of problemeven the arbitrary one of mine (i going to read it in french in my old courses (theres many years i havent been working seriously math) and i began to get some doubts (this is usual when dealing whith math) ))
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Junior Member
    Joined
    Jun 2007
    From
    Cambridge, UK
    Posts
    41
    Quote Originally Posted by ThePerfectHacker View Post
    Did I say it was wrong? I did not read it. The solution I gave was just a different solution.
    You should remember the rule that there are sometimes many ways to prove a theorem.*

    *)For example, Quadradic Reciprocity, what a beautify law, there are more than 200 ways to prove it!!!
    No, indeed you did not say it was wrong. I was just interested when you suggested...

    The trick is to think of Cauchy Sequences. That is what Rebesques was suggesting. Doing this the ordinary way, i.e. convergent sequences might be difficult.
    ...that proving the proposition without the concept of a Cauchy sequence would be 'difficult'. In my inexperience, this led me to doubt that my (fairly short) argument was valid at all.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Search Tags


/mathhelpforum @mathhelpforum