MathDB

f(g(n)) = f(n) + 1 and g(f(n)) = g(n) + 1

Source: IMO Shortlist 2010, Algebra 6

7/17/2011

Suppose that

f

and

g

are two functions defined on the set of positive integers and taking positive integer values. Suppose also that the equations

f(g(n)) = f(n) + 1

and

g(f(n)) = g(n) + 1

hold for all positive integers. Prove that

f(n) = g(n)

for all positive integer

n.

Proposed by Alex Schreiber, Germany

functionalgebrafunctional equationIMO Shortlistpositive integers

There are two strings of pearls

Source: IMO Shortlist 2010, Combinatorics 6

7/17/2011

Given a positive integer

k

and other two integers

b > w > 1.

There are two strings of pearls, a string of

b

black pearls and a string of

w

white pearls. The length of a string is the number of pearls on it. One cuts these strings in some steps by the following rules. In each step:
(i) The strings are ordered by their lengths in a non-increasing order. If there are some strings of equal lengths, then the white ones precede the black ones. Then

k

first ones (if they consist of more than one pearl) are chosen; if there are less than

k

strings longer than 1, then one chooses all of them. (ii) Next, one cuts each chosen string into two parts differing in length by at most one. (For instance, if there are strings of

5, 4, 4, 2

black pearls, strings of

8, 4, 3

white pearls and

k = 4,

then the strings of 8 white, 5 black, 4 white and 4 black pearls are cut into the parts

(4,4), (3,2), (2,2)

and

(2,2)

respectively.) The process stops immediately after the step when a first isolated white pearl appears.
Prove that at this stage, there will still exist a string of at least two black pearls.
Proposed by Bill Sands, Thao Do, Canada

combinatoricsinvariantgameIMO Shortlist

IMO Shortlist 2010 - Problem G6

Source:

7/17/2011

The vertices

X, Y , Z

of an equilateral triangle

XYZ

lie respectively on the sides

BC, CA, AB

of an acute-angled triangle

ABC.

Prove that the incenter of triangle

ABC

lies inside triangle

XYZ.

Proposed by Nikolay Beluhov, Bulgaria

geometryincentercircumcircleinequalitiesIMO Shortlist

IMO Shortlist 2010 - Problem N6

Source:

7/17/2011

The rows and columns of a

2^n \times 2^n

table are numbered from

0

to

2^{n}-1.

The cells of the table have been coloured with the following property being satisfied: for each

0 \leq i,j \leq 2^n - 1,

the

j

-th cell in the

i

-th row and the

(i+j)

-th cell in the

j

-th row have the same colour. (The indices of the cells in a row are considered modulo

2^n

.) Prove that the maximal possible number of colours is

2^n

.
Proposed by Hossein Dabirian, Sepehr Ghazi-nezami, Iran

IMO Shortlistcombinatoricsnumber theorymatrix

6

Problems(4)