Slični zadaci

IMO Shortlist 1993 problem N4

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.$

Slični zadaci

Lista Tekst Dva stupca

Zadaci

IMO Shortlist 1999 problem A4

Prove that the set of positive integers cannot be partitioned into three nonempty subsets such that, for any two integers $x,y$ taken from two different subsets, the number $x^2-xy+y^2$ belongs to the third subset.

IMO Shortlist 2000 problem A4

The function $F$ is defined on the set of nonnegative integers and takes nonnegative integer values satisfying the following conditions: for every $n \geq 0,$

(i) $F(4n) = F(2n) + F(n),$
(ii) $F(4n + 2) = F(4n) + 1,$
(iii) $F(2n + 1) = F(2n) + 1.$

Prove that for each positive integer $m,$ the number of integers $n$ with $0 \leq n < 2^m$ and $F(4n) = F(3n)$ is $F(2^{m + 1}).$

IMO Shortlist 2002 problem A3

Let $P$ be a cubic polynomial given by $P(x)=ax^3+bx^2+cx+d$ , where $a,b,c,d$ are integers and $a\ne0$ . Suppose that $xP(x)=yP(y)$ for infinitely many pairs $x,y$ of integers with $x\ne y$ . Prove that the equation $P(x)=0$ has an integer root.

IMO Shortlist 2004 problem N3

Find all functions $f: \mathbb{N^{*}}\to \mathbb{N^{*}}$ satisfying
$\left(f^{2}\left(m\right)+f\left(n\right)\right) \mid \left(m^{2}+n\right)^{2}$
for any two positive integers $m$ and $n$ .

Remark. The abbreviation $\mathbb{N^{*}}$ stands for the set of all positive integers:
$\mathbb{N^{*}}=\left\{1,2,3,...\right\}$ .
By $f^{2}\left(m\right)$ , we mean $\left(f\left(m\right)\right)^{2}$ (and not $f\left(f\left(m\right)\right)$ ).

IMO Shortlist 2008 problem A4

For an integer $m$ , denote by $t(m)$ the unique number in $\{1, 2, 3\}$ such that $m + t(m)$ is a multiple of $3$ . A function $f: \mathbb{Z}\to\mathbb{Z}$ satisfies $f( - 1) = 0$ , $f(0) = 1$ , $f(1) = - 1$ and $f\left(2^{n} + m\right) = f\left(2^n - t(m)\right) - f(m)$ for all integers $m$ , $n\ge 0$ with $2^n > m$ . Prove that $f(3p)\ge 0$ holds for all integers $p\ge 0$ .

Proposed by Gerhard Woeginger, Austria

IMO Shortlist 2009 problem N3

Let $f$ be a non-constant function from the set of positive integers into the set of positive integer, such that $a-b$ divides $f\!\left(a\right)-f\!\left(b\right)$ for all distinct positive integers $a$ , $b$ . Prove that there exist infinitely many primes $p$ such that $p$ divides $f\!\left(c\right)$ for some positive integer $c$ .

Proposed by Juhan Aru, Estonia