**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]**