MathDB

Functions f(x)f(y) = y^a*f(x/2) + x^b*f(y/2)

Source: IMO Shortlist 1994, A4

8/10/2008

Let

\mathbb{R}

denote the set of all real numbers and \mathbb{R}^\plus{} the subset of all positive ones. Let

\alpha

and

\beta

be given elements in

\mathbb{R},

not necessarily distinct. Find all functions f: \mathbb{R}^\plus{} \mapsto \mathbb{R} such that f(x)f(y) \equal{} y^{\alpha} f \left( \frac{x}{2} \right) \plus{} x^{\beta} f \left( \frac{y}{2} \right) \forall x,y \in \mathbb{R}^\plus{}.

functionalgebrafunctional equationIMO Shortlist

Find the number of positive integers

Source: IMO Shortlist 1994, N4

10/22/2005

Define the sequences

a_n, b_n, c_n

as follows. a_0 \equal{} k, b_0 \equal{} 4, c_0 \equal{} 1. If

a_n

is even then a_{n \plus{} 1} \equal{} \frac {a_n}{2}, b_{n \plus{} 1} \equal{} 2b_n, c_{n \plus{} 1} \equal{} c_n. If

a_n

is odd, then a_{n \plus{} 1} \equal{} a_n \minus{} \frac {b_n}{2} \minus{} c_n, b_{n \plus{} 1} \equal{} b_n, c_{n \plus{} 1} \equal{} b_n \plus{} c_n. Find the number of positive integers

k < 1995

such that some a_n \equal{} 0.

number theoryIMO ShortlistSequencerecurrence relation

Cards and algorithm

Source: IMO Shortlist 1994, C4

3/29/2005

There are n \plus{} 1 cells in a row labeled from

0

to

n

and n \plus{} 1 cards labeled from

0

to

n

. The cards are arbitrarily placed in the cells, one per cell. The objective is to get card

i

into cell

i

for each

i

. The allowed move is to find the smallest

h

such that cell

h

has a card with a label

k > h

, pick up that card, slide the cards in cells h \plus{} 1, h \plus{} 2, ... ,

k

one cell to the left and to place card

k

in cell

k

. Show that at most 2^n \minus{} 1 moves are required to get every card into the correct cell and that there is a unique starting position which requires 2^n \minus{} 1 moves. [For example, if n \equal{} 2 and the initial position is 210, then we get 102, then 012, a total of 2 moves.]

algorithminductionvectorcombinatoricsIMO Shortlist

4

Problems(3)