

Title: Intersection Post by Pietro K.C. on Oct 16^{th}, 2002, 8:16pm 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. upsidedown big U. 

Title: Re: NEW PROBLEM: INTERSECTION Post by Garzahd on Nov 1^{st}, 2002, 4:00pm 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 x^{2}  Ax/B  1 = 0 x = (A/B +/ sqrt(A^{2}/B^{2} + 4))/2 x = (A +/ sqrt(A^{2} + 4B^{2}))/2B which is only rational if A^{2} + 4B^{2} is a square. So let's define a set of rationals M_{1}, such that A/B is in M iff A^{2} + 4B^{2} is not square. Each element of M_{1} has no "ancestor", so it can't be in any f^{(k)}(S) (with k>=1). So then f^{(1)}(S) = SM_{1}. Now: What of the firstgeneration descendants of elements of M_{1}? Numbers like 3/2 that exist in f^{(1)}(S) because their ancestor, a member of M_{1}, 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 M_{2}. So f^{(2)}(S) = S  (M_{1} U M_{2}). 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. 

Title: NRe: NEW PROBLEM: INTERSECTION Post by Pietro K.C. on Nov 2^{nd}, 2002, 9:59am I don't follow. ??? I agree with your results up to Quote:
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 (N_{1}, N_{2}, ...), where N_{1} is obtained from N by removing all even numbers, N_{2} from N_{1} by removing all numbers divisible by 3, and in general N_{i+1} is obtained from N_{i} 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 kth prime  but the number 1 is still in every one of the N_{i}, 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 (N_{1}, N_{2}, ...) where N_{1} is N except the square numbers, N_{2} is N_{1} except the cubes, and in general N_{i+1} is N_{i} except the p_{i+1}th powers, where p_{i+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 p_{k}" are lost. Yet, numbers that are not perfect powers (clearly, an infinite number) are in the intersection of all the N_{i}. Maybe you could rephrase the last part of the argument? 

Title: Re: NEW PROBLEM: INTERSECTION Post by TimMann on Nov 2^{nd}, 2002, 6:09pm 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 = (a^{2}  b^{2})/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 a^{2}, so p can divide the numerator only if it also divides b^{2}. 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 = a^{2}  b^{2} = (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. 

Title: Re: NEW PROBLEM: INTERSECTION Post by Pietro K.C. on Nov 3^{rd}, 2002, 9:57am 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:
hit me hard in the face. "Doh!", thought I, "S is Q  {1, 0, 1}, not R  {1, 0, 1}!" :P 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"? :) 

Title: Re: NEW PROBLEM: INTERSECTION Post by TimMann on Nov 3^{rd}, 2002, 7:08pm Interesting how you got to the answer. My first step involved a similar confusion: I "proved" that f is not welldefined 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). 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 