2012 Canada National Olympiad

Part of Canada National Olympiad

Subcontests

(5)

1

Moving k-th book to the k-th position

A bookshelf contains

n

volumes, labelled

1

n

, in some order. The librarian wishes to put them in the correct order as follows. The librarian selects a volume that is too far to the right, say the volume with label

k

, takes it out, and inserts it in the

k

-th position. For example, if the bookshelf contains the volumes

1,3,2,4

in that order, the librarian could take out volume

2

and place it in the second position. The books will then be in the correct order

1,2,3,4

.
(a) Show that if this process is repeated, then, however the librarian makes the selections, all the volumes will eventually be in the correct order. (b) What is the largest number of steps that this process can take?

1

Quadrilateral ABCD such that AC+AD=BC+BD

ABCD

be a convex quadrilateral and let

P

be the point of intersection of

AC

BD

AC+AD=BC+BD

. Prove that the internal angle bisectors of

\angle ACB

\angle ADB

\angle APB

meet at a common point.

1

L(n,k) is the lcm of k consecutive integers

For any positive integers

n

k

L(n,k)

be the least common multiple of the

k

consecutive integers

n,n+1,\ldots ,n+k-1

. Show that for any integer

b

, there exist integers

n

k

L(n,k)>bL(n+1,k)

1

Non-homogeneous xyz inequality

x,y

z

be positive real numbers. Show that

x^2+xy^2+xyz^2\ge 4xyz-4

1

robots in the grid

A number of robots are placed on the squares of a finite, rectangular grid of squares. A square can hold any number of robots. Every edge of each square of the grid is classified as either passable or impassable. All edges on the boundary of the grid are impassable. You can give any of the commands up, down, left, or right.
All of the robots then simultaneously try to move in the specified direction. If the edge adjacent to a robot in that direction is passable, the robot moves across the edge and into the next square. Otherwise, the robot remains on its current square. You can then give another command of up, down, left, or right, then another, for as long as you want. Suppose that for any individual robot, and any square on the grid, there is a finite sequence of commands that will move that robot to that square. Prove that you can also give a finite sequence of commands such that all of the robots end up on the same square at the same time.