1998 Japan MO Finals

Part of Japan MO Finals

Subcontests

(5)

1

Othello game

12

points around a circle we place a disk with one white side and one black side. We may perform the following move: select a black disk, and reverse its two neighbors. Find all initial configurations from which some sequence of such moves leads to the position where all disks but one are white.

1

Number of permutations

c_{n, m}

be the number of permutations of

\{1, \ldots, n\}

which can be written as the product of

m

transpositions of the form

(i, i+1)

i=1, \ldots, n-1

m-1

suct transpositions. Prove that for all

n \in \mathbb{N}

\sum_{m=0}^\infty c_{n, m}t^{m}= \prod_{i=1}^{n}(1+t+\cdots+t^{i-1}).

1

External angle of closed polygons

P_{1}, \ldots P_{n}

be the sequence of vertices of a closed polygons whose sides may properly intersect each other at points other than the vertices. The external angle at

P_{i}

180^\circ

minus the angle of rotation about

P_{i}

required to bring the ray

P_{i}P_{i-1}

P_{i}P_{i+1}

, taken in the range (

0^\circ, 360^\circ

P_{0}=P_{n}

P_{1}=P_{n+1}

). Prove that if the sum of the external angles is a multiple of

720^\circ

, then the number of self-intersections is odd.

1

Maximum number of direct flights that can be offered

1998

airports connected by some direct flights. For any three airports, some two are not connected by a direct flight. What is the maximum number of direct flights that can be offered?

1

The number that made entry of points

p \geq 3

be a prime, and let

p

A_{0}, \ldots, A_{p-1}

lie on a circle in that order. Above the point

A_{1+\cdots+k-1}

we write the number

k

k=1, \ldots, p

1

is written above

A_{0}

). How many points have at least one number written above them?