LII OM - I - Zadanie 11

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Układ liczb całkowitych dodatnich $c_1,c_2,\ldots,c_n$ nazwiemy dopuszczalnym, gdy za pomocą wagi szalkowej i dwóch kompletów odważników o ciężarach $c_1,c_2,\ldots,c_n$ można zważyć dowolny przedmiot o ciężarze będącym liczbą naturalną nie przekraczającą $2(c_1 + c_2 +\ldots + c_n)$ . Dla każdej liczby $n$ wyznaczyć maksymalną sumę $n$ liczb tworzących układ dopuszczalny.

Uwaga: Odważniki można kłaść na obie szalki wagi.

Rozwiązanie

Niech $p_1,p_2,\ldots,p_n$ oraz $q_1,q_2,\ldots,q_n$ będą dwoma zestawami odważników o ciężarach odpowiednio $c_1,c_2,\ldots,c_n$ . Wykażemy najpierw, że za pomocą tych dwóch zestawów możemy zważyć co najwyżej $\frac{1}{2}(5^n-1)$ przedmiotów, niezależnie od tego, czy liczby $c_1,c_2,\ldots,c_n$ tworzą układ dopuszczalny, czy nie.

Ustawienie odważników na szalkach wagi nazwiemy optymalnym, jeśli dla każdego $k \in\{1,2,\ldots,n\}$ ciężarki $p_k$ i $q_k$ nie znajdują się na dwóch różnych szalkach wagi.

Aby otrzymać ustawienie optymalne, dwa odważniki $p_k$ i $q_k$ możemy ustawić na szalkach wagi na $5$ sposobów (zob. tabela obok). Zatem liczba wszystkich optymalnych ustawień odważników jest równa $5^n$ . W tej liczbie mieści się jedno ustawienie „puste", w którym na żadną szalkę nie kładziemy odważników. Pozostałe ustawienia można połączyć w pary symetryczne, w których jedno ustawienie powstaje z drugiego przez zamianę zawartości obydwu szalek wagi.

lewa szalka	prawa szalka
0	0
1	0
2	0
0	1
0	2

Tak więc liczba niepustych, istotnie różnych optymalnych ustawień odważników wynosi $\frac{1}{2}(5^n-1)$ , co oznacza, że możemy zważyć co najwyżej $\frac{1}{2}(5^n-1)$ przedmiotów o różnych ciężarach.

Załóżmy, że liczby $c_1,c_2,\ldots,c_n$ tworzą układ dopuszczalny. Wówczas masa najcięższego przedmiotu, jaki można zważyć, wynosi $2(c_1 + c_2 +\ldots + c_n)$ . Ponieważ nie da się zważyć więcej niż $\frac{1}{2}(5^n-1)$ przedmiotów,

$ (1)\qquad 2(c_{1}+c_{2}+\ldots+c_{n})\leq\frac{1}{2}(5^{n}-1). $

Wykażemy teraz, że liczby $c_1 = 1, c_2 = 5, c_3 = 5^2,\ldots ,c_n = 5^{n-1}$ tworzą układ dopuszczalny. Dla tych wartości $c_i$ zachodzi równość

$ (2)\qquad 2(c_{1}+c_{2}+\ldots+c_{n})=\frac{1}{2}(5^{n}-1). $

Należy więc udowodnić, że za pomocą dwóch kompletów odważników o ciężarach $1, 5, 5^2,\ldots,5^{n-1}$ można zważyć każdy przedmiot o ciężarze będącym liczbą naturalną nie przekraczającą $\frac{1}{2}(5^n-1)$ . Dowód tego faktu przeprowadzimy na dwa sposoby.

Sposób I

Indukcja. Dla $n = 1$ mamy dwa odważniki o ciężarze $1$ każdy i za ich pomocą można zważyć przedmiot o ciężarze $1$ lub $2 = \frac{1}{2}(5^1 - 1)$ .

Załóżmy, że dysponujemy dwoma zestawami odważników o ciężarach $1, 5, 5^2 ,\ldots , 5^{n-1}$ i za ich pomocą umiemy zważyć każdy przedmiot o ciężarze nie przekraczającym $\frac{1}{2}(5^n-1)$ . Oto jak zważyć przedmiot $p$ o ciężarze $c$ , gdy:

(a) $c\in \langle \frac{1}{2}(5^n-1)+1 ,5^n-1 \rangle$ .

Korzystając z założenia indukcyjnego ważymy najpierw przedmiot $q$ o ciężarze $5^n-c$ kładąc go na prawą szalkę wagi. Następnie kładziemy dodatkowy ciężarek o masie $5^n$ na prawą szalkę wagi, zdejmujemy przedmiot $q$ i kładziemy przedmiot $p$ na lewą szalkę.

(b) $c\in \langle 5^n+1,\frac{1}{2}(3\cdot 5^n-1)\rangle$ .

Podobnie jak w przypadku (a), ważymy najpierw przedmiot $q$ o ciężarze $c - 5^n$ kładąc go na prawą szalkę wagi. Następnie kładziemy dodatkowy ciężarek o masie $5^n$ na lewą szalkę wagi, zdejmujemy przedmiot $q$ i kładziemy przedmiot $p$ na prawą szalkę.

Ważymy najpierw przedmiot $q$ o ciężarze $2\cdot 5^n - c$ kładąc go na prawą szalkę wagi. Następnie kładziemy dwa ciężarki o masie $5^n$ na prawą szalkę wagi, zdejmujemy przedmiot $q$ , po czym kładziemy przedmiot $p$ na lewą szalkę.

(d) $c\in \langle 2\cdot 5^n+1,\frac{1}{2}(5^{n+1}-1) \rangle$ .

Ważymy najpierw przedmiot $q$ o ciężarze $c - 2\cdot 5^n$ kładąc go na prawą szalkę wagi. Następnie kładziemy dwa ciężarki o masie $5^n$ na lewą szalkę wagi, zdejmujemy przedmiot $q$ , po czym kładziemy przedmiot $p$ na prawą szalkę.

Przedmioty o masach $5^n$ i $2\cdot 5^n$ można zważyć używając jedynie dwóch odważników o masie $5^n$ . Dowód indukcyjny został więc zakończony.

Sposób II

Niech $c$ będzie dowolną liczbą naturalną nie przekraczającą $\frac{1}{2}(5^n-1)$ . Wówczas liczba $c + \frac{1}{2}(5^n-1)$ jest mniejsza od $5^n$ . Liczbę tę można zatem zapisać w systemie piątkowym przy użyciu co najwyżej $n$ cyfr. Innymi słowy

$ c+\frac{1}{2}(5^{n}-1)=\sum_{i=0}^{n-1}a_{i}5^{i},\ \textrm{gdzie} \ a_{i}\in\{0,1,2,3,4\}. $

Ponieważ $\frac{1}{2}(5^{n}-1)=2(1+5+5^{2}+\ldots+5^{n-1})$ , więc

$ c=\sum_{i=0}^{n-1}\varepsilon_{i}5^{i},\ \textrm{gdzie}\ \varepsilon_{i}\in\{-2,-1,0,1,2\}. $

Powyższa równość oznacza, że przedmiot o ciężarze $c$ można zważyć za pomocą dwóch kompletów odważników o ciężarach $1, 5, 5^2, \ldots,5^{n-1}$ , co kończy dowód.

Z równości (1) i (2) wynika, że maksymalna suma zbioru $n$ liczb dopuszczalnych wynosi $\frac{1}{4}(5^n-1)$ .