wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Intersection
        
(Message started by: Pietro K.C. on Oct 16^th, 2002, 8:16pm)

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⁽ⁿ⁾(S) = empty
n = 1

where f⁽ⁿ⁾ 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.

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² - Ax/B - 1 = 0
x = (A/B +/- sqrt(A²/B² + 4))/2
x = (A +/- sqrt(A² + 4B²))/2B
which is only rational if A² + 4B² is a square. So let's define a set of rationals M₁, such that A/B is in M iff A² + 4B² is not square. Each element of M₁ has no "ancestor", so it can't be in any f^(k)(S) (with k>=1).

So then f⁽¹⁾(S) = S-M₁.

Now: What of the first-generation descendants of elements of M₁? Numbers like -3/2 that exist in f⁽¹⁾(S) because their ancestor, a member of M₁, existed in f⁽⁰⁾(S) (in this case, 1/2). They won't be in f⁽²⁾(S) because their ancestor isn't in f⁽¹⁾(S). Call these numbers M₂. So f⁽²⁾(S) = S - (M₁ U M₂). And so on.

So, after each iteration of f⁽ⁿ⁾(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:

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 (N₁, N₂, ...), where N₁ is obtained from N by removing all even numbers, N₂ from N₁ 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 k-th 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₁, N₂, ...) where N₁ is N except the square numbers, N₂ is N₁ 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² - b²)/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², so p can divide the numerator only if it also divides b². 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² - b² = (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⁽ⁿ⁾(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:

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}!" :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⁽ⁿ⁾(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 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).