Problem 25

ThePerfectHacker · #1 $Old$ June 4th, 2007, 01:11 PM

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

Pterid · #2 $Old$ June 4th, 2007, 02:31 PM

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!)

Rebesques · #3 $Old$ June 6th, 2007, 06:51 PM

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 $||{\bf s}_{m+1}-{\bf s}_m||\leq \sqrt{2}\left(\frac{1}{2}+\ldots+\frac{1}{2^m}\right)\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!!

ThePerfectHacker · #4 $Old$ June 6th, 2007, 07:14 PM

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.

Rebesques · #5 $Old$ June 6th, 2007, 07:26 PM

Quote:

I try to keep these problems elementary.

Like that's supposed to make me feel better

Pterid · #6 $Old$ June 7th, 2007, 04:33 AM

Coincidentally, Problem 3 just came up in this thread...

http://www.mathhelpforum.com/math-he...ion-proof.html

SkyWatcher · #7 $Old$ June 7th, 2007, 10:15 AM

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

SkyWatcher · #8 $Old$ June 7th, 2007, 10:41 AM

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

SkyWatcher · #9 $Old$ June 8th, 2007, 07:16 AM

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

ThePerfectHacker · #10 $Old$ June 10th, 2007, 09:25 PM

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.

Pterid · #11 $Old$ June 11th, 2007, 11:32 AM

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?

ThePerfectHacker · #12 $Old$ June 11th, 2007, 12:40 PM

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

SkyWatcher · #13 $Old$ June 11th, 2007, 02:41 PM

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

SkyWatcher · #14 $Old$ June 11th, 2007, 02:55 PM

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)

))

Pterid · #15 $Old$ June 11th, 2007, 03:24 PM

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

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.