Mamy danych \(\displaystyle{ n}\) liczb całkowitych dodatnich (na tablicy). Ruch polega na zamianie dwóch różnych liczb na ich NWD oraz NWW. Dowieść, że po skończonej liczbie ruchów liczby nie będą się już zmieniać.
Proszę o sprawdzenie, gdyż nie jestem pewny tego, co mam:
Ukryta treść:
Wiemy, że dla \(\displaystyle{ a < b \ NWD(a, b) = a \Leftrightarrow a | b \ \text{oraz} \ NWW(a, b) = b \Leftrightarrow a | b}\)
zatem jeśli w ruchu wybierzemy dwie liczby takie, że jedna jest dzielnikiem drugiej, to nie zmienimy tych liczb. Weźmy więc liczby \(\displaystyle{ a<b}\), że \(\displaystyle{ a \nmid b}\). Wówczas \(\displaystyle{ NWD(a,b) | NWW(a,b)}\) oraz jeśli dla pewnego \(\displaystyle{ k \ k | a \ \vee \ k | b \Rightarrow k | NWW(a,b)}\), a jeśli \(\displaystyle{ a|k \ \vee \ b|k \Rightarrow NWD(a,b) | k}\).
Więc po takim ruchu zwiększyliśmy liczbę par liczb takich, że jedna dzieli drugą, ale liczba ta musi być skończona, skąd teza.
[Kombinatoryka] - liczby na tablicy, NWD, NWW
: 4 lip 2011, o 15:53
autor: norwimaj
Ja bym trochę poprawił logikę.
patry93 pisze:
jeśli dla pewnego \(\displaystyle{ k \ k | a \ \vee \ k | b \Rightarrow k | NWW(a,b)}\)
Napisałeś "jeśli", ale nigdzie nie napisałeś "to". Taki zapis jest nieczytelny. W tej sytuacji lepiej by było wszystkie spójniki napisać słownie.
Poza tym zamiast \(\displaystyle{ k | a\vee k | b \Rightarrow k | NWW(a,b)}\) powinieneś mieć osobno \(\displaystyle{ k | a \Rightarrow k | NWW(a,b)}\) oraz \(\displaystyle{ k | b \Rightarrow k | NWW(a,b)}\). Inaczej nie widać, że zwiększa się liczba par takich, że jedna liczba dzieli drugą liczbę.
[Kombinatoryka] - liczby na tablicy, NWD, NWW
: 4 lip 2011, o 15:58
autor: Dumel
źle. gdy po lewej stronie implikacji masz dwie podzielności prawdziwe to nie pokazałeś że liczba par się nie zmniejsza.
można tak:
Ukryta treść:
gdy coś zmieniamy to suma rośnie, a ponieważ iloczyn jest stały więc jest ona ograniczona
[Kombinatoryka] - liczby na tablicy, NWD, NWW
: 4 lip 2011, o 16:05
autor: norwimaj
Dumel pisze:źle. gdy po lewej stronie implikacji masz dwie podzielności prawdziwe to nie pokazałeś że liczba par się nie zmniejsza.
Racja. Wydawało mi się że po mojej poprawce jest dobrze, ale jednak nic istotnego nie zmieniłem.-- 4 lip 2011, o 16:07 --Ale i tak da się to poprawić, rozważając osobno przypadki, gdy po lewych stronach implikacji oba warunki są prawdziwe.
[Kombinatoryka] - liczby na tablicy, NWD, NWW
: 4 lip 2011, o 17:54
autor: patry93
Faktycznie... hm, tylko, że nawet po ewentualnej poprawce, tezy nie będzie, gdyż liczba tych par może dosyć "długo" nie zmieniać się i jeszcze nie widzę uzasadnienia, dlaczego miałaby kiedyś wzrosnąć.
A to drugie rozwiązanie, Dumela - super
@norwimaj - super, dzięki
[Kombinatoryka] - liczby na tablicy, NWD, NWW
: 4 lip 2011, o 19:28
autor: norwimaj
Jeśli \(\displaystyle{ k | a}\) i \(\displaystyle{ k | b}\) to nie tylko \(\displaystyle{ k | NWW(a,b)}\) ale też \(\displaystyle{ k | NWD(a,b)}\).
A jeśli zachodzą oba warunki: \(\displaystyle{ a|k}\) i \(\displaystyle{ b|k}\), to \(\displaystyle{ NWD(a,b) | k}\) oraz \(\displaystyle{ NWW(a,b) | k}\).
Dlatego nawet w takich przypadkach liczba tych par wzrasta.
[Kombinatoryka] - liczby na tablicy, NWD, NWW
: 4 lip 2011, o 21:21
autor: Dumel
ok mój błąd. ale nie wzrasta tylko nie maleje, więc do dowodu trochę/sporo brakuje
[Kombinatoryka] - liczby na tablicy, NWD, NWW
: 4 lip 2011, o 22:42
autor: norwimaj
Wzrasta, bo przed zamianą jest \(\displaystyle{ a \nmid b}\) i \(\displaystyle{ b \nmid a}\), a po zamianie \(\displaystyle{ NWD(a,b) | NWW(a,b)}\)