1996 USAMO

Part of USAMO

Subcontests

(5)

1

a, b subset

Determine (with proof) whether there is a subset

X

of the integers with the following property: for any integer

n

there is exactly one solution of

a + 2b = n

a,b \in X

1

n-term Sequence

n

(x_1, x_2, \ldots, x_n)

in which each term is either 0 or 1 is called a binary sequence of length

n

a_n

be the number of binary sequences of length

n

containing no three consecutive terms equal to 0, 1, 0 in that order. Let

b_n

be the number of binary sequences of length

n

that contain no four consecutive terms equal to 0, 0, 1, 1 or 1, 1, 0, 0 in that order. Prove that

b_{n+1} = 2a_n

for all positive integers

n

1

Intersections

ABC

be a triangle. Prove that there is a line

\ell

(in the plane of triangle

ABC

) such that the intersection of the interior of triangle

ABC

and the interior of its reflection

A'B'C'

\ell

has area more than

\frac23

the area of triangle

ABC

1

Sum of groups

For any nonempty set

S

of real numbers, let

\sigma(S)

denote the sum of the elements of

S

A

n

positive integers, consider the collection of all distinct sums

\sigma(S)

S

ranges over the nonempty subsets of

A

. Prove that this collection of sums can be partitioned into

n

classes so that in each class, the ratio of the largest sum to the smallest sum does not exceed 2.

1

Trig Sum

Prove that the average of the numbers

n \sin n^{\circ} \; (n = 2,4,6,\ldots,180)

\cot 1^{\circ}