2n + 1 odważników - jednakowa waga
-
- Użytkownik
- Posty: 165
- Rejestracja: 15 wrz 2010, o 09:13
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 28 razy
2n + 1 odważników - jednakowa waga
Mamy \(\displaystyle{ 2n + 1}\) odważników, z których każdy waży całkowitą liczbę gramów. Wiadomo, że każde \(\displaystyle{ 2n}\) odważnków można tak rozłożyć na szalakach wagi, po \(\displaystyle{ n}\) odważników na kazdej, że nastąpi równowaga. Udowodnij, że wszystkie odważniki mają jednakową wagę.
- Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
2n + 1 odważników - jednakowa waga
Zauważmy, że jeżeli oznaczymy wagi danych odważników jako \(\displaystyle{ a_1 , a_2 , ... , a_{2n+1}}\) to z tego, że spełniają one założenie wynika, że założenie spełniają również odważniki o masach \(\displaystyle{ a_1-1 , a_2-1 , ... , a_{2n+1}-1}\), podobnie jak wszystkie odważniki są parzyste, to założenie spełniają również odważniki o masach \(\displaystyle{ \frac{a_1}{2} , \frac{a_2}{2} , ... , \frac{a_{2n+1}}{2}}\).
Załóżmy więc, że istnieje \(\displaystyle{ 2n+1}\) odważników spełniających założenie, których masy nie są parami równe. Jak wcześniej zauważyliśmy, skoro nasze odważniki spełniają założenie, to dzieląc wszystkie masy odważników przez maksymalną potęgę dwójki dzielącą wszystkie odważniki otrzymamy masy odważników, które również spełniają nasze założenie. Teraz zauważmy, że nie mogą istnieć dwie wagi odważników różnej parzystości. Istotnie, załóżmy nie wprost, że taka sytuacja jest możliwa. W takiej sytuacji skoro jest nieparzysta ilość wszystkich odważników może być:
(a) parzysta ilość odważników (\(\displaystyle{ 2k}\)) o parzystych wagach i nieparzysta ilość odważników (\(\displaystyle{ 2l+1}\)) o nieparzystych wagach
(b) nieparzysta ilość odważników (\(\displaystyle{ 2k+1}\)) o parzystych wagach i parzysta ilość odważników \(\displaystyle{ 2l}\)) o nieparzystych wagach
W przypadku (a) odkładamy jeden odważnik parzysty i zostaje nam \(\displaystyle{ 2k-1}\) odważników o parzystych wagach i \(\displaystyle{ 2l+1}\) odważników o nieparzystych wagach, czego nie da się podzielić na dwie grupy o równej sumie wag (parzystości obu stron będą różne). Analogiczną sprzeczność dostajemy w (b) (odkładamy odważnik nieparzysty)
Tak więc otrzymujemy odważniki o wszystkich wagach nieparzystych, jednak tutaj odejmujemy od wagi każdego odważnika \(\displaystyle{ 1}\) i powtarzamy całą procedurę od początku. Jak widać procedurę możemy powtarzać w nieskończoność, jeżeli od pewnego momentu wszystkie wagi danych odważników będą równe \(\displaystyle{ 0}\) a to jest równoważne temu, że na początku ważyły tyle samo, cnd.
Załóżmy więc, że istnieje \(\displaystyle{ 2n+1}\) odważników spełniających założenie, których masy nie są parami równe. Jak wcześniej zauważyliśmy, skoro nasze odważniki spełniają założenie, to dzieląc wszystkie masy odważników przez maksymalną potęgę dwójki dzielącą wszystkie odważniki otrzymamy masy odważników, które również spełniają nasze założenie. Teraz zauważmy, że nie mogą istnieć dwie wagi odważników różnej parzystości. Istotnie, załóżmy nie wprost, że taka sytuacja jest możliwa. W takiej sytuacji skoro jest nieparzysta ilość wszystkich odważników może być:
(a) parzysta ilość odważników (\(\displaystyle{ 2k}\)) o parzystych wagach i nieparzysta ilość odważników (\(\displaystyle{ 2l+1}\)) o nieparzystych wagach
(b) nieparzysta ilość odważników (\(\displaystyle{ 2k+1}\)) o parzystych wagach i parzysta ilość odważników \(\displaystyle{ 2l}\)) o nieparzystych wagach
W przypadku (a) odkładamy jeden odważnik parzysty i zostaje nam \(\displaystyle{ 2k-1}\) odważników o parzystych wagach i \(\displaystyle{ 2l+1}\) odważników o nieparzystych wagach, czego nie da się podzielić na dwie grupy o równej sumie wag (parzystości obu stron będą różne). Analogiczną sprzeczność dostajemy w (b) (odkładamy odważnik nieparzysty)
Tak więc otrzymujemy odważniki o wszystkich wagach nieparzystych, jednak tutaj odejmujemy od wagi każdego odważnika \(\displaystyle{ 1}\) i powtarzamy całą procedurę od początku. Jak widać procedurę możemy powtarzać w nieskończoność, jeżeli od pewnego momentu wszystkie wagi danych odważników będą równe \(\displaystyle{ 0}\) a to jest równoważne temu, że na początku ważyły tyle samo, cnd.