Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
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.
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ę.
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.
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
Ostatnio zmieniony 4 lip 2011, o 19:54 przez patry93, łącznie zmieniany 1 raz.
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.
