Solve these six problems by David Wilson.
competition/tests/math/wilson.problems New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Solve these six problems by David Wilson. In the problems, [x] is the
floor of x (greatest integer <= x).
1. Describe all solutions to x^y = y^x where x and y are positive
rationals. What solutions remain if, in addition, x^y must be a
positive rational?
2. For which integers k does there exist a circle in the Cartesian
plane passing through precisely k points with integer coordinates?
3. For positive integers a and b, let G be the grid of points
{ (x, y) in ZxZ : 0 <= x < a, 0 <= y < b } in the Cartesian plane.
How many triangles have all their vertices in G?
4. For integer n >= 1, define f(n) recursively as follows:
f(n) = 1, if n = 1
n
SUM f([n/k]), if n > 1
k = 2
[Editor: "f([f(n/k)])" in one of the two copies collected; the
other copy and the solution use f([n/k]).]
Let n be the product of k >= 1 distinct odd prime factors. What
is the value of f(n) - f(n-1)?
5. For positive integers p and n, let
n
SUM f(k, p) = p
k > 0
k | n
Show that for any p > 0 and k > 0, k | f(k, p).
6. Let c = (3+sqrt(5))/2. Show that for all integers k,
[c[ck]+c] - [c[ck]] = 2
[ Editor: posted to rec.puzzles by David Wilson (ctron-news.ctron.com),
who wrote: "The following six problems, of varying difficulty, are
typical of my sick mathematical bent. I am the author of each." The
first sentence is the editor's. ]
Show solution
[ Editor: solutions to 4-6 by Chris Long, sent to the archive in
August 1993. He wrote: "I haven't solved 1-3, nor were solutions to
them ever posted." No solutions to 1-3 were found in the collected
material. ]
4.
Let df(n) = f(n)-f(n-1). Note that for n>2 f(n)-f(n-1) = f([n/n]) +
\sum_{k=2}^{n-1} f([n/k])-f([(n-1)/k]); [n/k]=[(n-1)/k] except when
k|n, when [n/k]=[(n-1)/k]+1 ==> we have that f(n)-f(n-1) = 1 +
\sum_{k|n,k>1,k<n} df([n/k]). Let n be a number that is the product
of m distinct odd primes; by the above result and induction df(n)
depends only on m and df(n=o_m) = 1+\sum_{i=1}^{m-1} C(m,i)*df(o_i),
where o_i is a number that is the product of i distinct odd primes.
Since df(o_1)=1 this shows that df(o_2)=3, df(o_3)=13, df(o_4)=75,
df(o_5)=541. I haven't been able to find a simple form for df(o_m)
in general yet, but we do have that df(2^m) = [2^{m-2}], df(o_1^m) =
2^{m-1}, and df(2*o_1^m) = (m+1)*2^{m-1}.
5.
By the Moebius inversion theorem f(n,p) = \sum_{d|n} mu(d)*p^{n/d};
now it follows from this that if (a,b)=1 then f(ab,p) =
\sum_{d|b} mu(d)*p^{b/d}*f(a,p) = \sum_{d|a} mu(d)*p^{a/d}*f(b,p).
This implies that if n|f(n,p) for all n the power of a prime, then
it holds for all n. But f(q^m,p) = \sum_{d|q^m} mu(d)*p^{n/d} =
p^{q^m} - p^{q^{m-1}}. If (p,q)=1 by Euler's theorem p^{q^m} =
p^{q^m-q^{m-1}}*p^{q^{m-1}} = p^{q^{m-1}} (mod q^m) so p^{q^m} -
p^{q^{m-1}} = 0 (mod q^m); if p=0 (mod q) then clearly p^{q^m} -
p^{q^{m-1}} = 0 (mod q^m), and so we are done.
6.
Let c=w+1 and wk = [wk] + e, then [(w+1)[(w+1)k]+w+1] - [(w+1)[(w+1)k]]
= 1 + [w[wk+k]+w] - [w[wk+k]] = 1 + [w[wk]+wk+w] - [w[wk]+wk]
= 1 + [w^2*k-we+wk+w] - [w^2*k-we+wk] = 1 + [wk+k-we+wk+w] -
[wk+k-we+wk] = 1 + [[wk]+e-we+[wk]+e+w] - [[wk]+e+-e+[wk]+e]
= 1 + [e-we+e+w] - [e-we+e] = 1 + [e(2-w)+w] - [e(2-w)]. Now,
0=<e<1 and 0<(2-w)<1 so [e(2-w)]=0. Also 0=<e(2-w)<(2-w) so
1 < w =< e(2-w)+w < (2-w)+w = 2 so [e(2-w)+w] = 1.
Note that 0=<e<1 for all k since w is irrational.
-- Chris Long <clong@remus.rutgers.edu>