LIII OM - III - Zadanie 3

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

Komentarze

Dodaj nową odpowiedź