Solutions to the 2000 Putnam exam. First come the solutions I came up with on my own on test day; you will see A6 and B6 are undone. Following are some additions received in email, beginning with solutions to A6 and B6 sent by Robin Chapman, followed by some of the nice alternative solutions to various problems snagged as they drifted past me in cyberspace. dave rusin@math.niu.edu 2000/12/03 ============================================================================== A1. This is the standard comparison of L^p norms for different p. Let B = Sum(x_j)^2 and as given, A = Sum |x_j|. Then with no other information except the positivity of all x_j, we can only conclude 0 < B < A^2 that is, all such values B can be attained. Positivity alone clearly gives B < ( Sum(x_j) )^2 = A^2 and B > 0. In order to show each such B can in fact be attained, we may use geometric series: take x_j = a r^j and compute that the respective sums are A and B when A = a/(1-r) and B = a^2/(1-r^2), which comes to the conditions r = (A^2-B)/(A^2+B), a=2AB/(B+A^2). [This algebraic solution by Richard Blecksmith is prettier than the epsilonics I used!] ============================================================================== A2. It's easy to find two consecutive numbers expressible as a sum of two squares: N^2+0^2 and N^2+1^2. To complete the set it is only necessary to show that for enough values of N we also have N^2-1 expressible as a sum of two squares. But that's (N-1)(N+1) and it's well known that products of sum-of-two-squares numbers are again of this type, so we need only find examples of pairs of these numbers separated by 2. One possibility is (1^2+1^2)(k^2+0^2) and (1^2+1^2)(k^2+1^2). In symbols, our selection is then n = 4k^4+ 4k^2, and a suitable set of presentations is n = (2k^2)^2 + (2k)^2 n+1 = (2k^2+1)^2 + 0^2 n+2 = (2k^2+1)^2 + 1^2 Note: one can come close with a non-constructive approach too: if it were NOT true that infinitely many such triples exist, then for every n at least one of 4n, 4n+1, and 4n+2 would be not a sum-of-two-squares number, making the proportion of sums-of-two-squares bounded by about 1/2, whereas these numbers are fairly common. But that argument is not quite strong enough, at least not without embellishment: the correct proportion of numbers less than N which are sums of two squares is about .8/sqrt(ln(N)), which is already less than 1/2 around n=10. ============================================================================== A3. View the octagon, the square, and the rectangle each as the union of several triangles joining two vertices and the circle's center. (We'll skip the ASCII-art, but a picture here is helpful.) If the radius of the circle is r and the central angle is theta, then the area of the triangle is r^2 sin(theta) /2 . If we label the central angles from P1 to P2, P2 to P3, etc. as alpha, beta, gamma, and delta, then by symmetry the next four angles are again alpha, beta, gamma, and delta. Thus the area of the octagon is r^2 (sin(alpha) + sin(beta) + sin(gamma) + sin(delta) ) In the same way, the area of the rectangle will be r^2 ( sin(beta + gamma) + sin(delta +alpha) ) and the area of the square will be r^2 (sin(alpha + beta) + sin(gamma + delta) ), except that it is clear that we have a square precisely when alpha + beta = pi/2 and gamma + delta = pi/2. The given area of the square then shows 5 = 2 r^2. Eliminating beta, delta, and r, we find the area of the octagon to be (5/2) ( sin(alpha) + cos(alpha) + sin(gamma) + cos(gamma) ) = (5/2) ( sqrt(2) ) ( sin( alpha + pi/4 ) + sin( gamma + pi/4 ) ) and of the rectangle to be (5/2) ( sin(pi/2 - alpha + gamma) + sin(pi/2 - gamma + alpha) ) = 5 cos(alpha - gamma) Therefore, the imposition of a particular area (4) for the rectangle is tantamount to an equation alpha - gamma = constant (namely arccos(4/5) for us). Now treat this as a Lagrange Multipler problem: We must maximize (5/sqrt(2)) ( sin( alpha + pi/4 ) + sin( gamma + pi/4 ) ) subject to the constraint alpha - gamma = constant We discover that the maximum occurs when cos( alpha + pi/4 ) = - cos( gamma + pi/4 ) which can only happen when ( alpha + pi/4 ) + ( gamma + pi/4 ) = pi i.e. alpha = pi/2 - gamma = delta. In short, the rectangle must be symmetrically placed around the square. To determine the actual area of the octagon, substitute alpha = pi/2 - gamma in alpha - gamma = arccos(4/5) to see 4/5 = sin(2 gamma), so that cos(2 gamma) = 3/5 and cos(gamma) = 2/sqrt(5), sin(gamma) = 1/sqrt(5). For alpha = pi/2 - gamma the trig values are of course reverse. Thus the area of the octagon is (5/2) ( sin(alpha) + cos(alpha) + sin(gamma) + cos(gamma) ) = (5/2) ( 2*(2/sqrt(5)) + 2*(1/sqrt(5)) ) = 3 sqrt(5). ============================================================================== A4. From sin(x) sin(x^2) = (1/2)( cos(x^2-x) - cos(x^2+x) ) we convert the integral over [0,B] into half the difference of two integrals. Using the substitutions u = x - 1/2 and u = x + 1/2 respectively, these _both_ become integrals of cos(u^2 - 1/4), the first over the interval [ -1/2, B - 1/2 ] and the second over the interval [ + 1/2 , B + 1/2 ]. Subtracting, we may cancel the common parts of these intervals and write our original integral as (1/2) \int_[-1/2, 1/2] cos(u^2 - 1/4) du - (1/2) \int_[B-1/2, B+1/2] cos(u^2 - 1/4) du The first half is just some constant (OK, I cheated and found out it's 0.49...) so we need only investigate the behaviour of the other integral as B -> oo. Viewing the integrand as (1/u)*( u cos(u^2 - 1/4) ), we apply integration by parts to obtain (1/u)*(1/2)*sin(u^2 - 1/4) + (1/2) \int sin(u^2 - 1/4) / u^2 du for the antiderivative, and thus the definite integral is sin(B^2+B) / (2B+1) - sin(B^2-B) / (2B-1) +(1/2) \int_[B-1/2, B+1/2] sin(u^2 - 1/4) / u^2 du Now simply observe everywhere that | sin(theta) | <= 1, so that the magnitude of the above is bounded by 1 / (2B+1) + 1 / (2B-1) + (1/2) \int_[B-1/2, B+1/2] 1/u^2 du which is roughly 1/B and clearly drops to zero as B -> oo. ============================================================================== A5. We are given three points in the plane. Let D be the largest distance between any pair. If we view these points as vertices of a triangle, then we may view r as the radius of the circumcircle of a triangle. If the lengths of the sides are a,b, and c, and the area is A, then the circumradius is given by r = abc/(4A). Since D = max(a,b,c), we have r < D^3/4A, whence D > (4A r)^(1/3) On the other hand, the area of the triangle may be determined from the coordinates of its vertices; it's half the area of a certain parallelogram, which is in turn computed by a determinant, showing that the area of such a triangle must be at least 1/2. This gives D > (2 r)^(1/3), a slightly stronger result than was asked for. ============================================================================== [INCOMPLETE] A6. The problem begins only with f and then computes the a_n, but for our purposes we may treat both f and the a_n as given. In that case, it's actually better to ignore f for a while and study the a_n. So we suppose given a set of integers a_0, a_1, ..., a_(m-1), and we consider all polynomials f which might carry each a_n to a_(n+1) (cyclically). There is surely at least one polynomial L which does this, and it is unique among such polynomials of degree less than m, and it has rational coefficients. This is the Lagrange Interpolation polynomial, which we may describe in a number of ways. All the other polynomials with the same images of these a_n differ from L by a multiple of Q = Prod( x - a_n ). Thus we must have an equation of the form f = L + P Q for some rational polynomial P. In view of the degrees of the polynomials, it is clear that L is exactly the remainder in the division algorithm performed when dividing f by Q. In particular, since Q is monic and integral, it is clear that if f is integral, so is L. So we conclude: if there is an integral polynomial permuting these points, then the Lagrange polynomial is another example of such; conversely, if the Lagrange polynomial is not integral, there can be no such f. (For illustration consider a putative example in which there is an f with f(0)=1, f(1)=2, f(2)=4, and f(4)=0. We compute that L(x) = (-11/24) x^3 + (15/8) x^2 - (5/12) x + 1 and deduce that f(x) = L(x) + P(x) ( x(x-1)(x-2)(x-4) ) for some P, which is impossible for integral f.) So our task is to show that the Lagrange Interpolating polynomial can never have integral coefficients when there are more than two points a_n. Our proof at this point is incomplete. We can suggest an outline, however. Writing L(x) = Sum( c_n x^n , n < m ), we may treat the c_n as unknowns determined by the conditions L(a_n)=a_(n+1). In matrix form, the equation to be solved has the form M v = w, where v=[ c0, c1, ..., c_(m-1) ]' is the vector of unknown coefficients, w=[ a1, a2, ..., a_(m-1), a0]' is the vector of targets, and M has a particular well-known form: M_{i,j} = ( a_{i-1} )^ (j-1). This is known as a "vandermonde" matrix, and it is known that is determinant is D = Prod(a_j - a_i), the product taken over all pairs with 0 <= i < j < m. In particular, the product is nonzero, it is an integer, it provides an upper bound on the denominators of the c_n, and, when m > 2, it must be larger than 1. (Given three distinct integers, there is a pair with difference larger than 1 ...) So in order for L to be an integer polynomial, it is necessary and sufficient that D divide all the entries of the matrix adj(M) w . Sadly, we have run out of tricks to determine when that can occur... ============================================================================== ============================================================================== B1. For each vector v=[a,b,c] in GF(2)^3, let S_v be the set of indices j for which a_j = a mod 2, b_j=b mod 2, and c_j=c mod 2. We are given that S_[0,0,0] is empty. The other seven subsets S_v have cardinalities which sum to N. Now, we are asked to show that there is a vector v = [r,s,t] for which v' w = 1 for some vectors w with large enough sets S_w. For each vector v we may check to see whether this v is the one we seek; it is as long as the cardinalities of the four sets S_w add up to at least 4N/7, where w ranges over the vectors with v' w = 1. But it is clear that _some_ v must work. If not, then for each of the seven candidates v we would have an inequality of the form |S_(w_1)| + |S_(w_2)| + |S_(w_3)| + |S_(w_4)| < 4N/7 Summing all seven inequalities, and noting that each vector w appears in four of the left sides, gives 4 Sum( |S_w| ) < 4N, which is nonsense since the |S_w| sum to N. ============================================================================== B2. We need only evaluate the rational number p-adically for all primes p, that is, we check to see how many times each prime p divides the numerator (n choose m) and make sure it exceeds the number of times p divides the denominator n/gcd(n,m). Since we know (n choose m) is an integer, there is no difficulty unless p divides n. Write n = p^a n' and m = p^b m' where n' and m' are not divisible by p. Then the denominator is p^max(0,a-b) n'/gcd(n', m'), and we need only ensure that when a > b, p^(a-b) divides (n choose m). But in fact it is easy to describe the number of times a prime p divides a binomial coefficient: write n-m and m in their base-p expansions, and add (to get n in its base-p expansion); the number of times p divides the binomial coefficient is the number of "carries". But if a > b, then the base-p expansions of n and m have, respectively, a and b zeros at the right, meaning that n-m has b zeros at the right, and the next (b-a) 'digits' are found by subtracting the corresponding digit of m from (p-1). When adding back together, we get a carry in each of these a-b positions. So indeed p^(a-b) divides (n choose m) too. ============================================================================== B3. WARNING: PROBLEM STATEMENT UNCLEAR! It _appears_ that we are viewing this as a function defined on R/Z (the circle). Obviously as a function defined on the real line, this f is periodic, and has, at least, a root at every integer, so that N_k is undefined. Rolle's theorem assures us that between any two roots of f^(k) there lies a root of f^(k+1), giving N_(k+1) >= N_k -1 instantly. We gain an additional root by periodicity, that is, if z0 and z1 are the least and greatest roots of f^(k) in [0,1], then f^(k)(z0+1) = 0 implies there is a root z*of f^(k+1) between z1 and z0 + 1. Since z* - 1 is also a root of f^(k+1), it follows we have another root of f^(k+1) in [0,1] whether z* <= 1 or z* > 1. Clearly f^(k)(t) = (2pi)^k Sum( ( a_j j^k ) trig(2pi j t) ) where "trig" will be, depending on k, one of +-sin or +-cos. For sufficiently large k, then, we find that for t = (1/4N)*(integer of appropriate parity), the values of (a_N N^k) trig(2pi N t) dominate the values of the other summands, showing that f^(k) alternates in sign, taking only at least 1/N positive values between 1/N negative values, giving at least 2N roots when k is sufficiently large. [I forgot to explain why the number of roots was in fact no _more_ than 2N, which I had resolved in the same manner as Robin Chapman posted later: ] From: Robin Chapman Newsgroups: sci.math Date: Sun, 03 Dec 2000 18:00:35 GMT These trig functions will all have the form F(z)/z^N on the unit circle where F has degree 2N and so will have <= 2N roots. ============================================================================== B4. Define another function g on the real line by g(t) = f(cos(pi t)). Then g is continuous, g(-t)=g(t), g(t+2) = g(t), and g(2t) = f(cos(2 pi t)) = f( 2 cos(pi t)^2 - 1 ) = 2 cos(pi t) f(cos(pi t)) = 2 cos(pi t) g(t). In particular, g(1)=0, and thus g(2)=0, and thus g(0)=0. Now compare the Fourier expansions of g(2t) and 2 cos(pi t) g(t). If g(t) = Sum( a_n cos( n pi t ) ) then the first has expansion Sum( a_(n/2) cos( n pi t ) ) (meaning that there are nonzero coefficients only in front of the terms with n even) and the second has expansion 2 Sum( a_n cos(pi t) cos( n pi t) ) = Sum( a_n [cos( (n+1) pi t) + cos( (n-1) pi t) ] ) = Sum( [a_(n-1) + a_(n+1)] cos( n pi t) ) So we conclude the Fourier coefficents of g satisfy a_(2k) + a_(2k-2) = 0 a_(2k+1) + a_(2k-1) = a_k These equation start with a0=a1, a2+2a0=0, a1+a3=a1, a2+a4=0, a3+a5=a2, ... By induction we prove that all a_n are integer multiples of a_0, but then the convergence of the Fourier coefficients of a continuous function implies a_0 must be zero, whence all a_n = 0, whence g=0 and f=0. ============================================================================== B5. To each finite set S of integers we associate a polynomial P = Sum( x^a, a in S ) in GF(2) [x]; obviously we could recover the set S from the polynomial, too. Now, the coefficient of x^a in (1+x) P is nonzero precisely when exactly one of x^a or x^(a-1) has a nonzero coefficient in P. Therefore, the sequence of polynomials corresponding to our sets S_n satisfies the recurrence P_(n+1) = (1 + x ) P_n By induction, then, P_n = ( 1 + x )^n P_0. But when n is a power of 2, (1 + x)^n = (1 + x^n ), and as long as n is larger than the degree of P_0, it follows that there is no cancellation in the expression ( P_0 ) + ( x^n P_0 ), that is, the elements of S_n will be the elements of S_0, together with the translates a+n of all the elements a of S_0. ============================================================================== [INCOMPLETE] B6. As in an earlier problem, we may associate the points of B to vectors in GF(2)^n, using a vector v as a label for the point [ (-1)^v_0, (-1)^v_1, ... (-1)^v_n ]. The distance between the points corresponding to vectors v and w is then sqrt(4*d(v,w)) where the distance between two vectors is the number of entries at which they disagree. So we need only show that, given any set of (2/n)*2^n of the vectors in GF(2)^n, we may find three of them u,v,w with the property that d(u,v) = d(v,w) = d(u,w). The distances must be even, since we discover from a Venn diagram that the number of entries in which u, v, and w agree will be n - (3/2) d(u,v). In other words, an equilateral triangle must be formed from vectors v using containing only an even number of 1's, or only an odd number of 1's. One of these two families -- without loss of generality, let us assume it's the evens -- exceeds 2^n / n vectors. We must show there is an equilateral triangle among these. Hm. ============================================================================== Robin Chapman polished off the remaining two: ============================================================================== From: Robin Chapman To: rusin@vesuvius.math.niu.edu Date: Sun, 03 Dec 2000 10:46:56 GMT > Problem B6 Let X be the set of all 2^n points with coordinates +-1. Define the (Hamming) distance of two points P and Q in X by d(P,Q) = # of positions in which P and Q differ. For P in X let A_P = {Q in X: d(P,Q) = 1}. The points in A_P are equidistant, so if any A_P contains three points in B we are done. The A_P each contain n points, and they cover X evenly so the average number of points in each A_P intersect B is (n/2^n)|B| > 2, so some A_P intersect B has at least three points. More formally count the pairs (P,Q) where P in X, Q in B and d(P,Q) = 1. There are n P for each Q, and so there are n|B| such pairs. On the other hand there are |A_P intersect B| pairs statring with P and so sum_P |A_P intersect B| = n|B| > 2^{n+1} and so some |A_P intersect B| >= 3. ============================================================================== From: Robin Chapman To: rusin@vesuvius.math.niu.edu Date: Sun, 03 Dec 2000 14:29:04 GMT > Problem A6 Suppose that m >= 3 is the least m > 0 with a_m = 0. Since f(0) = a_1, then the sequence (a_j) is identically zero modulo a_1, that is a_1 | a_j for all j. Suppose first that m is a prime. For each k with 0 < k < m, consider the k-fold iterate f^k of f. Then f^k(0) = a_k and by the above argument a_k | a_{jk} for each j. There is some j with jk = 1 (mod m) and so a_{jk} = a_1. Hence a_1 | a_k | a_1 and a_k = +- a_1 for all such k. Since the values a_0 = 0, a_1, ..., a_{m-1} are distinct then we must have m = 3 and a_2 = -a_1. In this case, as f(-a_1) = 0 then f(X) = (X + a_1)h(X) where h(X) has integer coefficients. Hence -a_1 = f(a_1) = 2a_1 h(a_1) and so 2a_1 | (-a_1) which is impossible as a_1 is nonzero. Now consider the case m = 4. As before a_1 | a_2 and a_1 | a_3. Conisdering f^3 shows that a_3 | a_1 and so a_3 = -a_1. Also f(X) = (X + a_1)h(X) shows that a_2 = 2a_1 h(a_1) so that 2a_1 | a_2. But also f(X) = a_1 + Xg(X) so that -a_1 = f(a_2) = a_1 + a_2 g(a_2) and so a_2 | 2a_1. Hence a_2 = +- a_1. Suppose that a_2 = 2a_1. Then -a_1 = f(a_2) = 3a_1 h(a_2) which is impossible. Hence a_2 = -2a_1. But applying the same argument to f^3 gives a_2 = -2a_3 = 2a_1. This is impossible. In general m >= 3 has a factor q = 4 or q an odd prime. Replacing f by f^{m/q} shows that this case is impossible too. ============================================================================== Following are additional responses from other people. --djr Oddity: it's mostly the even-numbered problems! A2(3) A4(5) A6(2) B2(3) B4(2) B6(1), and only A3(2) is odd ============================================================================== From: "Brian R. Hunt" Date: Sun, 3 Dec 2000 12:26:36 -0500 (EST) Newsgroups: sci.math [A4:] Rewrite the integrand as (sin x/(2x)) 2x sin x^2 and integrate by parts. You get 3 terms, 2 of which converge as B -> infinity, while the other is the integral of (cos x/(2x)) cos x^2. Integrate by parts again and everything converges (the integrands decay like 1/x^2 or faster). If I'm not mistaken, this method could be used to show convergence with x^2 replaced by any power of x bigger than 1. [A6:] The basic idea is that if a_2 is nonzero, then one can show that a_m = 0 implies a_{m-1} = -a_1, which implies a_{m-2} = -2a_1, a_{m-3} = -3a_1, etc. Here are a couple proofs, I'm afraid that the short direct proof I wrote will be unreadable so I wrote a longer but more intuitive indirect proof. INDIRECT PROOF: Assume a_m = 0 but a_1 is nonzero. Notice that a_{m+1} = a_1 because a_m = a_0. Since f(0) = a_1, the constant term of f is a_1, and by induction all a_n are multiples of a_1. Also x divides f(x) - a_1 for all x, so if a_m = 0 then a_{m-1} divides -a_1. Thus a_{m-1} is either a_1 (in which case a_2 = 0) or -a_1. In the latter case we will show by induction on k that a_{m-k} = -ka_1 for all k >= 0, which leads to a contradiction when k = m. By our assumptions, a_{m-k} = -ka_1 for k = -1, 0, 1. For k >= 1 assume a_{m-j} = -ja_1 for j = k, k-1, k-2. Then f(a_{m-k}) = a_{m-k+1} becomes f(-ka_1) = -(k-1)a_1, so x + ka_1 is a factor of f(x) + (k-1)a_1. With x = a_{m-k-1}, this says that a_{m-k-1} + ka_1 divides a_{m-k} + (k-1)a_1 = -a_1. Thus a_{m-k-1} = -(k+1)a_1 or -(k-1)a_1. In the latter case, a_{m-k-1} = a_{m-k+1}, which can't be true because a_{m-k} = -ka_1 is not equal to a_{m-k+2} = -(k-2)a_1. Therefore a_{m-k-1} = -(k+1)a_1, completing the induction. DIRECT BUT MORE CRYPTIC PROOF: Assume a_m = 0 but a_1 is nonzero. Notice that a_{m+1} = a_1 because a_m = a_0. Since f(0) = a_1, the constant term of f is a_1, and by induction all a_n are multiples of a_1. Let k be the smallest positive integer for which a_{m-k} does not equal -ka_1, and notice that they are equal when k = -1, 0. Then f(a_{m-k+1}) = a_{m-k+2} becomes f(-(k-1)a_1) = -(k-2)a_1, so x + (k-1)a_1 is a factor of f(x) + (k-2)a_1. With x = a_{m-k}, this says that a_{m-k} + (k-1)a_1 divides a_{m-k+1} + (k-2)a_1 = -a_1. By the definition of k, a_{m-k} cannot equal -ka_1, so it must equal -(k-2)a_1 = a_{m-k+2}. It follows that a_{m+2} = a_m = 0, and hence a_2 = f(f(0)) = 0. [B2:] Since lcm(m,n) = mn/(gcd(m,n)), this is equivalent to proving that lcm(m,n) divides k = binomial(n,m)m, which is true if both m and n divide k. Clearly m divides k, while since k = binomial(n-1,m-1)n, so does n. ============================================================================== Date: Sun, 03 Dec 2000 14:05:41 -0400 From: Yin Chen To: rusin@math.niu.edu [A4:] We only need to prove \lim_{B \to \infty} \int_[1, B] sin (x) sin (x^2) dx converges. Let u = x^2, then we have \int_[1, C] sin (u) sin (\sqrt u)/{2 \sqrt u)} du = (integral by parts) I_1 - (1/2) \int_[1,C] (- cos (u) \frac{sin (\sqrt u) }{2u} du +I_2 = I_1 + I_2 + I_3 - (1/4) \int_[1, C] sin (u) \frac{sin (\sqrt u) (\sqrt u)/2 - sin (u)}{2} dx =I_1 + I_2 + I_3 + I_4. Every I_j converges, so does the improper integral. [B4:] f(2x^2-1)=2xf(x). It easy to see f is an odd function. So f(0) =0. Let x = cos (u), then f(cos 2u) = 2 cos (u) f (cos u), or f(cos u) = 2 cos (u/2) f (cos u/2) = sin(u)/sin(u/2) f(cos u/2) =... = sin(u)/sin(u/{2^n}) f( cos u/{2^n}). (**) Let x = sin(u), then f(-cos 2u) = 2 sin(u)f(sin u). f is odd, so 2 cos(u) f(cos u) = - 2 sin(u) f(sin u). If cos(u) is not 0, then f(cos u) = - f(sin u) sin(u)/cos(u). Using this to (**) implies that f( cos u) = - sin(u)/cos(u/{2^n}) f(sin u/{2^n}) --> 0 as n --> \infty. ===> f(x) =0 for x \in (-1, 1). f(-1)=f(1)=0 can be easily obtained. ============================================================================== From cjr2000@telia.com Sun Dec 3 09:39:50 CST 2000 Newsgroups: sci.math Date: Sun, 03 Dec 2000 12:33:29 GMT [A2:] Positive integers makes this slighly more interesting. If we include 0 take c^2,c^2+1,c^2+1=(c-1)^2+2c+1 which works if 2c +1 is square. For positive integers, take n=a^2+b^2=c^2, n+1=c^2+1, n+2=c^2+2=(c-1)^2+2c+1, so again c=2d^2+2d works if it can be a member of infinitely many pythagorean triples. So for example 4(x^2+y^2)=2d^2+2d gives x^2+y^2=T(d), but for triangular numbers T(m-1)^2+T(m)^2=T(m^2). So n=(4T(k^2))^2 works. To get more solutions, we could also simply take 2x^2=x^2+x^2, so that 2x^2+2=(x-1)^2+(x+1)^2 and 2x^2+1=(x-y)^2+(x+y-1)^2 gives 2y^2-2y-2x=0, so that 2(y^2-y)^2 works too. ============================================================================== From: FGD Newsgroups: sci.math Date: Sun, 03 Dec 2000 16:10:19 GMT [A2:] The easiest solution must be: There are infinitely many x such that x^2-1 is a sum of two squares. Indeed, 3^2-1 = 2^2+2^2 and if x^2 - 1 = a^2 + b^2 then x^4 - 1 = (x^2 - 1)(x^2 + 1) = (a^2 + b^2)(x^2 + 1^2) = (ax - b)^2 + (a + bx)^2 So the sequence of n = 3^{2^k}-1, n+1 = 3^{2^k}, n+2 = 3^{2^k}+1 witnesses the desired fact. ============================================================================== From: Robin Chapman Newsgroups: sci.math Date: Sun, 03 Dec 2000 18:00:35 GMT [A3:] I did this by noting that beta + gamma = phi = arcsin(4/5). Then beta, gamma and delta are expressible in terms of alpha, and we get area (5/2)[sin alpha + cos alpha - cos(alpha + phi) + sin(alpha + phi)] = (5/2)[(12/5) sin alpha + (6/5)sin(alpha)] = 3[2sin alpha + cos alpha]. The maximum value of 2sin alpha + cos alpha is sqrt(2^2 + 1^2) = sqrt(5) attained fo alpha = arctan 2. [A4:] My approach was to write y = x^2 and integrate by parts twice. A bit messy but perfectly straightforward. [B4:] I didn't use Fourier theory. I found it easier to use G(t) = f(cos t). Then G(t)/sin t = G(2t)/sin(2t) [as long as both make sense]. Let H(t) = G(t)/sin(t) for t not in pi Z. Then H(t) = H(t/2^k) and as H(t + 2pi) = H(t), then H(t) = H(2t) = H(t + 2pi) = H(t + pi). Similarly H(t + pi/2^k) = H(t). Taking t not commensurable with pi, we get H(t + u pi) = H(t) for all dyadic rationals u. By continuity H(t) is constant, but H(-t) = -H(t) so that constant is zero. ============================================================================== From: FGD Newsgroups: sci.math Date: Sun, 03 Dec 2000 16:28:17 GMT [B2:] Dave's proof relies on a theorem of Kummer and p-adic valuations of binomial coefficients... Here's a simpler appraoch: Note that (*) C(n,m)/n = C(n-1,m-1)/m and we are given n >= m >= 1. So C(n,m) and C(n-1,m-1) are both integers. Whatever the least positive denominator of the fraction (*) is, it must divide both m and n. Therefore gcd(m,n)C(n,m)/n must be an integer. ============================================================================== Date: Sun, 3 Dec 2000 15:02:08 -0500 (EST) From: Matthew Steven Fisher To: rusin@vesuvius.math.niu.edu [B2:] ** This is not my proof, but is a teammate's of mine ** By noting gcd(m,n) = a*m + b*n, we see gcd(m,n)/n * C(n,m) = (a*m / n) * C(n,m) + b * C(n,m) = a*C(n-1,m-1) + b * C(n,m) ============================================================================== Date: Sun, 03 Dec 2000 14:32:49 -0500 From: Abhinav Kumar Newsgroups: sci.math [A2:] Here's a solution I got from Richard Stanley : if n satisfies the proposition then n(n+2) does too! i.e if n = k^2, n+2 = l^2 then n(n+2) = (kl)^2 n(n+2) + 1 = (n+1)^2 n(n+2)+2 = (n+1)^2 + 1 now start with n = 8 for instance and apply this. ============================================================================== Date: Sun, 3 Dec 2000 20:02:08 -0500 (EST) From: David Savitt To: Kiran Kedlaya , rusin@math.niu.edu [A4:] My solution was horrible: substitute u = x^2, break up into intervals [2n pi, (2n+2) pi], and estimate each of these to be close to (a constant times) cos(sqrt(2n pi))/ n, where by "close" I mean that the sum of the differences converges absolutely. So the whole integral differs by a constant from the integral from 1 to infinity of cos(sqrt(2pi u))/u, so we need to see if this converges. Substituting back x = sqrt(2pi u) gives the integral of sin(x)/x, which coverges by the alternating-sign test. [A6:] Here are two and a half solutions. Mine first, written to Mike Zieve, who had mentioned the problem to me (notice the date on the email!): > Date: Sun, 19 Mar 2000 00:47:36 -0500 (EST) > From: David Savitt > To: Michael Zieve > Subject: Cycles for Z[x] > > Hi Mike, > > Nice problem. Let f(x) \in Z[x] be a polynomial with a cycle of length > > 1. Replace f(x) by f(x+n)-n for suitable n to ensure that the smallest > integer in the cycle is 0. Then f(0)=c > 0. Evidently, iterating f on c > gives a sequence of integers all of which are divisible by c, and all of > which are positive (by choice of 0 as the smallest point in the cycle). > One of these integers must be a root of the polynomial, since the cycle > eventually returns to 0. However, since f(0)=c every integer root of the > polynomial divides c, so the only potential positive root of f which is > diviible by c is c itself. Hence the cycle has length 2. > > -Dave Alternately (here's how I thought about it yesterday), choose k such that | a_{k+1} - a_k | is minimal, and replace f(x) by f(x - a_k) + a_k -- since there may be many possible such choices of k, either choose k for which a_{k+1} > a_k with the smallest value of a_k, or for which a_{k+1} < a_k with the largest value of a_k. In particular, by this choice of k it is impossible that a_k - a_{k-1} = a_{k+1} - a_k. Now a_{m-1} is a root and so divides the constant term of the f(x), and therefore is at least as close to 0=a_0 as is a_1. But |a_1 - a_0| is minimal, hence a_{m-1} = +/- a_1. If the cycle does not have length two, then a_{m-1} = - a_1. But then a_1 - a_0 = a_0 - a_{m-1}, contradiction. Here's Mike Zieve's solution, with some interesting comments -- apparently this problem relates to his doctoral thesis from several years ago: On Thu, 23 Mar 2000, Michael Zieve wrote: > > Date: Thu, 23 Mar 2000 18:14:14 +0100 > From: Michael Zieve > To: dsavitt@MATH.HARVARD.EDU > Subject: Re: Cycles for Z[x] > > Hi Dave, > > my proof uses the same idea, but is phrased a bit differently -- > suppose f(x) in Z[x] has cycle (x_1,x_2,...,x_n), > then since x-y divides f(x)-f(y) in Z[x,y] we have that > x_2 - x_1 divides x_3 - x_2 which divides x_4 - x_3 etc. > Hence all the consecutive differences x_{i+1} - x_i are > associates of one another. If they're all the same, then n=1. > If they're not all the same, then we have > x_{i+1} - x_i = - (x_{i+2} - x_{i+1}) for some i, > so x_i = x_{i+2} and n=2. > > Of course, this proof works if we replace Z by any domain > whose only units are +-1. And if instead we use a domain with > more units, we still get some control on cycle lengths. We can > also use that, if a divides b in Z/nZ, then > each a-th difference x_{a+i} - x_i divides > each b-th difference x_{b+i} - x_i. > (which is especially useful if n is prime) > > The upshot is that one quickly reduces to questions about sets > of units with strange additive relations. There are results > about such sets (Evertse, Vojta, etc.) but the quantitative > bounds in those results are pretty awful. In general, one does > better by passing to the completions at one or two primes, > and getting divisibility information about the cycle lengths > in those situations. (But for the special case of Z, this doesn't > work -- for every prime p, there is a polynomial in Z_p[x] having > a 4-cycle (in Z_p). And we can even do this if we replace Z_p > by its intersection with Q (i.e. if we replace the p-adic > completion with the p-adic localization).) > > Best wishes, > Mike [B6:] The solution I eventually found was the same as Robin Chapman's (i.e., for a vertex, consider the simplex of all vertices a distance 1 away, and show that one of those simplices must have three points of the subset). However, I was sidetracked for a *long* time thinking about this is Ramsey-theoretic ways, which produced lots of much-improved bounds for small n but for which I've given up on coming up with a solution for large n. (Maybe you guys can do better?) Here's the idea. Consider the set B to be the vertices of a complete graph G. Label the edge between vertices v,w with the number of coordinates in which v,w differ. This provides an n-colouring of G, and we want to show that there's a monochromatic triangle. Obviously the size of B isn't big enough to force, a priori, that there be a monochromatic triangle -- for example, when n = 3, |B| might be 6, but it's well known that |B| = 6 only forces a monochromatic triangle when it's 2-coloured, not 3-coloured. However, in our case we know that the colouring has a little more structure, for example one easily sees: (1) Parity -- if a triangle has edges coloured j, k then the colour of the third edge must have the same parity as j + k. (2) Triangle inequality: if a triangle has edges colour j, k then the colour of the third edge must be between | k - j | and min( j + k, 2n - j - k). Observe, by parity, that any monochromatic triangle has all edges coloured with even numbers. Furthermore, notice that parity implies the following structure on G: the vertices B are partitioned into two subsets, B' and B'', such that the complete graphs induced on B' and B'' all have only even-coloured edges, and the edges between B' and B'' are all odd. In particular, we have found a complete subgraph of G with ceil(|B|/2) vertices, all edges even, and we'd like to see that in there must reside a monochromatic triangle. Example 1: if n=3, the only even colour is 2. Hence if ceil(|B|/2)=3, we get a monochromatic triangle of 2's. Therefore, the largest we can make |B| and still avoid having a monochromatic triangle is |B| = 4. Thus if |B| >= 5, there's an equilateral triangle., Example 2: if n=4, in which case the even colours are 2 and 4, I will show that ceil(|B|/2) <= 4 to avoid a monochromatic triangle. Indeed, if take a complete subgraph with N+1 vertices and only even edges, select any one vertex v. That vertex has N edges emanating from it. If there are three edges vw_1, vw_2, vw_3 labelled 2 emanating from it, then either w_i w_j are all labelled 4 (in which case w_1 w_2 w_3 is our triangle) or one of them -- say, w_1 w_2 -- is labelled 2, in which case v w_1 w_2 is our triangle. So only two of the N vertices may be labelled 2. However, only one can be labelled 4, since if two edges from the same vertex are labelled 4 and n=4, then the triangle inequality implies that they're one and the same edge. Hence N <= 3, and so N+1 <= 4, as desired. Thus |B|=9 forces an equilateral triangle. Example 3: let's jump ahead a bit, to n=10. Now there are five even colours, 2, 4, 6, 8, and 10. From the triangle inequality, if two sides of a triangle have length 2, then the third side has length 2 or 4; for sides of length 4, the third must be 2,4,6,8; for 6, 2,4,6,8; for 8, just 2, 4; and 10 is impossible. Take a complete graph on N+1 vertices with all edges even, and satisfying our triangle inequality. Pick one vertex. There are N_2, N_4, N_6, N_8, N_10 edges of colour 2,4,6,8,10 from it. If there is no monochromatic triangle, then: -- N_2 <= 2, as if N_2 = 3 we have three vertices between which the only colours are 2 and 4. If all are 4 we have a triangle among these three, and if there's a 2 then there's a triangle with our original vertex. -- N_4 <= 15. If N_4 >= 16, we'd have a complete graph on 16 vertices, each edge labelled 2,6, or 8 (no 4, because that gives us a triangle) but in a complete 3-coloured graph on 16 vertices there *is* a monochromatic triangle (by Ramsey theory). -- N_6 <= 15, N_8 <= 5, N_10 <= 1, same methods. Hence N+1 <= 2 + 15 + 15 + 5 + 1 + 1 = 39. Thus |B| = 79 forces an equilateral triangle, a large improvement over the problem's bound of ceil(2^11 / 10) = 205. Unfortunately, for larger n, the only bounds I'm aware of for the (n/2)-colouring Ramsey numbers grow like 5/2*n!, which is much bigger than 2^n / n, so I don't see how to make a solution out of this. ============================================================================== From: Ray Newsgroups: sci.math Date: Sun, 03 Dec 2000 15:33:35 -0500 [A3]: Fix the rectangle. The total area is the area of the rectangle plus the areas of the triangles, but the area of each triangle is 1/2 base * height, base is constant, and there's no reason we can't rotate the square to maximums both heights at the same time. So the square must be placed symmetrically around the rectangle. ============================================================================== From: Iliya Bluskov Newsgroups: sci.math Date: Sun, 03 Dec 2000 18:50:56 -0800 [A3:] Can be done by first year calculus: Let x be the angle between P_5P_1 and P_4P_2, x is in [0,arcsin \sqr(1/5)] Let a be the angle between P_4P_8 and P_4P_2, sin a= \sqr(1/5), cos a= \sqr(4/5) (one might draw two diameters parallel to the sides of the rectangle and mark the angles at O). The radius of the circle is \sqr(5/2) Then the area of the octagon, A, is A=2 [A(OP_1P_8)+A(OP_8P_7)+A(OP_2P_1)+A(OP_3P_2)] =5/2[sin (a-x) + sin(pi/2+x-a) + sin(x+a) + sin(pi/2-x-a)] =5/2[sin (a-x) + cos(a-x) + sin(x+a) + cos(a+x)] =5(sin a + cos a) cos x The maximum is at x=0, max A=5(sin a + cos a)= 5[(\sqr(1/5) + \sqr(4/5)]=3\sqr(5). ============================================================================== From: Ayatollah Potassium Newsgroups: sci.math Date: Sun, 03 Dec 2000 22:14:05 -0500 [A4:] This is the integral of sin(x)cos(y) dy dx over the parabolic region 0 < y < x^2. By periodicity we can delete any rectangular sub-region with width or height pi, because the integral over any such rectangle is zero. The remainder are integrals of a function bounded by a constant (namely 1) over small parabolic regions of height = pi and width on the order of 1/sqrt(n) - 1/sqrt(n+1) ~ 1/n^(3/2) for n = 1,2,3,.... and the sum of these converges absolutely. In this argument both sin(x) and sin(x^2) can be replaced by more general expressions. The integral of g(x) sin(F(x) dx will converge if F(x) grows rapidly enough to cause rapid oscillation relative to fluctuations of g(x). ==============================================================================