2007 Putnam

Part of Putnam

Subcontests

(6)

2

Putnam 2007 A6

A triangulation

\mathcal{T}

P

is a finite collection of triangles whose union is

P,

and such that the intersection of any two triangles is either empty, or a shared vertex, or a shared side. Moreover, each side of

P

is a side of exactly one triangle in

\mathcal{T}.

\mathcal{T}

is admissible if every internal vertex is shared by

6

or more triangles. For example [asy] size(100); dot(dir(-100)^^dir(230)^^dir(160)^^dir(100)^^dir(50)^^dir(5)^^dir(-55)); draw(dir(-100)--dir(230)--dir(160)--dir(100)--dir(50)--dir(5)--dir(-55)--cycle); pair A = (0,-0.25); dot(A); draw(A--dir(-100)^^A--dir(230)^^A--dir(160)^^A--dir(100)^^A--dir(5)^^A--dir(-55)^^dir(5)--dir(100)); [/asy] Prove that there is an integer

M_n,

depending only on

n,

such that any admissible triangulation of a polygon

P

n

sides has at most

M_n

Putnam 2007 B6

For each positive integer

n,

f(n)

be the number of ways to make

n!

cents using an unordered collection of coins, each worth

k!

k,\ 1\le k\le n.

Prove that for some constant

C,

n,

n^{n^2/2\minus{}Cn}e^{\minus{}n^2/4}\le f(n)\le n^{n^2/2\plus{}Cn}e^{\minus{}n^2/4}.

2

Putnam 2007 A5

Suppose that a finite group has exactly

n

elements of order

p,

p

is a prime. Prove that either n\equal{}0 or

p

divides n\plus{}1.

Putnam 2007 B5

k

be a positive integer. Prove that there exist polynomials P_0(n),P_1(n),\dots,P_{k\minus{}1}(n) (which may depend on

k

) such that for any integer

n,

\left\lfloor\frac{n}{k}\right\rfloor^k\equal{}P_0(n)\plus{}P_1(n)\left\lfloor\frac{n}{k}\right\rfloor\plus{} \cdots\plus{}P_{k\minus{}1}(n)\left\lfloor\frac{n}{k}\right\rfloor^{k\minus{}1}. (

\lfloor a\rfloor

means the largest integer

\le a.

2

Putnam 2007 A4

A repunit is a positive integer whose digits in base

10

are all ones. Find all polynomials

f

with real coefficients such that if

n

is a repunit, then so is

f(n).

Putnam 2007 B4

n

be a positive integer. Find the number of pairs

P,Q

of polynomials with real coefficients such that (P(X))^2\plus{}(Q(X))^2\equal{}X^{2n}\plus{}1 and

\text{deg}P<\text{deg}{Q}.

2

Putnam 2007 A3

k

be a positive integer. Suppose that the integers 1,2,3,\dots,3k \plus{} 1 are written down in random order. What is the probability that at no time during this process, the sum of the integers that have been written up to that time is a positive integer divisible by

3

? Your answer should be in closed form, but may include factorials.

Putnam 2007 B3

Let x_0 \equal{} 1 and for

n\ge0,

let x_{n \plus{} 1} \equal{} 3x_n \plus{} \left\lfloor x_n\sqrt {5}\right\rfloor. In particular, x_1 \equal{} 5,\ x_2 \equal{} 26,\ x_3 \equal{} 136,\ x_4 \equal{} 712. Find a closed-form expression for

x_{2007}.

\lfloor a\rfloor

means the largest integer

\le a.

2

Putnam 2007 A2

Find the least possible area of a convex set in the plane that intersects both branches of the hyperbola xy\equal{}1 and both branches of the hyperbola xy\equal{}\minus{}1. (A set

S

in the plane is called convex if for any two points in

S

the line segment connecting them is contained in

S.

Putnam 2007 B2

f: [0,1]\to\mathbb{R}

has a continuous derivative and that \int_0^1f(x)\,dx\equal{}0. Prove that for every

\alpha\in(0,1),

\left|\int_0^{\alpha}f(x)\,dx\right|\le\frac18\max_{0\le x\le 1}|f'(x)|

2

Putnam 2007 B1

f

be a polynomial with positive integer coefficients. Prove that if

n

is a positive integer, then

f(n)

divides f(f(n)\plus{}1) if and only if n\equal{}1.

Putnam 2007 A1

Find all values of

\alpha

for which the curves y\equal{}\alpha x^2\plus{}\alpha x\plus{}\frac1{24} and x\equal{}\alpha y^2\plus{}\alpha y\plus{}\frac1{24} are tangent to each other.