# Problem 25

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Jun 4th 2007, 11:11 AM
ThePerfectHacker
Problem 25
1)Let $\displaystyle 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 $\displaystyle S_2$. Now divide this square into 4 smaller squares, pick any one, call it $\displaystyle S_3$. And thus on. Let $\displaystyle s_1,s_2,s_3,...$ be the sequence of points which represent the centers of $\displaystyle S_1,S_2,S_3,...$ respectively. Show that $\displaystyle (s_n)$ convergences to some point.

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

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

*)Meaning, if $\displaystyle a,b\in U$ then $\displaystyle ab\in U$.
• Jun 4th 2007, 12:31 PM
Pterid
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 $\displaystyle S_1$ of dimension $\displaystyle 2a$, centred on co-ordinates $\displaystyle s_1 = (x,y)$.

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

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

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

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

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

$\displaystyle 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 $\displaystyle \lambda_2 , \mu_2$ defined similarly. Extend this principle to the Nth square, whose centre will be at

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

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

The problem of whether the squares' centres will converge, as $\displaystyle 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 $\displaystyle \{ \lambda_i , \mu_i \}$, because of a basic property of infinite series (assumed here) :

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

The series $\displaystyle \sum_{i=1}^{N} \frac{1}{2^{i}}$ converges to unity. Hence, the x- and y- coordinates of $\displaystyle s_N$ converge to definite values, regardless of our choices of sign along the way. (QED!)
• Jun 6th 2007, 04:51 PM
Rebesques
Quote:

. 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 $\displaystyle ||{\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 :confused: Hacker's love for algebra has ruined him!!:p
• Jun 6th 2007, 05:14 PM
ThePerfectHacker
Quote:

Originally Posted by Rebesques
For 2, I am at a loss :confused: Hacker's love for algebra has ruined him!!:p

This is far from an algebra question. I try to keep these problems elementary.
• Jun 6th 2007, 05:26 PM
Rebesques
Quote:

I try to keep these problems elementary.

Like that's supposed to make me feel better :p
• Jun 7th 2007, 02:33 AM
Pterid
Coincidentally, Problem 3 just came up in this thread... :)

http://www.mathhelpforum.com/math-he...ion-proof.html
• Jun 7th 2007, 08:15 AM
SkyWatcher
for probleme 1 i have got an idea that i don't know if i will be able to translate it in english
:o
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 :confused:
• Jun 7th 2007, 08:41 AM
SkyWatcher
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:D
• Jun 8th 2007, 05:16 AM
SkyWatcher
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):once 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!!!
• Jun 10th 2007, 07:25 PM
ThePerfectHacker
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 $\displaystyle L$ be the length of the square. Then the maximum distance between any two points in $\displaystyle S_1$ is $\displaystyle \frac{L\sqrt{2}}{2}$, i.e. the diagnol. The length of the side of $\displaystyle S_2$ is $\displaystyle \frac{L}{2}$ and hence the maximum distance between any two points in $\displaystyle S_2$ is $\displaystyle \frac{L\sqrt{2}}{2^2}$. By induction the maximum distance between any two points in $\displaystyle S_n$ is $\displaystyle \frac{L\sqrt{2}}{2^n}$.
Let $\displaystyle s_1,s_2,s_3,...$ be the sequence of centers of these squares. It is necessary and sufficient to show that $\displaystyle (s_n)$ is a Cauchy sequence. Let $\displaystyle \epsilon >0$ then it is possible to find such an $\displaystyle N>0$ so that $\displaystyle \frac{L\sqrt{2}}{2^n} < \epsilon$ for all $\displaystyle n>N$ because $\displaystyle \lim \frac{L\sqrt{2}}{2^n} = 0$. But if $\displaystyle n,m>N$ then $\displaystyle s_n,s_m$ all lie in the $\displaystyle S_{N+1}$ square because $\displaystyle S_{k+1} \subset S_k$. But by above arguments the maximum distance between any two points in $\displaystyle S_{N+1}$ is $\displaystyle \frac{L\sqrt{2}}{2^{N+1}} < \epsilon$. And so if $\displaystyle n,m>N$ we have $\displaystyle |s_n-s_m| < \epsilon$. Hence $\displaystyle (s_n)$ is convergent (eventhough we have no idea what it converges to).
$\displaystyle \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 $\displaystyle U = \{ \}$ the proof is immediate. And if $\displaystyle S \mbox{ or }T = \{ \}$ then the proof is immediate again. Having desposed the trivial cases let us consider a non-empty subset $\displaystyle U$ of $\displaystyle \mathbb{R}$ which is closed. And we can safely say that $\displaystyle S,T$ are non-empty subsets of $\displaystyle U$. We will argue by contradiction: assume that both are not closed. Hence, there exists $\displaystyle s_1,s_2\in S \mbox{ and }t_1,t_2\in T$ with the property that $\displaystyle s_1s_2 \not \in S \mbox{ and }t_1t_2 \not \in T$. But since these are disjoint subsets with the condition that $\displaystyle S\cup T = U$ and that $\displaystyle U$ is closed we must have $\displaystyle s_1s_2 \in U \mbox{ and }t_1t_2 \in U$ thus $\displaystyle s_1s_2 \in T \mbox{ and }t_1t_2 \in S$. We have shown that $\displaystyle 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: $\displaystyle t_1t_2(s_1s_2) \in T \mbox{ and }s_1s_2(t_1t_2)\in S$. But that means $\displaystyle S\cap T \not = \{ \}$ which is a contradiction. Which means one of these sets must be closed.
$\displaystyle \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.
• Jun 11th 2007, 09:32 AM
Pterid
Quote:

Originally Posted by ThePerfectHacker
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?
• Jun 11th 2007, 10:40 AM
ThePerfectHacker
Quote:

Originally Posted by Pterid
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!!!
• Jun 11th 2007, 12:41 PM
SkyWatcher
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 :D
• Jun 11th 2007, 12:55 PM
SkyWatcher
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):) ))
• Jun 11th 2007, 01:24 PM
Pterid
Quote:

Originally Posted by ThePerfectHacker
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...

Quote:

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.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last