MathDB
Problems
Contests
Undergraduate contests
Putnam
2008 Putnam
2008 Putnam
Part of
Putnam
Subcontests
(12)
B6
1
Hide problems
Putnam 2008 B6
Let
n
n
n
and
k
k
k
be positive integers. Say that a permutation
σ
\sigma
σ
of
{
1
,
2
,
…
n
}
\{1,2,\dots n\}
{
1
,
2
,
…
n
}
is
k
k
k
-limited if |\sigma(i)\minus{}i|\le k for all
i
.
i.
i
.
Prove that the number of
k
k
k
-limited permutations of
{
1
,
2
,
…
n
}
\{1,2,\dots n\}
{
1
,
2
,
…
n
}
is odd if and only if
n
≡
0
n\equiv 0
n
≡
0
or 1\pmod{2k\plus{}1}.
B5
1
Hide problems
Putnam 2008 B5
Find all continuously differentiable functions
f
:
R
→
R
f: \mathbb{R}\to\mathbb{R}
f
:
R
→
R
such that for every rational number
q
,
q,
q
,
the number
f
(
q
)
f(q)
f
(
q
)
is rational and has the same denominator as
q
.
q.
q
.
(The denominator of a rational number
q
q
q
is the unique positive integer
b
b
b
such that q\equal{}a/b for some integer
a
a
a
with \gcd(a,b)\equal{}1.) (Note:
gcd
\gcd
g
cd
means greatest common divisor.)
B4
1
Hide problems
Putnam 2008 B4
Let
p
p
p
be a prime number. Let
h
(
x
)
h(x)
h
(
x
)
be a polynomial with integer coefficients such that h(0),h(1),\dots, h(p^2\minus{}1) are distinct modulo
p
2
.
p^2.
p
2
.
Show that h(0),h(1),\dots, h(p^3\minus{}1) are distinct modulo
p
3
.
p^3.
p
3
.
B3
1
Hide problems
Putnam 2008 B3
What is the largest possible radius of a circle contained in a 4-dimensional hypercube of side length 1?
B2
1
Hide problems
Putnam 2008 B2
Let F_0\equal{}\ln x. For
n
≥
0
n\ge 0
n
≥
0
and
x
>
0
,
x>0,
x
>
0
,
let \displaystyle F_{n\plus{}1}(x)\equal{}\int_0^xF_n(t)\,dt. Evaluate
lim
n
→
∞
n
!
F
n
(
1
)
ln
n
.
\displaystyle\lim_{n\to\infty}\frac{n!F_n(1)}{\ln n}.
n
→
∞
lim
ln
n
n
!
F
n
(
1
)
.
B1
1
Hide problems
Putnam 2008 B1
What is the maximum number of rational points that can lie on a circle in
R
2
\mathbb{R}^2
R
2
whose center is not a rational point? (A rational point is a point both of whose coordinates are rational numbers.)
A6
1
Hide problems
Putnam 2008 A6
Prove that there exists a constant
c
>
0
c>0
c
>
0
such that in every nontrivial finite group
G
G
G
there exists a sequence of length at most
c
ln
∣
G
∣
c\ln |G|
c
ln
∣
G
∣
with the property that each element of
G
G
G
equals the product of some subsequence. (The elements of
G
G
G
in the sequence are not required to be distinct. A subsequence of a sequence is obtained by selecting some of the terms, not necessarily consecutive, without reordering them; for example,
4
,
4
,
2
4,4,2
4
,
4
,
2
is a subesequence of
2
,
4
,
6
,
4
,
2
,
2,4,6,4,2,
2
,
4
,
6
,
4
,
2
,
but
2
,
2
,
4
2,2,4
2
,
2
,
4
is not.)
A5
1
Hide problems
Putnam 2008 A5
Let
n
≥
3
n\ge 3
n
≥
3
be an integer. Let
f
(
x
)
f(x)
f
(
x
)
and
g
(
x
)
g(x)
g
(
x
)
be polynomials with real coefficients such that the points
(
f
(
1
)
,
g
(
1
)
)
,
(
f
(
2
)
,
g
(
2
)
)
,
…
,
(
f
(
n
)
,
g
(
n
)
)
(f(1),g(1)),(f(2),g(2)),\dots,(f(n),g(n))
(
f
(
1
)
,
g
(
1
))
,
(
f
(
2
)
,
g
(
2
))
,
…
,
(
f
(
n
)
,
g
(
n
))
in
R
2
\mathbb{R}^2
R
2
are the vertices of a regular
n
n
n
-gon in counterclockwise order. Prove that at least one of
f
(
x
)
f(x)
f
(
x
)
and
g
(
x
)
g(x)
g
(
x
)
has degree greater than or equal to n\minus{}1.
A4
1
Hide problems
Putnam 2008 A4
Define
f
:
R
→
R
f: \mathbb{R}\to\mathbb{R}
f
:
R
→
R
by f(x)\equal{}\begin{cases}x&\text{if }x\le e\\ xf(\ln x)&\text{if }x>e\end{cases} Does \displaystyle\sum_{n\equal{}1}^{\infty}\frac1{f(n)} converge?
A3
1
Hide problems
Putnam 2008 A3
Start with a finite sequence
a
1
,
a
2
,
…
,
a
n
a_1,a_2,\dots,a_n
a
1
,
a
2
,
…
,
a
n
of positive integers. If possible, choose two indices
j
<
k
j < k
j
<
k
such that
a
j
a_j
a
j
does not divide
a
k
a_k
a
k
and replace
a
j
a_j
a
j
and
a
k
a_k
a
k
by
gcd
(
a
j
,
a
k
)
\gcd(a_j,a_k)
g
cd
(
a
j
,
a
k
)
and
lcm
(
a
j
,
a
k
)
,
\text{lcm}\,(a_j,a_k),
lcm
(
a
j
,
a
k
)
,
respectively. Prove that if this process is repeated, it must eventually stop and the final sequence does not depend on the choices made. (Note:
gcd
\gcd
g
cd
means greatest common divisor and lcm means least common multiple.)
A2
1
Hide problems
Putnam 2008 A2
Alan and Barbara play a game in which they take turns filling entries of an initially empty
2008
×
2008
2008\times 2008
2008
×
2008
array. Alan plays first. At each turn, a player chooses a real number and places it in a vacant entry. The game ends when all entries are filled. Alan wins if the determinant of the resulting matrix is nonzero; Barbara wins if it is zero. Which player has a winning strategy?
A1
1
Hide problems
Putnam 2008 A1
Let
f
:
R
2
→
R
f: \mathbb{R}^2\to\mathbb{R}
f
:
R
2
→
R
be a function such that f(x,y)\plus{}f(y,z)\plus{}f(z,x)\equal{}0 for real numbers
x
,
y
,
x,y,
x
,
y
,
and
z
.
z.
z
.
Prove that there exists a function
g
:
R
→
R
g: \mathbb{R}\to\mathbb{R}
g
:
R
→
R
such that f(x,y)\equal{}g(x)\minus{}g(y) for all real numbers
x
x
x
and
y
.
y.
y
.