Prev: Set Theory, Anyone?
Next: pentic root
From: Math Help on 5 Dec 2009 10:08
Dear colleagues, dear friends,

As you know William Lowell Putnam Competition takes place in USA and
Canada in 2009 today on Saturday 5 December, right now. It started at
10:00 a.m. GMT-4 in Atlantic zone and will finish at 4:00 p.m. GMT-10
in Hawaii zone. Also some students may take exams on Sunday because of
religious restrictions.

We are going to organize a local competition in our university in
Ukraine by the problems from Putnam Competition 2009 (unofficially
surely) on Sunday 6 December 2009. (The day of Saturday USA and Canada
is the night from Saturday to Sunday in Ukraine.) We would like to
start at 10:00 a.m GMT+2 (3:00 a.m. EST, 0:00 a.m. PST) and finish at
5:00 p.m. GMT+2 (10:00 a.m. EST, 7:00 a.m. PST).

So would you be so kind _NOT TO PUBLISH_ and _NOT TO DISCUSS_ Putnam
problems at least untill that time?

Actually some students in USA and Canada participates on Sunday too.
So maybe it would be better not to discuss a little longer. For
example at mathlinks.ro/ArtOfProblemSolving.com forum such
conversations are officially forbidden until Sunday evening, 8:00 p.m
EST (5:00 p.m. PST).

Thank you for your understanding and cooperation.

Best regards,
Dmytro Mitin,
Assistant Professor, Kyiv Taras Shevchenko National University,
Kyiv, Ukraine.
From: dave.rusin on 6 Dec 2009 09:55
On Dec 5, 10:08 am, Math Help <math...(a)gmail.com> wrote:

> As you know William Lowell Putnam Competition takes place in USA and
> Canada in 2009 today on Saturday 5 December, right now. It started at
> 10:00 a.m. GMT-4 in Atlantic zone and will finish at 4:00 p.m. GMT-10
> in Hawaii zone. Also some students may take exams on Sunday because of
> religious restrictions.
>
> We are going to organize a local competition in our university in
> Ukraine by the problems from Putnam Competition 2009 (unofficially
> surely) on Sunday 6 December 2009. (The day of Saturday USA and Canada
> is the night from Saturday to Sunday in Ukraine.) We would like to
> start at 10:00 a.m GMT+2 (3:00 a.m. EST, 0:00 a.m. PST) and finish at
> 5:00 p.m. GMT+2 (10:00 a.m. EST, 7:00 a.m. PST).
>
> So would you be so kind _NOT TO PUBLISH_ and _NOT TO DISCUSS_ Putnam
> problems at least untill that time?


Here are the problems from the 2009 Putnam exam, held
Saturday Dec 5 2009. I will post the answers I came up with
in a few minutes. I'm missing a couple.


A1. Let f be a real-valued function on the plane such that for
every square ABCD in the plane, f(A)+f(B)+f(C)+f(D) = 0.
Does it follow that f(P) = 0 for all points P in the plane?

A2. Functions f, g, h are differentiable on some open interval
around 0 and satisfy the equations and initial conditions
f' = 2f^2gh + 1/(gh), f(0)=1
g' = fg^2h + 4/(fh), g(0)=1
h' = 3fgh^2 + 1/(fg), h(0)=1
Find an explicit formula for f(x), valid in some open interval
around 0.

A3. Let d_n be the determinant of the n x n matrix whose
entries, from left to right and then from top to bottom, are
cos1, cos2, ..., cos n^2. (For example,
| cos1 cos2 cos3 |
d_3 = | cos4 cos5 cos6 |.
| cos7 cos8 cos9 |
The argument of cos is always in radians, not degrees.)
Evaluate lim_{n\to\infty} d_n .

A4. Let S be a set of rational numbers such that
(a) 0 \in S
(b) if x \in S then x+1 \in S and x-1 \in S; and
(c) if x \in S and x\not\in {0,1}, then 1 / [ x(x-1)] \in S.
Must S contain all rational numbers?

A5. Is there a finite abelian group G such that the product of
the orders of all its elements is 2^2009 ?

A6. Let f : [0,1]^2 -> R be a continuous function on the closed
unit square such that [the partial derivatives] df/dx and df/dy
exist and are continuous on the interior (0,1)^2 . Let
a = \int_0^1 f(0,y) dy
b = \int_0^1 f(1,y) dy
c = \int_0^1 f(x,0) dx
d = \int_0^1 f(x,1) dx

Prove or disprove: There must be a point (x0, y0) in (0,1)^2 such
that df/dx(x0,y0) = b-a and df/dy (x0,y0) = d-c .



B1. Show that every positive rational number can be written as a
quotient of products of factorials of (not necessarily distinct)
primes. For example, 10/9 = (2! 5!)/(3! 3! 3!)

B2. A game involves jumping to the right on the real number line.
If a and b are real numbers and b > a, the cost of jumping
from a to b is b^3 - a b^2. For what real numbers c can one
travel from 0 to 1 in a finite number of jumps with total cost
exactly c ?

B3. Call a subset S of {1,2, ..., n} "mediocre" if it has the
following property: Whenever a and b are elements of S whose
average in an integer, that average is also an element of S .
Let A(n) be the number of mediocre subsets of {1, 2, ..., n}.
[For instance, every subset of {1,2,3} except {1,3} is mediocre,
so A(3) =7.] Find all positive integers n such that
A(n+2) - 2 A(n+1) + A(n) = 1 .

B4. Say that a polynomial with real coefficients in two variables,
x,y, is "balanced" if the average value of the polynomial on each
circle centered at the origin is 0. The balanced polynomials of
degree at most 2009 form a vector space V over R. Find the
dimension of V.

B5. Let f: (1,\infty) -> R be a differentiable function such that

f'(x) = [ x^2 - (f(x))^2]/[ x^2 ( (f(x))^2 + 1 ) ] for all x>1

Prove that lim_{x\to\infty} f(x) = infinity .

B6. Prove that for every positive integer n there is a sequence
of integers a_0, a_1, ..., a_2009 with a_0 = 0 and a_2009 = n
such that each term after a0 is either an earlier term plus 2^k
for some nonnegative integer k, or of the form b mod c for some
earlier positive terms b and c. [Here b mod c denotes the
remainder when b is divided by c, so 0 <= (b mod c ) < c .]

From: dave.rusin on 6 Dec 2009 10:01
Here are my solutions to the 2009 Putnam questions.
I drew a blank on A6. B6 mystifies me -- it doesn't seem
possible!

Seemed like lots of the problems were designed to be
accessible to average-to-good students this year.
I thought the "2009" theme got a little tiresome.

A1: Yes. Fix a square ABCD centered at P. Let Z,Y,X,W
be the midpoints of AB,BC,CD,DA respectively (so that ZYXW is
also a square). Then

4 f(P) = (f(A)+f(Z)+f(P)+f(W)) + (f(Z)+f(B)+f(Y)+f(P))
+ (f(Y)+f(C)+f(X)+f(P)) + (f(X)+f(D)+f(W)+f(P))
- (f(A)+f(B)+f(C)+f(D)) -2(f(Z)+f(Y)+f(X)+f(W)) = 0


A2: Divide the equations by f,g,h respectively to get
f'/f = 2k + 1/k , g'/g = k + 4/k , h'/h = 3k + 1/k
where k(x) = f(x) g(x) h(x). I will replace this set of three
equations with a different set of three linear combinations of them.

If we add these three equations, the result may be expressed as

k' / k = 6 k + 6 / k, k(0)=1.

This is a separable differential equation, with solution
arctan(k) = 6 x + c, so that c = arctan(1) = pi/4. Thus
k(x) = tan(6x+ pi/4) .

A different linear combination of the divided equations (using
multipliers of -11, 1, and 7 respectively) shows
log(g h^7/f^11) ' = 0
so g h^7 / f^11 is constant, and thus (because of the initial
conditions) equal to 1, i.e. g = f^11/h^7. Thus k = f^12/h^6,
so that
f^2 / h = tan(6x+pi/4)^(1/6)
(up to sign, but at x=0 we require f^2/h = 1 ).

Finally subtracting two of the divided equations shows
h'/h - f'/f = k
so log(h/f) is an antiderivative of k and so is of the form
(-1/6) log( | cos(6x+pi/4) | ) + C
meaning that
h/f = | sqrt(2) cos(6x+pi/4) |^(-1/6)
(where I have inserted the necessary constant to have h/f = 1
when x=0).

Multiplying the results from the last two paragraphs I get
f = [ sin(6x+pi/4) / ( sqrt(2) cos^2(6x+pi/4) ) ]^(1/6)

(This is an uglier answer than I expected from a Putnam problem.)


A3: The determinants are all zero for n > 3 since the
first three rows are linearly independent, with multipliers
-1, 2 cos(n), -1 : for every i we have
- cos(i-n) + 2 cos(n) cos(i) - cos(i+n) = 0.


A4: No, for example S might be the set of all rationals
except those of the form n + 2/5 for integers n. This set S
clearly satisfies conditions (a) and (b). If x = a/b is in
lowest terms then so is 1/[x(x-1)] = b^2/[a(a-b)], and in
particular this never has a denominator matching n + 2/5 unless
{a,a-b}={1,5} or {-1,-5}, which would require a/b = -1/4 or 5/4,
in which case 1/[x(x-1)]=16/5, which is indeed already in S.
So (c) is met too.


A5: No. Maybe we could economize by using the special nature
of 2009 right away, but let us examine the general problem.

From the structure theorems for finite abelian groups,
G would have to be of the form
G = (Z/2)^a x(Z/4)^b x(Z/8)^c x(Z/16)^d x(Z/32)^e
x(Z/64)^f x(Z/128)^g x(Z/256)^h
for some natural numbers a,b,c,d,e,f,g,h .

We need not continue the list further: if G had an element of
order 512, its odd powers would give 256 such elements, so that
the product of the orders would exceed (512)^256 = 2^(9 . 256)
which is more than 2^2009.

The number of elements of orders dividing 2,4,8,16, ... are
2^(a+ b+ c+ d+ e+ f+ g+ h)
2^(a+2b+2c+2d+2e+2f+2g+2h)
2^(a+2b+3c+3d+3e+3f+3g+3h)
2^(a+2b+3c+4d+4e+4f+4g+4h)
2^(a+2b+3c+4d+5e+5f+5g+5h)
2^(a+2b+3c+4d+5e+6f+6g+6h)
2^(a+2b+3c+4d+5e+6f+7g+7h)
2^(a+2b+3c+4d+5e+6f+7g+8h)
so, taking successive differences, we obtain a formula for the
product of the orders of all the elements in any such group:

1
x 2^( 2^(a+ b+ c+ d+ e+ f+ g+ h) - 1 )
x 4^( 2^(a+2b+2c+2d+2e+2f+2g+2h) - 2^(a+ b+ c+ d+ e+ f+ g+ h) )
x 8^( 2^(a+2b+3c+3d+3e+3f+3g+3h) - 2^(a+2b+2c+2d+2e+2f+2g+2h) )
x 16^( 2^(a+2b+3c+4d+4e+4f+4g+4h) - 2^(a+2b+3c+3d+3e+3f+3g+3h) )
x 32^( 2^(a+2b+3c+4d+5e+5f+5g+5h) - 2^(a+2b+3c+4d+4e+4f+4g+4h) )
x 64^( 2^(a+2b+3c+4d+5e+6f+6g+6h) - 2^(a+2b+3c+4d+5e+5f+5g+5h) )
x128^( 2^(a+2b+3c+4d+5e+6f+7g+7h) - 2^(a+2b+3c+4d+5e+6f+6g+6h) )
x256^( 2^(a+2b+3c+4d+5e+6f+7g+8h) - 2^(a+2b+3c+4d+5e+6f+7g+7h) )

which is 2 raised to this exponent:

1x( 2^(a+ b+ c+ d+ e+ f+ g+ h) - 1 )
+ 2x( 2^(a+2b+2c+2d+2e+2f+2g+2h) - 2^(a+ b+ c+ d+ e+ f+ g+ h) )
+ 3x( 2^(a+2b+3c+3d+3e+3f+3g+3h) - 2^(a+2b+2c+2d+2e+2f+2g+2h) )
+ 4x( 2^(a+2b+3c+4d+4e+4f+4g+4h) - 2^(a+2b+3c+3d+3e+3f+3g+3h) )
+ 5x( 2^(a+2b+3c+4d+5e+5f+5g+5h) - 2^(a+2b+3c+4d+4e+4f+4g+4h) )
+ 6x( 2^(a+2b+3c+4d+5e+6f+6g+6h) - 2^(a+2b+3c+4d+5e+5f+5g+5h) )
+ 7x( 2^(a+2b+3c+4d+5e+6f+7g+7h) - 2^(a+2b+3c+4d+5e+6f+6g+6h) )
+ 8x( 2^(a+2b+3c+4d+5e+6f+7g+8h) - 2^(a+2b+3c+4d+5e+6f+7g+7h) )

or equivalently,

- 1
- 2^(a+ b+ c+ d+ e+ f+ g+ h)
- 2^(a+2b+2c+2d+2e+2f+2g+2h)
- 2^(a+2b+3c+3d+3e+3f+3g+3h)
- 2^(a+2b+3c+4d+4e+4f+4g+4h)
- 2^(a+2b+3c+4d+5e+5f+5g+5h)
- 2^(a+2b+3c+4d+5e+6f+6g+6h)
- 2^(a+2b+3c+4d+5e+6f+7g+7h)
+ 8 x 2^(a+2b+3c+4d+5e+6f+7g+8h)

So we must solve the diophantine problem of selecting non-negative
integers abcdefgh so that this last expression equals 2009.

But now if we read this equation modulo 2^(a+2b+2c+2d+2e+2f+2g+2h)
we are left with 2010 = - 2^(a+ b+ c+ d+ e+ f+ g+ h).
Accounting for powers of 2 this shows that either
a+b+c+d+e+f+g+h=1 or a+2b+2c+2d+2e+2f+2g+2h = 2.
In either case, only one of our variables can be nonzero
(and must equal 1), i.e. G must be cyclic.

But the product of the orders of elements in a cyclic 2-group is of
the form
1 x 2 x 4^2 x 8^4 x 16^8 x ...
= 2^( 0 + 1.2^0 + 2.2^1 + 3.2^2 + 4.2^3 + ... + (N+1).2^N)
= 2N.2^N + 1

This is too small (1793) when N=7 and too large (4096) when N=8.


That was a lot of arithmetic.


A6: Drew a blank, sorry.




B1: It suffices to show this for integers, which we can do
by induction: if n is composite, write it as a product of smaller
integers, and by induction write each as a quotient of products of
prime-factorials. If instead n is prime, use the inductive
hypothesis to express each of n-1, n-2, n-3, ... in the desired
form, and then substitute into the expression
n = n! / ( (n-1) (n-2) (n-3) ... )

I can't imagine what's really being tested here; this is obvious.


B2: The right set of c's is the interval (1/3, 1].

If we are to jump in succession from x0=0 to x1, x2, ..., x_n =1
then the total cost will be
C = \sum_{i=0}^{i=n} x_{i+1}^2 \Delta_i
where Delta_i = x_{i+1} - x_i is the size of the i-th jump.
Since each x_i <= 1 this C is less than the sum of the Delta_i,
which is 1.

Observe that this expression for C is exactly the Right-Hand
Riemann Sum used to estimate the integral \int_0^1 x^2 dx for
the partition of [0,1] defined by the jumps. Since the squaring
function is increasing, this Riemann sum exceeds the actual
integral, which course equals 1/3 .

So our cost must lie in the interval.

Let C_n be the set of possible costs for n-jump games.
The cost is a continuous function of the variables Delta_i,
which range over a simplex in R^n, hence C_n is an interval.
By considering jumps of length 0 it is clear that C_n is
a subset of C_{n+1}. Also C_1 = {1}.

Finally note that the integral \int_0^1 x^2 dx must be the
infimum of these Riemann sums, so as n increases, the C_n
approach 1/3 arbitrarily closely.

Thus the set of all possible costs must be (1/3, 1].


B3: Those n which are 1 less than a power of 2:
A(3)=7, A(4)=12, A(5)=18 and 18-2x12+7 = 1;
A(7)=36, A(8)=48, A(9)=61 and 61-2x48+36=1; etc.

Let U_n = {1, 2, ..., n}. Observe that U_{n+2} itself is
a mediocre subset of U_{n+2}. So are all the mediocre subsets
of U_{n+1}, as well as the translates of those by +1 .
Indeed, they account for all the mediocre subsets of U_{n+2} which
lack 1 or n+2 (or both -- those are precisely the translates of
the mediocre subsets of U_n ). So we have already demonstrated
that A(n+2) >= 2 A(n+1) - A(n) + 1, which equality iff the
only mediocre subset of U_{n+2} containing both 1 and n+2
is U_{n+2} itself.

If n+1 = r s with s>1 odd, then
{ 1, 1+s, 1+2s, ..., 1+rs }
is a mediocre subset of U_{n+2}, so equality can only hold
when n+1 is a power of 2.

Conversely if n+1 = 2^k then a mediocre subset of U_{n+2}
containing 1 and n+2 = 1+2^k is found first to include the
midpoint 1 + 2^(k-1), then 1 + 2^(k-2) and 1 + 3 2^(k-2),
and so on ("counting in binary") until we discover the subset
includes all of U_{n+2}.

So equality holds iff n+1 is a power of 2.


B4: the average value of x^i y^j on the circle
(R cos t, R sin t) is
(1/2pi) R^{i+j-1} \int_0^2pi (cos t)^i (sin t)^j dt.
This is zero whenever i or j is odd by symmetry and obviously
positive if i and j are both even, in which case we can scale the
monomial so that the average value is exactly R^{i+j-1}. Thus the
vector space V is spanned by all the monomials x^i y^j with
i or j odd, together with a codimension-1 subspace of the spans of
1
x^2, y^2
x^4, x^2 y^2, y^4
etc.

So of the 2010.2011/2 possible monomials x^i y^j, we remove
1005.1006/2 even-even pairs to get 1,515,540 balanced monomials,
plus 1 polynomial in the span of x^2, y^2; 2 in the span of
x^4, x^2y^2, y^4, etc., up to 1004 in the span of x^2008, ... ;
these give an additional 1004.1005/2 = 504,510 polynomials, for a
grand total of a 2,020,050-dimensional space.


B5: I am probably gathering too much information but
I find f = O(x^(1/3)) and in particular f is unbounded.

The related ODE h'(x) = 1/(h(x)^2 + 1) is satisfied by what
I might call a "twisted cube root function", defined by
h(z)^3 + 3 h(z) = 3 z.
It's easy to check that this equation defines a unique h for each
z, roughly h(z) = O(z^(1/3)). This h is smoothly invertible.

Let u = h^{-1} o f, that is, we write f(x) = h(u(x)) for an
unknown function u . Then we compute derivatives:
f'(x) = u'(x) / (h(u(x))^2+1).
Comparing to the ODE this tells us
u'(x) = 1 - (h(u(x))/x)^2

In particular, u'(x) < 1, so u(x) < x + C for some constant C.
Now, the definition of h shows that h(z) < (3z)^(1/3) when z>0,
so h(u(x))/x < (3(x+C))^(1/3)/x < A x^(-2/3) for suitable A.
It follows that u'(x) > 1 - A^2 x^(-4/3), so that
u(x) > x + B x^(-1/3) for suitable B . In particular,
u -> infinity with x, and then f = h(u(x)) -> infinity as well.

B6: No answer. I find this a little surprising: EVERY integer, no
matter how large, can be computed in at most 2009 steps? How would
you compute e.g. (2^1000000)! in this way?

From: Jake Wildstrom on 6 Dec 2009 14:38
In article <6813d8d1-6cb6-4f61-9458-931939204fdb(a)t18g2000vbj.googlegroups.com>,
dave.rusin <dave.rusin(a)gmail.com> wrote:
>B6: No answer. I find this a little surprising: EVERY integer, no
>matter how large, can be computed in at most 2009 steps? How would
>you compute e.g. (2^1000000)! in this way?

This one seems definitely a bit dubious, but consider: if it's
possible to make a_n a sufficiently large prime for which 2 is a
primitive root, you can get _every_ number less than a_n by taking
a_(n+1)=2^k, a_(n+2)=mod a_n.

The hard part, then, is showing that there are arbitrarily large
primes with fewer than 2007 1s in their binary representation, which
have 2 as a primitive root. I can't prove that (and, in fact, it's a
modification of Artin's conjecture, and thus a far-from-trivial
assertion in its own right), but it seems plausible at least.

-Jake
From: Erick Bryce Wong on 7 Dec 2009 12:42
Jake Wildstrom <dwildstr(a)erdos.math.louisville.edu> wrote:
>dave.rusin <dave.rusin(a)gmail.com> wrote:
>>B6: No answer. I find this a little surprising: EVERY integer, no
>>matter how large, can be computed in at most 2009 steps? How would
>>you compute e.g. (2^1000000)! in this way?
>
>This one seems definitely a bit dubious, but consider: if it's
>possible to make a_n a sufficiently large prime for which 2 is a
>primitive root, you can get _every_ number less than a_n by taking
>a_(n+1)=2^k, a_(n+2)=mod a_n.
>
>The hard part, then, is showing that there are arbitrarily large
>primes with fewer than 2007 1s in their binary representation, which
>have 2 as a primitive root. I can't prove that (and, in fact, it's a

Aha, but you don't need to have a large prime p. Instead, we can use
5^k as a modulus to represent any n coprime to 5 (either n or n-1 has
this property). So we can do this if we can produce 5^k in a bounded
number of steps.

Now to produce 5^k, note that given a < b in the sequence, we can easily
generate b - a by picking a large 2^m and taking (2^m + b) mod (2^m + a).
Thus we can quickly produce numbers of the form 2^m - 5.

Now, since 2^m == 5 (mod 2^m - 5), we have 2^km == 5^k (mod 2^m - 5).
Thus we can produce 5^k by taking m sufficiently large.

It is clear that we have used fewer than 2009 steps to get this far;
probably no more than 15. I'm curious to see how many other operations
are possible in constant time with this instruction set. Addition is
trivial from two subtractions. The above trick allows taking arbitrary
powers, which then almost gives multiplication (by (x+y)^2 - x^2 - y^2).

Also, if x can be computed in k steps then so could x * 2^m for any x.

-- Erick
 |  Next  |  Last
Pages: 1 2
Prev: Set Theory, Anyone?
Next: pentic root