LIII OM - III - Zadanie 3

Zawody matematyczne:

LIII OM, 2001-2002

Etap:

III

Na tablicy są napisane trzy nieujemne liczby całkowite. Wybieramy z tej trójki dwie liczby $k$ , $m$ i zastępujemy je liczbami $k + m$ i $|k - m|$ , a trzecia liczba pozostaje bez zmiany. Z otrzymaną trójką postępujemy tak samo. Rozstrzygnąć, czy z każdej początkowej trójki liczb całkowitych nieujemnych, kontynuując to postępowanie, można otrzymać trójkę, w której co najmniej dwie liczby są zerami.

Rozwiązanie

Każdą trójkę liczb całkowitych nieujemnych można przedstawić w postaci

$<br /> (1) \qquad (2^pa,2^qb, 2^rc)<br />$

gdzie $p$ , $q$ , $r$ są liczbami całkowitymi nieujemnymi, zaś każda z liczb $a$ , $b$ , $c$ jest nieparzysta lub równa $0$ . Wagą trójki przedstawionej w postaci (1) nazwiemy wielkość $a + b + c$ .

Wykażemy, że z każdej trójki liczb całkowitych nieujemnych o co najmniej dwóch liczbach niezerowych, wykonując operacje opisane w treści zadania, da się uzyskać trójkę o mniejszej wadze. Tym samym udowodnimy, że zawsze można otrzymać trójkę, w której co najmniej dwie liczby są zerami.

Załóżmy więc, że w trójce $(2^pa,2^qb,2^rc)$ co najmniej dwie liczby są różne od $0$ . Bez straty ogólności przyjmijmy, że $b,c \neq 0$ oraz $q \leq r$ .

Wykonując $2(r-q)$ -krotnie operację $(k,l,m) \to (k +l, |k - l|,m)$ przeprowadzamy trójkę $(2^pa,2^qb, 2^rc)$ na trójkę $(2^{p+r-q}a,2^rb,2^rc)$ , którą następnie przekształcamy na $(2^{p+r-q}a,2^r|b - c|,2^r(b + c))$ . Liczby $b$ i $c$ są nieparzyste, więc waga ostatniej trójki nie przekracza

$<br /> a+\frac{1}{2}|b-c|+\frac{1}{2}(b+c)=a+\max(b,c),<br />$

co jest mniejsze od $a + b + c$ , czyli od wagi trójki $(2^pa,2^qb,2^rc)$ .