Author |
Topic: Intersection (Read 798 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
Intersection
« on: Oct 16th, 2002, 8:16pm » |
 Quote  Modify
|
It's hard coming up with names for every single problem I post!  Another good one from the Putnams follows.
Let S denote the set of rational numbers different from {-1, 0, 1}. Define f:S->S by f(x)=x - 1/x. Prove or disprove that
infinity
INTER f(n)(S) = empty
n = 1
where f(n) denotes f composed with itself n times, and INTER is to be replaced with the usual symbol of set intersection, i.e. upside-down big U.
|
| « Last Edit: Nov 7th, 2002, 8:49am by Pietro K.C. » |
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: NEW PROBLEM: INTERSECTION
« Reply #1 on: Nov 1st, 2002, 4:00pm » |
Quote Modify
|
I actually had this problem on one of the Putnams I took
I got a 12 that year, so there's probably some flaw in this logic that forced them to give me a 0 or 1 on this. Or maybe this got a 9 or 10; stupid Putnam results not telling you what you got wrong.
Let's investigate whether a particular rational A/B can actually be in a set f(k)(S) for k>=1. Then
A/B = x - 1/x
x2 - Ax/B - 1 = 0
x = (A/B +/- sqrt(A2/B2 + 4))/2
x = (A +/- sqrt(A2 + 4B2))/2B
which is only rational if A2 + 4B2 is a square. So let's define a set of rationals M1, such that A/B is in M iff A2 + 4B2 is not square. Each element of M1 has no "ancestor", so it can't be in any f(k)(S) (with k>=1).
So then f(1)(S) = S-M1.
Now: What of the first-generation descendants of elements of M1? Numbers like -3/2 that exist in f(1)(S) because their ancestor, a member of M1, existed in f(0)(S) (in this case, 1/2). They won't be in f(2)(S) because their ancestor isn't in f(1)(S). Call these numbers M2. So f(2)(S) = S - (M1 U M2). And so on.
So, after each iteration of f(n)(S), you're losing infitely many items from the set, so the intersection of infitely many iterations is empty.
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
NRe: NEW PROBLEM: INTERSECTION
« Reply #2 on: Nov 2nd, 2002, 9:59am » |
Quote Modify
|
I don't follow. 
I agree with your results up to
Quote:| So f(2)(S) = S - (M1 U M2) |
|
But then you lost me. It is actually possible that such an intersection is not empty, and even infinite! Let me give two examples. Consider the set N of positive integers, and define the sequence (N1, N2, ...), where N1 is obtained from N by removing all even numbers, N2 from N1 by removing all numbers divisible by 3, and in general Ni+1 is obtained from Ni by removing all numbers divisible by the (i+1)-th prime. In this case as well, you are "losing infinitely many elements" at each step - at the very least, step k removes all powers of the k-th prime - but the number 1 is still in every one of the Ni, and hence in their intersection!
You might conclude that such processes always lead to finite intersections,then. Not so. Consider again the set N of positive integers, and this time define the sequence (N1, N2, ...) where N1 is N except the square numbers, N2 is N1 except the cubes, and in general Ni+1 is Ni except the pi+1-th powers, where pi+1 is the (i+1)-th prime. In this process also, infinitely many elements are being lost at each step - in step k, numbers X with the property "the greatest common divisor of the exponents in the prime factorization of X is pk" are lost. Yet, numbers that are not perfect powers (clearly, an infinite number) are in the intersection of all the Ni.
Maybe you could rephrase the last part of the argument?
|
| « Last Edit: Nov 3rd, 2002, 10:00am by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: INTERSECTION
« Reply #3 on: Nov 2nd, 2002, 6:09pm » |
Quote Modify
|
Here's my solution.
The elements of S are rational, so we can write any element of S as a fraction a/b in lowest terms; that is, with a, b relatively prime integers, b != 0. Since 0, 1, -1 are not in S, we also have that |a| and |b| are not both 1.
Now consider any element of f(S). It can be written as f(a/b) = a/b - b/a = (a2 - b2)/ab. Lemma: This expression is again in lowest terms. Proof: Suppose the expression is not in lowest terms. Then some prime p divides both the denominator and numerator. If p divides ab, then p divides a or p divides b. Suppose p divides a; then p divides a2, so p can divide the numerator only if it also divides b2. But then p divides b as well, contradicting our premise that a/b is in lowest terms. The argument is the same if we suppose p divides b.
For any nonzero integer n, let T(n) be the number of terms in |n|'s prime factorization, with T(1) = 0. Thus T(2) = 1, T(4) = T(2*2) = 2, etc.
For a/b in S, obviously T(b) can have any value >= 0. However, as shown above, if c/d (written in lowest terms) is an element of f(S), then d = ab where a, b are relatively prime and not both 1. So T(d) >= 1.
Also, since c = a2 - b2 = (a + b)(a - b) and b != 0, |c| != 1.
Applying this argument repeatedly, we find that if j/k (written in lowest terms) is an element of f(n)(S), then T(k) >= n.
Thus for any rational number j/k, j/k is not an element of f(T(k)+1)(S). So the intersection given in the problem is empty.
(I got this without looking at the earlier incorrect solution, so I'm not sure how far off that one is. Certainly Pietro is correct in criticizing the last sentence of it. In general one can remove an infinity of elements from an infinite set, and repeat that an infinity of times, yet still have a nonempty set; in fact the set can still be infinite.)
Edit: I forgot to show that |c| != 1 when I first posted this, and I was sloppy about dealing with negative elements of S.
|
| « Last Edit: Nov 2nd, 2002, 11:57pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PROBLEM: INTERSECTION
« Reply #4 on: Nov 3rd, 2002, 9:57am » |
Quote Modify
|
Yep. Very similar to my answer. The funny thing is, at first it took me about two seconds to find a solution to this, and I was left with a feeling I was missing something. And indeed I was!
I reasoned that the function f(x) = x - 1/x was clearly bijective from the set S = R - {-1, 0, 1} onto S (cf. Garzahd's argument, or a number of simpler ones), and hence any number of compositions of f, when applied to S, would still yield S. So the intersection referred to was actually all of S! I found it very odd that there was such disparity between the statement you are asked to prove or disprove and the "truth"!
Then I read Garzahd's post, and the line
Quote:| which is only rational if A2 + 4B2 is a square |
|
hit me hard in the face. "Doh!", thought I, "S is Q - {-1, 0, 1}, not R - {-1, 0, 1}!" 
Then I started trying to prove the intersection was not empty in some other way. Call me hardheaded. One way to prove this would be to find a fixed point of the transformation, i.e. an x in Q such that f(x) = x. Needless to say, that attempt lasted for about half a second. Then I thought, "hey, it would still not be empty if there were x, y in Q such that f(x) = y, f(y) = x!" Because then we would have both x and y in every set f(n)(S). Alas, one of x or y would have to be the square root of 1/2 for this to happen, as a little algebra shows.
Trying it out with a triple of elements (x, y, z such that f(x) = y, f(y) = z, f(z) = x) seemed a bit too complicated, so I caved and started trying to prove it was indeed empty.
The light came when I quit the approach "solve y = f(x) for y in terms of x, and make y rational", and instead just wrote out the general form of f(m/n). Well, how's that for "explaining how you arrived at an answer"?
|
| « Last Edit: Nov 3rd, 2002, 9:59am by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PROBLEM: INTERSECTION
« Reply #5 on: Nov 3rd, 2002, 7:08pm » |
Quote Modify
|
Interesting how you got to the answer. My first step involved a similar confusion: I "proved" that f is not well-defined because there exists x such that f(x) = 1. Then I remembered that x must be rational. D'oh.
After that, writing out f(a/b) was the next thing I happened to try. It was easy from there, although I twice almost forgot to account for the possibility of a or b being equal to 1 (or -1).
|
|
IP Logged |
http://tim-mann.org/
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print