lotus

previous page: 145 competition/tests/math/putnam/putnam.1987.p
  
page up: Puzzles FAQ
  
next page: 147 competition/tests/math/putnam/putnam.1990.p

146 competition/tests/math/putnam/putnam.1988.p




Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

146 competition/tests/math/putnam/putnam.1988.p


Problem A-1: Let R be the region consisting of the points (x,y) of the
cartesian plane satisfying both |x| - |y| <= 1 and |y| <= 1. Sketch
the region R and find its area.

Problem A-2: A not uncommon calculus mistake is to believe that the
product rule for derivatives says that (fg)' = f'g'. If f(x) =
exp(x^2), determine, with proof, whether there exists an open interval
(a,b) and a non-zero function g defined on (a,b) such that the wrong
product rule is true for x in (a,b).

Problem A-3: Determine, with proof, the set of real numbers x for
which sum from n=1 to infinity of ((1/n)csc(1/n) - 1)^x converges.

Problem A-4:
(a) If every point on the plane is painted one of three colors, do
there necessarily exist two points of the same color exactly one inch
apart?
(b) What if "three" is replaced by "nine"?
Justify your answers.

Problem A-5: Prove that there exists a *unique* function f from the
set R+ of positive real numbers to R+ such that
f(f(x)) = 6x - f(x) and f(x) > 0 for all x > 0.

Problem A-6: If a linear transformation A on an n-dimensional vector
space has n + 1 eigenvectors such that any n of them are linearly
independent, does it follow that A is a scalar multiple of the
identity? Prove your answer.

---------------------------------------------------------------------------

Problem B-1: A *composite* (positive integer) is a product ab with a
and b not necessarily distinct integers in {2,3,4,...}. Show that
every composite is expressible as xy + xz + yz + 1, with x, y, and z
positive integers.

Problem B-2: Prove or disprove: If x and y are real numbers with y >= 0
and y(y+1) <= (x+1)^2, then y(y-1) <= x^2.

Problem B-3: For every n in the set Z+ = {1,2,...} of positive
integers, let r(n) be the minimum value of |c-d sqrt(3)| for all
nonnegative integers c and d with c + d = n. Find, with proof, the
smallest positive real number g with r(n) <= g for all n in Z+.

Problem B-4: Prove that if sum from n=1 to infinity a(n) is a
convergent series of positive real numbers, then so is
sum from n=1 to infinity (a(n))^(n/(n+1)).

Problem B-5: For positive integers n, let M(n) be the 2n + 1 by 2n + 1
skew-symmetric matrix for which each entry in the first n subdiagonals
below the main diagonal is 1 and each of the remaining entries below
the main diagonal is -1. Find, with proof, the rank of M(n).
(According to the definition the rank of a matrix is the largest k
such that there is a k x k submatrix with non-zero determinant.)

One may note that M(1) = (  0 -1  1 ) and M(2) = (  0 -1 -1  1  1 )
                         (  1  0 -1 )            (  1  0 -1 -1  1 )
                         ( -1  1  0 )            (  1  1  0 -1 -1 )
                                                 ( -1  1  1  0 -1 )
                                                 ( -1 -1  1  1  0 )

Problem B-6: Prove that there exist an infinite number of ordered
pairs (a,b) of integers such that for every positive integer t the
number at + b is a triangular number if and only if t is a triangular
number. (The triangular numbers are the t(n) = n(n + 1)/2 with n in
{0,1,2,...}.)

competition/tests/math/putnam/putnam.1988.s

%
%  Layout
%
\def\layout{\hsize 150truemm  % 210mm - 1in * 2 for margins
                \vsize 246truemm  % 297mm - 1in * 2 for margins
                \advance \vsize by -24 pt
                \topskip=10pt plus 1 pt}
\magnification=1200
\layout
\parindent=0pt
\parskip=\medskipamount
\newdimen\digitindent \digitindent=16truemm
\newdimen\solindent \solindent=24truemm
\newdimen\problemskip\newdimen\subproblemskip
\problemskip=\bigskipamount \subproblemskip=\medskipamount
\hoffset=\digitindent
\def\problem #1 { \vskip \problemskip\hskip-\digitindent\hbox to\digitindent
                  {\bf #1\hfill}\ignorespaces}
\def\solution #1 { \vskip \problemskip\hskip-\solindent\hbox to\solindent
                  {\bf #1\hfill}\ignorespaces}
\def\notes #1 { \vskip \problemskip\hskip-\solindent\hbox to\solindent
                  {\bf #1\hfill}\ignorespaces}
\def\subproblem #1 {\vskip \subproblemskip\hskip-\digitindent
                     \hbox to\digitindent{\hfill{\bf #1}\hfill}\ignorespaces}
\def\endpage {\vfill\supereject\dosupereject}
\headline={\headlinemacro}
\footline={\hfil}
\def\activeheadline{\hglue -\digitindent
                     Chris Long, Rutgers University \hfill January 22, 1989}
\let\headlinemacro=\activeheadline
\advance \baselineskip by 6pt
%
% Aliases
%
\def\streck{\hbox {\vbox {\vfill \hrule width 0.5pt height 6pt \vskip 0.7pt}}}
\def\C{\hbox{\hskip 1.5pt \streck \hskip -3.2pt {\rm C}}}
\def\Q{\hbox{ \streck \hskip -3pt {\rm Q}}}
\def\negativethinspace{\mskip-\thinmuskip}
\def\R{\hbox{$\rm I \negativethinspace R $}}
\def\Z{\hbox{$\rm Z \negativethinspace  \negativethinspace Z $}}
\def\N{\hbox{$\rm I \negativethinspace N $}}
\def\H{\hbox{$\rm I \negativethinspace H $}}
\def\adj{\rm adj}
\def\det{\rm det}
\def\Matrix#1{\left\lgroup\matrix{#1}\rgroup\right}
\def\mod #1 {({\rm mod~}#1)}
\def\Mod #1 {\ ({\rm mod~}#1)}
\def\ceil#1{\lceil #1 \rceil}
\def\floor#1{\lfloor #1 \rfloor}
%
%  Body of article
%
\problem {A-1:}
Let $R$ be the region consisting of the points $(x,y)$ of the cartesian
plane satisfying both $|x| - |y| \le 1$ and $|y| \le 1$. Sketch the
region $R$ and find its area.

\solution {Solution:}
The area is $6$; the graph I leave to the reader.

\problem {A-2:}
A not uncommon calculus mistake is to believe that the product rule for
derivatives says that $(fg)' = f'g'$. If $f(x) = e^{x^{2}}$, determine,
with proof, whether there exists an open interval $(a,b)$ and a non-zero
function $g$ defined on $(a,b)$ such that the wrong product rule
is true for $x$ in $(a,b)$.

\solution {Solution:}
We find all such functions. Note that $(fg)' = f'g' \Rightarrow f'g'
= f'g + fg'$ hence if $g(x), f'(x) - f(x) \neq 0$ we get that $g'(x)/g(x)
= f'(x)/(f'(x) - f(x))$. For the particular $f$ given, we then get that
$g'(x)/g(x) = (2x)e^{x^2}/( (2x-1) (e^{x^2}) ) \Rightarrow g'(x)/g(x) =
2x/(2x-1)$ (since $e^{x^2} > 0$). Integrating, we deduce that $\ln{|g(x)|}
= x + (1/2)\ln{|2x-1|} + c$ (an arbitrary constant) $\Rightarrow |g(x)|
= e^{c} \sqrt{|2x-1|} e^{x} \Rightarrow g(x) = C \sqrt{|2x-1|} e^{x}, C$
arbitrary $\neq 0$. We finish by noting that any $g(x)$ so defined is
differentiable on any open interval that does not contain $1/2$.

Q.E.D.

\problem {A-3:}
Determine, with proof, the set of real numbers $x$ for which
$\sum_{n=1}^{\infty} {( {1\over n} \csc ({1\over n}) - 1)}^{x}$
converges.

\solution {Solution:}
The answer is $x > {1\over 2}$. To see this, note that by Taylor's
theorem with remainder $\sin( {1\over{n}} ) = \sum_{i=1}^{k-1}
{ {(-1)}^{i-1} {n}^{-(2i+1)} } + c { {(-1)}^{k-1} {n}^{-(2k+1)} }$,
where $0 \leq c \leq {1\over n}$. Hence for $n\geq 1 ( 1/n )/( 1/n -
1/(3! n^{3}) + 1/(5! n^{5}) - 1 < (1/n) \csc(1/n) - 1 < ( 1/n )/( 1/n
- 1/(3! n^{3}) ) - 1 \Rightarrow$ for $n$ large enough, $ (1/2) 1/(3! n^{2})
< (1/n) \csc(1/n) - 1 < 2\cdot 1/(3! n^{2})$. Applying the p-test and the
comparison test, we see that $\sum_{n=1}^{\infty} {( {1\over n}
\csc({1\over n}) - 1)}^{x}$ converges iff $x > {1\over 2}$.

Q.E.D.

\problem {A-4:}
Justify your answers.

\subproblem {(a)}
If every point on the plane is painted one of three colors, do there
necessarily exist two points of the same color exactly one inch apart?

\solution {Solution:}
The answer is yes. Assume not and consider two equilateral
triangles with side one that have exactly one common face $\Rightarrow$
all points a distance of $\sqrt{3}$ apart are the same color; now
considering a triangle with sides $\sqrt{3}, \sqrt{3}, 1$ we reach the
desired contradiction.

Here is a pretty good list of references for the chromatic number of
the plane (i.e., how many colors do you need so that no two points 1
away are the same color) up to around 1982 (though the publication
dates are up to 1985). This asks for the chromatic number of the graph
where two points in R^2 are connected if they are distance 1 apart.
Let this chromatic number be chi(2) and in general let chi(n) be the
chromatic number of R^n. By a theorem in [2] this is equivalent to
finding what the maximum chromatic number of a finite subgraph of this
infinite graph is.

[1] H. Hadwiger, ``Ein Ueberdeckungssatz f\"ur den
Euklidischen Raum,'' Portugal. Math. #4 (1944), p.140-144

This seems to be the original reference for the problem

[2] N.G. de Bruijn and P. Erd\"os, ``A Color Problem for Infinite
Graphs and a Problem in the Theory of Relations,'' Nederl. Akad.
Wetensch. (Indag Math) #13 (1951), p. 371-373.

[3] H. Hadwiger, ``Ungel\"oste Probleme No. 40,'' Elemente der Math.
#16 (1961), p. 103-104.

Gives the upper bound of 7 with the hexagonal tiling and also
a reference to a Portugese journal where it appeared.

[4] L. Moser and W. Moser, ``Solution to Problem 10,'' Canad. Math.
Bull. #4 (1961), p. 187-189.

Shows that any 6 points in the plane only need 3 colors but
gives 7 points that require 4 (``the Moser Graph'' see [7]).

[5] Paul Erd\"os, Frank Harary, and William T. Tutte, ``On the
Dimension of a Graph,'' Mathematika #12 (1965), p. 118-122.

States that 3<chi(2)<8. Proves that chi(n) is finite for all n.

[6] P. Erd\"os, ``Problems and Results in Combinatorial Geometry,''
in ``Discrete Geometry and Convexity,'' Edited by Jacob E. Goodman,
Erwin Lutwak, Joseph Malkevitch, and Richard Pollack, Annals of
the New York Academy of Sciences Vol. 440, New York Academy of
Sciences 1985, Pages 1-11.

States that 3<chi(n)<8 and ``I am almost sure that chi(2)>4.''
States a question of L. Moser: Let R be large and S a measurable
set in the circle of radius R so that no two points of S have
distance 1. Denote by m(S) the measure of S. Determine

Lim_{R => infty} max m(S)/R^2.

Erd\"os conjectures that this limit is less than 1/4.

Erd\"os asks the following: ``Let S be a subset of the plane. Join
two points of S if their distances is 1. This gives a graph G(S).
Assume that the girth (shortest circuit) of G(S) is k. Can its
chromatic number be greater than 3? Wormald proved that such
a graph exists for k<6. The problem is open for k>5. Wormald
suggested that this method may work for k=6, but probably a
new idea is needed for k>6. A related (perhaps identical)
question is: `Does G(S) have a subgraph that has girth k and
chromatic number 4?' ''

[7] N. Wormald, ``A 4-chromatic graph with a special plane drawing,''
J. Austr. Math. Soc. Ser. A #28 (1970), p. 1-8.

The reference for the above question.

[8] R.L. Graham, ``Old and New Euclidean Ramsey Theorems,''
in ``Discrete Geometry and Convexity,'' Edited by Jacob E. Goodman,
Erwin Lutwak, Joseph Malkevitch, and Richard Pollack, Annals of
the New York Academy of Sciences Vol. 440, New York Academy of
Sciences 1985, Pages 20-30.

States that the best current bounds are 3<chi(2)<8. Calls the
graph in [3] the Moser graph. Quotes the result of Frankl and
Wilson [8] that chi(n) grows exponentially in n settling an
earlier conjecture of Erd\"os (I don't know the reference for
this). The best available bounds for this are

(1+ o(1)) (1.2)^n \le chi(n) \le (3+ o(1))^n.

[9] P. Frankl and R.M. Wilson, ``Intersection Theorems with Geometric
Consequences,'' Combinatorica #1 (1981), p. 357-368.

[10] H. Hadwiger, H. Debrunner, and V.L. Klee, ``Combinatorial
Geometry in the Plane,'' Holt, Rinehart & Winston, New York
(English edition, 1964).

[11] D.R. Woodall, ``Distances Realized by Sets Covering the Plane,''
Journal of Combinatorial Theory (A) #14 (1973), p. 187-200.

Among other things, shows that rational points in the plane can
be two colored.

[12] L. A. Sz\'ekely, ``Measurable Chromatic Number of Geometric
Graphs and Sets without some Distances in Euclidean Space,''
Combinatorica #4 (1984), p.213-218.

Considers \chi_m(R^2), the measurable chromatic number,
where sets of one color must be Lebesgue measurable.
He conjectures that \chi_m(R^2) is not equal to
\chi(R^2) (if the Axiom of Choice is false).

[13] Martin Gardner, ``Scientific American,'' October 1960, p. 160.

[14] Martin Gardner, ``Wheels, Life and other Mathematical Amusements,''
W.H. Freeman and Co., New York 1983, pages 195-196.

This occurs in a chapter on mathematical problems including
the 3x+1 problem. I think that his references are wrong, including
attributing the problem to Erd\"os and claiming that Charles Trigg
had original solutions in ``Problem 133,'' Crux Mathematicorum,
Vol. 2, 1976, pages 144-150.

Q.E.D.

\subproblem {(b)}
What if "three" is replaced by "nine"?

In this case, there does not necessarily exist two points of the same
color exactly one inch apart; this can be demonstrated by considering
a tessellation of the plane by a $3\times 3$ checkboard with side $2$,
with each component square a different color (color of boundary points
chosen in an obvious manner).

Q.E.D.

The length of the side of the checkerboard is not critical (the reader
my enjoy showing that $3/2 <$ side $< 3\sqrt{2}/2$ works).

\problem {A-5:}
Prove that there exists a {\it unique} function $f$ from the set
${\R}^{+}$ of positive real numbers to ${\R}^{+}$ such that $f(f(x))
= 6x - f(x)$ and $f(x) > 0$ for all $x > 0$.

\solution {Solution 1:}

Clearly $f(x) = 2x$ is one such solution; we need to show that it is the
{\it only} solution. Let $f^{1}(x) = f(x), f^{n}(x) = f(f^{n-1}(x))$ and
notice that $f^{n}(x)$ is defined for all $x>0$. An easy induction
establishes that for $n>0 f^{n}(x) = a_{n} x + b_{n} f(x)$, where $a_{0}
= 0, b_{0} = 1$ and $a_{n+1} = 6 b_{n}, b_{n+1} = a_{n} - b_{n}
\Rightarrow b_{n+1} = 6 b_{n-1} - b_{n}$. Solving this latter equation
in the standard manner, we deduce that $\lim_{n\to \infty} a_{n}/b_{n}
= -2$, and since we have that $f^{n}(x) > 0$ and since $b_{n}$ is
alternately negative and positive; we conclude that $2x \leq f(x) \leq 2x$
by letting $n \rightarrow \infty$.

Q.E.D.

\solution {Solution 2:}
(Dan Bernstein, Princeton)

As before, $f(x) = 2x$ works. We must show that if $f(x) = 2x + g(x)$
and $f$ satisfies the conditions then $g(x) = 0$ on ${\R}^{+}$.
Now $f(f(x)) = 6x - f(x)$ means that $2f(x) + g(f(x)) = 6x - 2x - g(x)$,
i.e., $4x + 2g(x) + g(f(x)) = 4x - g(x)$, i.e., $3g(x) + g(f(x)) = 0$.
This then implies $g(f(f(x))) = 9g(x)$. Also note that $f(x) > 0$
implies $g(x) > -2x$. Suppose $g(x)$ is not $0$ everywhere. Pick $y$
at which $g(y) \neq 0$. If $g(y) > 0$, observe $g(f(y)) = -3g(y) < 0$,
so in any case there is a $y_{0}$ with $g(y_{0}) < 0$. Now define $y_{1}
= f(f(y_{0})), y_{2} = f(f(y_{1}))$, etc. We know $g(y_{n+1})$ equals
$g(f(f(y_{n}))) = 9g(y_{n})$. But $y(n+1) = f(f(y_{n})) = 6y_{n} -
f(y_{n}) < 6y_{n}$ since $f>0$. Hence for each $n$ there exists
$y_{n} < 6^{n} y_{0}$ such that $g(y_{n}) = 9^{n} g(y_{0})$.
The rest is obvious: $0 > g(y_{0}) = 9^{-n} g(y_{n}) > -2\cdot 9^{-n}
y_{n} > -2 (6/9)^{n} y_{0}$, and we observe that as $n$ goes to infinity
we have a contradiction.

Q.E.D.

\problem {A-6:}
If a linear transformation $A$ on an $n$-dimensional vector space has
$n+1$ eigenvectors such that any $n$ of them are linearly independent,
does it follow that $A$ is a scalar multiple of the identity? Prove your
answer.

\solution {Solution:}
The answer is yes. First note that if $x_{1}, \ldots, x_{n+1}$ are the
eigenvectors, then we must have that $a_{n+1} x_{n+1} = a_{1} x_{1}
+ \cdots + a_{n} x_{n}$ for some non-zero scalars $a_{1}, \ldots, a_{n+1}$.
Multiplying by $A$ on the left we see that $\lambda_{n+1} a_{n+1} x_{n+1}
= \lambda_{1} a_{1} x_{1} + \cdots + \lambda_{n} a_{n} x_{n}$, where
$\lambda_{i}$ is the eigenvalue corresponding to the eigenvectors $x_{i}$.
But since we also have that $\lambda_{n+1} a_{n+1} x_{n+1} = \lambda_{n+1}
a_{1} x_{1} + \cdots + \lambda_{n+1} a_{n} x_{n}$ we conclude that
$\lambda_{1} a_{1} x_{1} + \cdots + \lambda_{n} a_{n} x_{n} = \lambda_{n+1}
a_{1} x_{1} + \cdots + \lambda_{n+1} a_{n} x_{n} \Rightarrow a_{1}
(\lambda_{1} - \lambda_{n+1}) x_{1} + \cdots + a_{n} (\lambda_{n} -
\lambda_{n+1}) x_{1} = 0 \Rightarrow \lambda_{1} = \cdots = \lambda_{n+1}
= \lambda$ since $x_{1}, \ldots, x_{n}$ are linearly independent. To
finish, note that the dimension of the eigenspace of $\lambda$ is equal
to $n$, and since this equals the dimension of the nullspace of $A -
\lambda I$ we conclude that the rank of $A - \lambda I$ equals $n - n =
0 \Rightarrow A - \lambda I = 0$.

Q.E.D.

\problem {B-1:}
A {\it composite} (positive integer) is a product $ab$ with $a$ and $b$
not necessarily distinct integers in $\{ 2,3,4,\ldots \}$. Show that
every composite is expressible as $xy + xz + yz + 1$, with $x, y$, and
$z$ positive integers.

\solution {Solution:}
Let $x = a-1, y = b-1, z = 1$; we then get that $xy + xz + yz + 1
= (a-1)(b-1) + a-1 + b-1 + 1 = ab$.

Q.E.D.

\problem {B-2:}
Prove or disprove: If $x$ and $y$ are real numbers with $y \geq 0$
and $y(y+1) \leq {(x+1)}^2$, then $y(y-1) \leq x^2$.

\solution {Solution:}
The statement is true. If $x+1 \geq 0$ we have that $\sqrt{y(y+1)}
- 1 \leq x \Rightarrow x^{2} \geq y^{2} + y + 1 - 2 \sqrt{y^{2}+y} \geq
y^{2} - y$ since $2y + 1 \geq 2 \sqrt{y^{2}+y}$ since ${(2y + 1)}^{2}
\geq 4 (y^{2}+y)$ if $y\geq 0$. If $x+1 < 0$, we see that $\sqrt{y(y+1)}
\leq -x - 1 \Rightarrow x^{2} \geq y^{2} + y + 1 + 2 \sqrt{y^{2}+y}
\geq y^{2} - y$.

Q.E.D.

\problem {B-3:}
For every $n$ in the set ${\Z}^{+} = \{ 1,2,\ldots \}$ of positive
integers, let $r(n)$ be the minimum value of $|c-d \sqrt{3}|$ for all
nonnegative integers $c$ and $d$ with $c + d = n$. Find, with proof,
the smallest positive real number $g$ with $r(n) \leq g$ for all $n$
in ${\Z}^{+}$.

\solution {Solution:}
The answer is $(1 + \sqrt{3})/2$. We write $|c-d\sqrt{3}|$ as
$|(n-d) - d\sqrt{3}|$; I claim that the minimum over all $d, 0 \leq d
\leq n$, occurs when $d = e = \floor{n/(1+\sqrt{3})}$ or when $d = f =
e+1 = \floor{n/(1+\sqrt{3})} + 1$. To see this, note that $(n-e) - e
\sqrt{3} > 0$ and if $e'<e$, then $(n-e') - e' \sqrt{3} > (n-e) - e
\sqrt{3}$, and similarly for $f'>f$. Now let $r = n/(1+\sqrt{3}) -
\floor{n/(1+\sqrt{3})}$ and note that $|(n-e) - e \sqrt{3}| = r
(1+\sqrt{3})$ and $|(n-f) - f \sqrt{3}| = (1-r) (1+\sqrt{3})$. Clearly
one of these will be $\leq (1+\sqrt{3})/2$. To see that $(1+\leq{3})/2$
cannot be lowered, note that since $1+\sqrt{3}$ is irrational, $r$ is
uniformly distributed $\mod{1} $.

Q.E.D.

\notes {Notes:}
We do not really need the result that $x$ irrational $\Rightarrow x n
- \floor{x n}$ u. d. $\mod{1} $, it would suffice to show that $x$
irrational $\Rightarrow x n - \floor{x n}$ is dense in $(0,1)$. But
this is obvious, since if $x$ is irrational there exists arbitrarily
large $q$ such that there exists $p$ with $(p,q) = 1$ such that $p/q <
x < (p+1)/q$. The nifty thing about the u. d. result is that it answers
the question: what number $x$ should we choose such that the density
of $\{ n : r(n) < x \}$ equals $t, 0 < t < 1$? The u. d. result implies
that the answer is $t (1+\sqrt{3})/2$. The u. d. result also provides
the key to the question: what is the average value of $r(n)$? The
answer is $(1+\sqrt{3})/4$.

\problem {B-4:}
Prove that if $\sum_{n=1}^{\infty} a(n)$ is a convergent series of
positive real numbers, then so is $\sum_{n=1}^{\infty} {(a(n))}^{n/(n+1)}$.

\solution {Solution:}
Note that the subseries of terms ${a(n)}^{n\over{n+1}}$ with
${a(n)}^{1\over{n+1}} \leq {1\over 2}$ converges since then
${a(n)}^{n\over{n+1}}$ is dominated by $1/2^{n}$, the subseries of
terms ${a(n)}^{n\over{n+1}}$ with ${a(n)}^{1\over{n+1}} > {1\over 2}$
converges since then ${a(n)}^{n\over{n+1}}$ is dominated by $2 a(n)$,
hence $\sum_{n=1}^{\infty} {a(n)}^{n\over{n+1}}$ converges.

Q.E.D.

\problem {B-5:}
For positive integers $n$, let $M(n)$ be the $2n + 1$ by $2n + 1$
skew-symmetric matrix for which each entry in the first $n$ subdiagonals
below the main diagonal is $1$ and each of the remaining entries below
the main diagonal is $-1$. Find, with proof, the rank of $M(n)$.
(According to the definition the rank of a matrix is the largest $k$
such that there is a $k \times k$ submatrix with non-zero determinant.)

One may note that \break\hfill
$M(1) = \left( \matrix{0&-1&1 \cr 1&0&-1
\cr -1&1&0} \right)$ and $M(2) = \left( \matrix{0&-1&-1&1&1
\cr 1&0&-1&-1&1 \cr 1&1&0&-1&-1 \cr -1&1&1&0&-1 \cr -1&-1&1&1&0}
\right)$.

\solution {Solution 1:}
Since $M(n)$ is skew-symmetric, $M(n)$ is singular for all $n$, hence
the rank can be at most $2n$. To see that this is indeed the answer,
consider the submatrix $M_{i}(n)$ obtained by deleting row $i$ and column
$i$ from $M(n)$. From the definition of the determinant we have that
$\det(M_{i}(n)) = \sum {(-1)}^{\delta(k)} a_{1 k(1)} \cdots a_{(2n) k(2n)}$,
where $k$ is member of $S_{2n}$ (the group of permutations on
$\{1,\ldots,2n\}$) and $\delta(k)$ is $0$ if $k$ is an even permutation or
$1$ if $k$ is an odd permutation. Now note that ${(-1)}^{\delta(k)}
a_{1 k(1)} \cdots a_{(2n) k(2n)}$ equals either $0$ or $\pm 1$, and is
non-zero iff $k(i) \neq i$ for all $i$, i.e. iff $k$ has no fixed points.
If we can now show that the set of all elements $k$ of $S_{2n}$, with
$k(i) \neq i$ for all $i$, has odd order, we win since this would imply that
$\det(M_{i}(n))$ is odd $\Rightarrow \det(M_{i}) \neq 0$. To show this,
let $f(n)$ equal the set of all elements $k$ of $S_n$ with $k(i) \neq
i$ for all $i$. We have that $f(1) = 0, f(2) = 1$ and we see that
$f(n) = (n-1) ( f(n-1) + f(n-2) )$ by considering the possible values of
$f(1)$ and whether or not $f(f(1)) = 1$; an easy induction now establishes
that $f(2n)$ is odd for all $n$.

Q.E.D.

\notes {Notes:}
In fact, it is a well-known result that $f(n) = n! ( 1/2! - 1/3! + \cdots
+ {(-1)}^{n}/n! )$.

\solution {Solution 2:}
As before, since $M(n)$ is skew-symmetric $M(n)$ is singular for all $n$
and hence can have rank at most $2n$. To see that this is the rank,
let $M_{i}(n)$ be the submatrix obtained by deleting row $i$ and column
$i$ from $M(n)$. We finish by noting that ${M_{i}(n)}^{2} \equiv
I_{2n} \Mod{2} $, hence $M_{i}(n)$ is nonsingular.

Q.E.D.

\problem {B-6:}
Prove that there exist an infinite number of ordered pairs $(a,b)$ of
integers such that for every positive integer $t$ the number $at + b$
is a triangular number if and only if $t$ is a triangular number.
(The triangular numbers are the $t(n) = n(n + 1)/2$ with $n$ in
$ \{ 0,1,2,\ldots \}$ ).

\solution {Solution:}
Call a pair of integers $(a,b)$ a {\it triangular pair} if $at + b$
is a triangular number iff $t$ is a triangular number. I claim that
$(9,1)$ is a triangular pair. Note that $9 (n(n+1)/2) + 1 =
(3n+1)(3n+2)/2$ hence $9t+1$ is triangular if $t$ is. For the other
direction, note that if $ 9t+1 = n(n+1)/2 \Rightarrow n = 3k+1$
hence $ 9t+1 = n(n+1)/2 = 9(k(k+1)/2)+1 \Rightarrow t = k(k+1)/2$,
therefore $t$ is triangular. Now note that if $(a,b)$ is a triangular
pair then so is $(a^{2},(a+1)b)$, hence we can generate an infinite
number of triangular pairs starting with $(9,1)$.

Q.E.D.

\notes {Notes:}
The following is a proof of necessary and sufficient conditions for $(a,b)$
to be a triangular pair.

I claim that $(a,b)$ is a triangular pair iff for some odd integer $o$
we have that $a = o^{2}, b = (o^{2}-1)/8$. I will first prove the
direction $\Leftarrow$. Assume we have $a = o^{2}, b = (o^{2}-1)/8$.
If $t = n(n+1)/2$ is any triangular number, then the identity $o^{2}
n(n+1)/2 + (o^{2}-1)/8 = (on + (o-1)/2) (on + (o+1)/2)/2$ shows that
$at + b$ is also a triangular number. On the other hand if $o^{2} t +
(o^{2}-1)/8 = n(n+1)/2$, the above identity implies we win if we can show
that $( n - (o-1)/2 )/o$ is an integer, but this is true since $o^{2} t +
(o^{2}-1)/8 \equiv n(n+1)/2 \Mod{o^{2}} \Rightarrow 4n^{2} + 4n \equiv -1
\Mod{o^{2}} \Rightarrow {(2n + 1)}^{2} \equiv 0 \Mod{o^{2}} \Rightarrow 2n + 1
\equiv 0 \Mod{o} \Rightarrow n \equiv (o-1)/2 \Mod{o} $. For the direction
$\Rightarrow$ assume that $(a,b)$ and $(a,c), c\ge b$, are both triangular
pairs; to see that $b = c$ notice that if $at + b$ is triangular for all
triangular numbers $t$, then we can choose $t$ so large that if $c>b$ then
$at + c$ falls between two consecutive triangular numbers; contradiction hence
$b = c$. Now assume that $(a,c)$ and $(b,c)$ are both triangular pairs;
I claim that $a = b$. But this is clear since if $(a,c)$ and $(b,c)$
are triangular pairs $\Rightarrow (ab,bc+c)$ and $(ab,ac+c)$ are
triangular pairs $\Rightarrow bc+c = ac+c$ by the above reasoning
$\Rightarrow bc=ac \Rightarrow$ either $a=b$ or $c=0 \Rightarrow a=b$
since $c=0 \Rightarrow a=b=1$. For a proof of this last assertion,
assume $(a,0), a>1$, is a triangular pair; to see that this gives a
contradiction note that if $(a,0)$ is a triangular pair $\Rightarrow
(a^{2},0)$ is also triangular pair, but this is impossible since then
we must have that $a(a^{3}+1)/2$ is triangular (since $a^{2} a (a^{3}+1)/2$
is triangular) but $(a^{2}-1)a^{2}/2 < a(a^{3}+1)/2 < a^{2}(a^{2}+1)/2$
(if $a>1$). We are now done, since if $(a,b)$ is a triangular pair
$\Rightarrow a 0 + b = n(n+1)/2$ for some $n\geq 0 \Rightarrow b =
({(2n+1)}^{2} - 1)/8$.

Q.E.D.

\bye

 

Continue to:













TOP
previous page: 145 competition/tests/math/putnam/putnam.1987.p
  
page up: Puzzles FAQ
  
next page: 147 competition/tests/math/putnam/putnam.1990.p