IMO Shortlist 1993 problem N4


Kvaliteta:
  Avg: 0,0
Težina:
  Avg: 7,0
Dodao/la: arhiva
2. travnja 2012.
LaTeX PDF
Let S be the set of all pairs (m,n) of relatively prime positive integers m,n with n even and m < n. For s = (m,n) \in S write n = 2^k \cdot n_o where k, n_0 are positive integers with n_0 odd and define f(s) = (n_0, m + n - n_0). Prove that f is a function from S to S and that for each s = (m,n) \in S, there exists a positive integer t \leq \frac{m+n+1}{4} such that f^t(s) = s, where f^t(s) = \underbrace{ (f \circ f \circ \cdots \circ f) }_{t \text{ times}}(s).

If m+n is a prime number which does not divide 2^k - 1 for k = 1,2, \ldots, m+n-2, prove that the smallest value t which satisfies the above conditions is \left [\frac{m+n+1}{4} \right ] where \left[ x \right] denotes the greatest integer \leq x.
Izvor: Međunarodna matematička olimpijada, shortlist 1993