POLYA018:  (2001 Putnam B-Problems, 12/1/01).

[Putnam 2001:B1] Let n be an even positive integer. Write the numbers 1,2, ..., n^2 in the squares of an n by n grid so that the k-th row, from left to right, is (k-1)n+1, (k-1)n+2, ..., (k-1)n+n. Color the squares of the grid so that half of the squares in each row and in each column are red and the other half are black (a checkereboard coloring is one possibility). Prove that for each such coloring, the sum of the numbers on the red squares is equal to the sum of the numbers on the black squares.
[Putnam 2001:B2] Find all pairs of real numbers (x,y) satisfying the system of equations
1/x + 1/(2y) = (x^2+3y^2)(3x^2+y^2), 1/x - 1/(2y) = 2(y^4-x^4).
[Putnam 2001:B3] For any positive integer n, let <n> denote the closest integer to sqrt n. Evaluate
sum((2^<n>+2^-<n>)/2^n, n=1,2, ..., infty).
[Putnam 2001:B4] Let S denote the set of rational numbers different from -1, 0, and 1. Define f:S -> S by f(x) = x - 1/x. Prove or disprove that
Intersection(f^(n)(S), n=1,2,..., infty) = empty set, where f^(n) = f.f....f n times [n-fold composite] and f(S) is the set of values f(s) for s in S..
[Putnam 2001:B5] Let a and b be real numbers in the interval (0, 1/2) and let g be a continuous real valued function such that g(g(x)) = ag(x) + bx for all real x. Prove that g(x) = cx for some constant c. (Apology for an earlier typo which has been corrected. In truncating the lines, I had inadvertently cut out x from bx. This note will stay here for a few days).
[Putnam 2001:B6]  Assume that (a_n) is an increasing sequence of positive real numbers such that lim (a_n)/n = 0. Must there exist infinitely many positive integers n such that a_(n-i) + a_(n+i) < 2a_n for i = 1,2, ..., n-1?

*************************************************************************************************************
Discussion. [Problem B1] Let n be an even positive integer. Write the numbers 1,2, ..., n^2 in the squares of an n by n grid so that the k-th row, from left to right, is (k-1)n+1, (k-1)n+2, ..., (k-1)n+n. Color the squares of the grid so that half of the squares in each row and in each column are red and the other half are black (a checkereboard coloring is one possibility). Prove that for each such coloring, the sum of the numbers on the red squares is equal to the sum of the numbers on the black squares.

[SCL]: There is a theorem known to undergraduates who have taken a graph theory course: Hall's matching theorem, and the version that is useful here is an exercise one can prove from it called Birkhoff's theorem.
If A is a (0,1)-matrix with row sums k and column sums k, then A is the sum of k permutation matrices. Problem B-1 is now trivial: Any permutation hits each row once and each column once. The sum of the entries is a sum of integers of the form a+bn, where a ranges over the numbers 0,1,...,n-1 and b ranges over the numbers 1,2,..,n, with each number in each of the two ranges occurring exactly once. The sum can thus be re-arranged to give the sum 1+(n+2)+(2n+3)+...+n^2.
In other words, the problem can be generalized as follows. an n by n matrix with the entries in the order specified by the problem is given. The squares are coloured so that exactly k squares in each row are white and n-k are black, and exactly k squares in each column are white and n-k are black. Then, the sum of the entries in the white squares is k*(1+(n+2)+(2n+3)+...+n^2) no matter what the colouring is.

*************************************************************************************************
[Problem B2] Find all pairs of real numbers (x,y) satisfying the system of equations
1/x + 1/(2y) = (x^2+3y^2)(3x^2+y^2)
1/x - 1/(2y) = 2(y^4-x^4).

[PY]: Adding and subtracting the two equations, we obtain 2/x = x^4+10x^2y^2+5y^4 and 1/y = 5x^4+10x^2y^2+y^4. From these,
2=x^5+10x^3y^2+5xy^4 and 1 = 5x^4y+10x^2y^3+y^5. Adding and subtracting these two, we have 3 = (x+y)^5 and 1 = (x-y)^5. Since x and y are real, the only possibilities are x+y = 3^(1/5) and x-y=1. Hence, x = (3^(1/5)+1)/2 and y=(3^(1/5)-1)/2.

*************************************************************************************************
[Problem B3] For any positive integer n, let <n> denote the closest integer to sqrt n. Evaluate sum((2^<n>+2^-<n>)/2^n, n=1,2, ..., infty).

[FvL]:  Numbers p = m(m-1)+1, ..., m(m+1) have <p>=m, there are 2m of them.
The partial sum from p = m(m-1)+1 to m(m+1) of (2^m+2^(-m))/2^p is hence equal to
  1/(2^(m(m-1))) * (1/2 + 1/4 + ...+ 1/2^(2m)) * (2^m + 2^(-m))
= 1/(2^(m(m-1))) * ( 1 - 1/2^(2m)) * (2^(2m) - 1)/2^m
= 2^(4m) - 1 /(2^(m^2 + 2m))
= 1/(2^(m^2-2m)) - 1/(2^(m^2+2m)) [1]
So the sum we look for is equal to summing [1] for m=1 to \infty. Clearly the left fraction for m=q is equal to the right fraction for m=q+2, while the fractions also converge to 0 when m approaches \infty, so that it is easy to see that we only have to evaluate the left fraction of [1] for m=1 and m=2, and have to add these. That gives that the sum we are looking for is equal to 1/2^(-1) + 1/2^0 = 2 + 1 = 3.

[JPE]: We have <n> = k iff k^2-k+1<= n <= k^2+k. As sum((2^k + 2^(-k))/2^n, n = k^2-k+1..k^2+k) = u_k = 1/2^(k^2-2k) - 1/2^(k^2 + 2k), the required sum is sum(u_k, k=1..inf) = 3  (except two of then, the terms of this sum disappear two by two).

*************************************************************************************************
[Problem B4] Let S denote the set of rational numbers different from -1, 0, and 1. Define f:S -> S by f(x) = x - 1/x. Prove or disprove that
Intersection(f^(n)(S), n=1,2,..., infty) = empty set, where f^(n) = f.f....f n times [n-fold composite] and f(S) is the set of values f(s) for s in S.

[TS]: If a rational number x = m/n, in reduced form (n a positive integer), let p(x) = # of prime factors of n. (So p(x) = 0 if and only if x is an integer; otherwise p(x)>0). Now let x = m/n, reduced form, then f(x) = x - 1/x = (m^2-n^2)/mn and it is easy to see that m^2-n^2 and mn cannot have common factors so that (depending on whether m is positive or not), either (m^2-n^2)/mn or (n^2-m^2)/(-m)n is the reduced form of f(x). Since two squares cannot differ by 1, we see first that f(S) does not contain any number of the form 1/n, n an integer. Moreover, since 1 and -1 are not in S, we also see that p(x)>0 for all x in f(S) (the denominator is nm and we can't have both n,m either 1 or -1). That is p(x) >= 1 for x in f(S). Now one sees by induction that if x is in f^{(n)}(S) (f applied n times to S), then p(x) is greater than or equal n, which shows that the intersection of all these sets must be empty (or consist of rational numbers whose reduced form has a denominator which is a product of an infinity of primes).

*************************************************************************************************
[Problem B5] Let a and b be real numbers in the interval (0, 1/2) and let g be a continuous real valued function such that g(g(x)) = ag(x) + bx for all real x. Prove that g(x) = cx for some constant c.

[PY]: Apology for an earlier typo which has been corrected above. In truncating the lines, I had inadvertently cut out x from bx. This note will stay here for a few days.

[SCL]: Let s_0=x. Define s_{n+1}=g(s_n). Then, s_{n+2}=g(g(s_n))=ag(s_n)+bs_n=as_{n+1}+bs_n.
Thus, we have a linear recurrence: s_{n+2}=as_{n+1}+bs_n.
The characteristic equation for this recurrence is s^2-as-b=0, with roots s = a/2 \pm \sqrt{a^2/4+b}. Now, since a,b are in the interval (0,1/2), a^2/4 < 1/16, a^2/4+b<9/16, s< 1. Also, \abs(s)< 1. Suppose that t,u are the two roots of the characteristic equation: t= a/2 + \sqrt{a^2/4+b}, u=a/2 - \sqrt{a^2/4+b}.
Thus, s_n=At^n+Bu^n --> 0 as n-->0.
That is, repeated applications of g bring us towards the origin.
Could find A,B in terms of a,b, x, g(x):
      x=A+B
   g(x)=At+Bu

      B=x-A
   g(x)=At+(x-A)u=xu+A(t-u)=xu+A\sqrt{a^2+4b}.
 If what I have so far is correct, can we show that A=0?

[JPE]:  Following SCL idea, note that 1>t>0>u and t+u = a>0. Putting g_n=g(g(g(....))), T(x) = g(x)-tx; U(x) = g(x)-ux, we have
(1) (t-u) g_n(x) = U(x) t^n -T(x) u^n
More over, as g is clearly injective, we have two possibilities
1)g is decreasing.  Suppose that U(x)<>0 pour some x; for y close to x and n large enough, g_n(x) - g_n(y) and U(x) - U(y) will have the same sign, which is impossible because g_n is decreasing for odd n and increasing for even n. Hence g(x) = ux for all x.
2) g is increasing. Then g(x)=tx for all x (same kind of proof than in 1) using -n instead of n).

Surely 2) is too quick. As g_n(0) -> 0 when n->infi ad g_(n+1)(0) = g(g_n(0)), we get g(0) = 0. Hence, for x>0, g(x)>0, g(g(x))>bx and g(x)->+infi when x->+infi. Same way, g(x)->-infi when x->-infi and g is a bijection from R to R. Now, we have (t-u) g_(-n)(x) = U(x)/t^n - T(x)/u^n. Suppose T(x)<>0 for some x; for y close to x and n large enough g_(-n)(x) - g_(-n)(y) and -(T(x)-T(y))/u^n will have the same sign, which is impossible
because the first sign is constant and the other one is not. Hence g(x)=tx for all x.
 

*************************************************************************************************
[Problem B6] Assume that (a_n) is an increasing sequence of positive real numbers such that lim (a_n)/n = 0. Must there exist infinitely many positive integers n such that a_(n-i) + a_(n+i) < 2a_n for i = 1,2, ..., n-1?

[SCL]: I'm assuming increasing means strictly increasing, otherwise a constant sequence would be a counterexample.
Suppose that there are only a finite number of such n. Then, for some N, n\ge N forces a_{n+1}-a_n \ge a_n-a_{n-1}. But now
a_{n+2}-a_n  =  a_{n+2}-a_{n+1} +a_{n+1}-a_n
                        \ge 2(a_{n+1}-a_n)
 and, by induction, a_{n+m}-a_n \ge m(a_{n+1}-a_n), and
      \lim_{m\to\infty} (a_{m+n})/{m+n)   \ge  \lim_{m\to\infty} (a_n+m(a_{n+1}-a_n))/(m+n)    = a_{n+1}-a_n  \neq 0.

'nuff said?

[SCL]: JPE has pointed out that I misread the question. What I proved would follow from a correct proof of the problem. SO, now the question might be whether or not one could modify my proof to prove the original question.

[JPE]: Let C_n be the property a_(n-i) + a_(n+i) < 2 a_n for i =1,2,...,n-1.
Suppose that C_n is wrong for all n>=N.
For any integer n, put f(n) = a_n - n (a_N - a_(N-1))/N.
Let E be the set of the integers n such as f(n) > 0.
Then E is finite (because a_n/n -> 0) and non empty because f(N) = a_(N-1).
Now, there exists m such as f(n) <= f(m) for n<=m and f(n)<f(m) for n>m (take for m the greatest value of n for which the restriction of f to E is maximal).
As f(m+i)<f(m) and f(m-i)<=f(m), adding, we get that C_m is true; hence m<N.
But a_m>f(m)>=f(N)=a_(N-1); hence m>N -1. Contradiction.

Bibliography.
 
 
 

Return to [Polya Home Page] [Members] [The Problems] [Inventory] [Reserve Area]