Päevaülesanne

Juhuslik

Harjutuskomplekt

Balti Tee 1998 · Ülesanne 1

Arvuteooria

Let Z+\mathbb{Z}^{+}be the set of all positive integers. Find all functions f:Z+→Z+f: \mathbb{Z}^{+} \rightarrow \mathbb{Z}^{+} satisfying the following conditions for all x,y∈Z+x, y \in \mathbb{Z}^{+}:

f(x,x)=x,f(x,y)=f(y,x),(x+y)f(x,y)=yf(x,x+y).\begin{aligned} f(x, x) & =x, \\ f(x, y) & =f(y, x), \\ (x+y) f(x, y) & =y f(x, x+y) . \end{aligned}
Muuda valikut

Kui oled valmis

Ülevaatematerjal muutub kättesaadavaks järgmise päevaülesannete komplektiga.

Ülevaade

Teemad

Diofantilised võrrandid

Lahendused

Lahendus

Answer: f(x,y)=lcm⁡(x,y)f(x, y)=\operatorname{lcm}(x, y) is the only such function.

We first show that there is at most one such function ff. Let z⩾2z \geqslant 2 be an integer. Knowing the values f(x,y)f(x, y) for all x,yx, y with 0<x,y<z0<x, y<z, we compute f(x,z)f(x, z) for 0<x<z0<x<z using the third equation (with y=z−xy=z-x ); then from the first two equations we get the values f(z,y)f(z, y) for 0<y⩽z0<y \leqslant z. Hence, if ff exists then it is unique.

Experimenting a little, we can guess that f(x,y)f(x, y) is the least common multiple of xx and yy. It remains to verify that the least-common-multiple function satisfies the given equations. The first two are clear, and for the third one:

(x+y)⋅lcm⁡(x,y)=(x+y)⋅xygcd⁡(x,y)=y⋅x(x+y)gcd⁡(x,x+y)==y⋅lcm⁡(x,x+y).\begin{aligned} (x+y) \cdot \operatorname{lcm}(x, y) & =(x+y) \cdot \frac{x y}{\operatorname{gcd}(x, y)}=y \cdot \frac{x(x+y)}{\operatorname{gcd}(x, x+y)}= \\ & =y \cdot \operatorname{lcm}(x, x+y) . \end{aligned}

Võistluse kontekst

Balti Tee tulemused 1998

11 võistkonda

Keskmine tulemus
3,2 / 5
4 või 5 punkti
6 / 11
Eesti
2 / 5

Punktijaotus

01
11
23
30
42
54
Kõigi võistkondade punktid
VõistkondPunktid
Latvia5 / 5
Estonia2 / 5
Poland5 / 5
Finland5 / 5
St. Petersburg0 / 5
Sweden2 / 5
Denmark2 / 5
Iceland4 / 5
Norway5 / 5
Germany1 / 5
Lithuania4 / 5