3

Part of 1992 Iran MO (2nd round)

Problems(2)

Cities and the river [Iran Second Round 1992]

Source:

There are some cities in both sides of a river and there are some sailing channels between the cities. Each sailing channel connects exactly one city from a side of the river to a city on the other side. Each city has exactly

k

sailing channels. For every two cities, there's a way which connects them together. Prove that if we remove any (just one) sailing channel, then again for every two cities, there's a way that connect them together.

( k \geq 2)

graph theorycombinatorics proposedcombinatorics

Number of the members of the set is divisible by p [Iran 92]

Source:

X \neq \varnothing

be a finite set and let

f: X \to X

be a function such that for every

x \in X

and a fixed prime

p

f^p(x)=x.

Y=\{x \in X | f(x) \neq x\}.

Prove that the number of the members of the set

Y

is divisible by

p.

{f^p(x)=x = \underbrace{f(f(f(\cdots ((f}_{ p \text{ times}}(x) ) \cdots )))} .

functioninductionnumber theory proposednumber theory