MathDB
Problems
Contests
Undergraduate contests
Putnam
1958 November Putnam
1958 November Putnam
Part of
Putnam
Subcontests
(14)
B7
1
Hide problems
Putnam 1958 November B7
Let
a
1
,
a
2
,
…
,
a
n
a_1 ,a_2 ,\ldots, a_n
a
1
,
a
2
,
…
,
a
n
be a permutation of the integers
1
,
2
,
…
,
n
.
1,2,\ldots, n.
1
,
2
,
…
,
n
.
Call
a
i
a_i
a
i
a big integer if
a
i
>
a
j
a_i >a_j
a
i
>
a
j
for all
i
<
j
.
i<j.
i
<
j
.
Find the mean number of big integers over all permutations on the first
n
n
n
postive integers.
B6
1
Hide problems
Putnam 1958 November B6
Let a complete oriented graph on
n
n
n
points be given. Show that the vertices can be enumerated as
v
1
,
v
2
,
…
,
v
n
v_1 , v_2 ,\ldots, v_n
v
1
,
v
2
,
…
,
v
n
such that
v
1
→
v
2
→
⋯
→
v
n
.
v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n.
v
1
→
v
2
→
⋯
→
v
n
.
B5
1
Hide problems
Putnam 1958 November B5
The lengths of successive segments of a broken line are represented by the successive terms of the harmonic progression 1, 1\slash 2, 1\slash 3, \ldots. Each segment makes with the preceding a given angle
θ
.
\theta.
θ
.
What is the distance and what is the direction of the limiting points (if there is one) from the initial point of the first segment?
B4
1
Hide problems
Putnam 1958 November B4
Let
C
C
C
be a real number, and let
f
:
R
→
R
f: \mathbb{R} \rightarrow \mathbb{R}
f
:
R
→
R
be a three times differentiable function such that
lim
x
→
∞
f
(
x
)
=
C
,
lim
x
→
∞
f
′
′
′
(
x
)
=
0.
\lim_{x \to \infty} f(x)=C, \;\; \; \lim_{x \to \infty} f'''(x)=0.
x
→
∞
lim
f
(
x
)
=
C
,
x
→
∞
lim
f
′′′
(
x
)
=
0.
Prove that
lim
x
→
∞
f
′
(
x
)
=
0
and
lim
x
→
∞
f
′
′
(
x
)
=
0.
\lim_{x \to \infty} f'(x) =0 \;\; \text{and} \;\; \lim_{x \to \infty} f''(x)=0.
x
→
∞
lim
f
′
(
x
)
=
0
and
x
→
∞
lim
f
′′
(
x
)
=
0.
B3
1
Hide problems
Putnam 1958 November B3
Show that if a unit square is partitioned into two sets, then the diameter (least upper bound of the distances between pairs of points) of one of the sets is not less than \sqrt{5} \slash 2. Show also that no larger number will do.
B1
1
Hide problems
Putnam 1958 November B1
Given
b
n
=
∑
k
=
0
n
(
n
k
)
−
1
,
n
≥
1
,
b_n = \sum_{k=0}^{n} \binom{n}{k}^{-1}, \;\; n\geq 1,
b
n
=
k
=
0
∑
n
(
k
n
)
−
1
,
n
≥
1
,
prove that
b
n
=
n
+
1
2
n
b
n
−
1
+
1
,
n
≥
2.
b_n = \frac{n+1}{2n} b_{n-1} +1, \;\; n \geq 2.
b
n
=
2
n
n
+
1
b
n
−
1
+
1
,
n
≥
2.
Hence, as a corollary, show
lim
n
→
∞
b
n
=
2.
\lim_{n \to \infty} b_n =2.
n
→
∞
lim
b
n
=
2.
A7
1
Hide problems
Putnam 1958 November A7
Let
a
a
a
and
b
b
b
be relatively prime positive integers,
b
b
b
even. For each positive integer
q
q
q
, let
p
=
p
(
q
)
p=p(q)
p
=
p
(
q
)
be chosen so that
∣
p
q
−
a
b
∣
\left| \frac{p}{q} - \frac{a}{b} \right|
q
p
−
b
a
is a minimum. Prove that
lim
n
→
∞
∑
q
=
1
n
q
∣
p
q
−
a
b
∣
n
=
1
4
.
\lim_{n \to \infty} \sum_{q=1 }^{n} \frac{ q\left| \frac{p}{q} - \frac{a}{b} \right|}{n} = \frac{1}{4}.
n
→
∞
lim
q
=
1
∑
n
n
q
q
p
−
b
a
=
4
1
.
A6
1
Hide problems
Putnam 1958 November A6
Let
a
(
x
)
a(x)
a
(
x
)
and
b
(
x
)
b(x)
b
(
x
)
be continuous functions on
[
0
,
1
]
[0,1]
[
0
,
1
]
and let
0
≤
a
(
x
)
≤
a
<
1
0 \leq a(x) \leq a <1
0
≤
a
(
x
)
≤
a
<
1
on that range. Under what other conditions (if any) is the solution of the equation for
u
,
u,
u
,
u
=
max
0
≤
x
≤
1
b
(
x
)
+
a
(
x
)
u
u= \max_{0 \leq x \leq 1} b(x) +a(x)u
u
=
0
≤
x
≤
1
max
b
(
x
)
+
a
(
x
)
u
given by
u
=
max
0
≤
x
≤
1
b
(
x
)
1
−
a
(
x
)
.
u = \max_{0 \leq x \leq 1} \frac{b(x)}{1-a(x)}.
u
=
0
≤
x
≤
1
max
1
−
a
(
x
)
b
(
x
)
.
A5
1
Hide problems
Putnam 1958 November A5
Show that the number of non-zero integers in the expansion of the
n
n
n
-th order determinant having zeroes in the main diagonal and ones elsewhere is
n
!
(
1
−
1
1
!
+
1
2
!
−
1
3
!
+
⋯
+
(
−
1
)
n
n
!
)
.
n ! \left(1- \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^{n}}{n!} \right) .
n
!
(
1
−
1
!
1
+
2
!
1
−
3
!
1
+
⋯
+
n
!
(
−
1
)
n
)
.
A4
1
Hide problems
Putnam 1958 November A4
In assigning dormitory rooms, a college gives preference to pairs of students in this order:
A
A
,
A
B
,
A
C
,
B
B
,
B
C
,
A
D
,
C
C
,
B
D
,
C
D
,
D
D
AA,\, AB ,\, AC, \, BB , \, BC ,\, AD , \, CC, \, BD, \, CD, \, DD
AA
,
A
B
,
A
C
,
BB
,
BC
,
A
D
,
CC
,
B
D
,
C
D
,
DD
in which
A
A
AA
AA
means two seniors,
A
B
AB
A
B
means a senior and a junior, etc. Determine numerical values to assign to
A
,
B
,
C
A,B,C
A
,
B
,
C
and
D
D
D
so that the set of numbers
A
+
A
,
A
+
B
,
A
+
C
,
B
+
B
,
…
A+A, A+B, A+C, B+B, \ldots
A
+
A
,
A
+
B
,
A
+
C
,
B
+
B
,
…
corresponding to the order above will be in descending order. Find the general solution and the solution in least positive integers.
A3
1
Hide problems
Putnam 1958 November A3
Under the assumption that the following set of relations has a unique solution for
u
(
t
)
,
u(t),
u
(
t
)
,
determine it.
d
u
(
t
)
d
t
=
u
(
t
)
+
∫
0
t
u
(
s
)
d
s
,
u
(
0
)
=
1.
\frac{d u(t) }{dt} = u(t) + \int_{0}^{t} u(s)\, ds, \;\;\; u(0)=1.
d
t
d
u
(
t
)
=
u
(
t
)
+
∫
0
t
u
(
s
)
d
s
,
u
(
0
)
=
1.
A2
1
Hide problems
Putnam 1958 November A2
Let
R
1
=
1
R_1 =1
R
1
=
1
and R_{n+1}= 1+ n\slash R_n for
n
≥
1.
n\geq 1.
n
≥
1.
Show that for
n
≥
1
,
n\geq 1,
n
≥
1
,
n
≤
R
n
≤
n
+
1.
\sqrt{n} \leq R_n \leq \sqrt{n} +1.
n
≤
R
n
≤
n
+
1.
A1
1
Hide problems
Putnam 1958 November A1
Let
f
(
m
,
1
)
=
f
(
1
,
n
)
=
1
f(m,1)=f(1,n)=1
f
(
m
,
1
)
=
f
(
1
,
n
)
=
1
for
m
≥
1
,
n
≥
1
m\geq 1, n\geq 1
m
≥
1
,
n
≥
1
and let
f
(
m
,
n
)
=
f
(
m
−
1
,
n
)
+
f
(
m
,
n
−
1
)
+
f
(
m
−
1
,
n
−
1
)
f(m,n)=f(m-1, n)+ f(m, n-1) +f(m-1 ,n-1)
f
(
m
,
n
)
=
f
(
m
−
1
,
n
)
+
f
(
m
,
n
−
1
)
+
f
(
m
−
1
,
n
−
1
)
for
m
>
1
m>1
m
>
1
and
n
>
1
n>1
n
>
1
. Also let
S
(
n
)
=
∑
a
+
b
=
n
f
(
a
,
b
)
a
≥
1
and
b
≥
1.
S(n)= \sum_{a+b=n} f(a,b) \,\,\;\; a\geq 1 \,\, \text{and} \,\; b\geq 1.
S
(
n
)
=
a
+
b
=
n
∑
f
(
a
,
b
)
a
≥
1
and
b
≥
1.
Prove that
S
(
n
+
2
)
=
S
(
n
)
+
2
S
(
n
+
1
)
for
n
≥
2.
S(n+2) =S(n) +2S(n+1) \,\, \; \text{for} \, \, n \geq 2.
S
(
n
+
2
)
=
S
(
n
)
+
2
S
(
n
+
1
)
for
n
≥
2.
B2
1
Hide problems
Erdös-Ginzburg-Ziv Theorem
Hi everybody! I've an interesting problem! Can you solve it?Prove Erdös-Ginzburg-Ziv Theorem: "Among any
2
n
−
1
2n-1
2
n
−
1
integers, there are some
n
n
n
whose sum is divisible by
n
n
n
."