[Kombinatoryka] - liczby na tablicy, NWD, NWW

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.
patry93
Użytkownik
Użytkownik
Posty: 1251
Rejestracja: 30 sty 2007, o 20:22
Płeć: Mężczyzna
Lokalizacja: Koziegłówki/Wrocław
Podziękował: 352 razy
Pomógł: 32 razy

[Kombinatoryka] - liczby na tablicy, NWD, NWW

Post autor: patry93 » 4 lip 2011, o 12:36

Witam.

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ść:    

norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

[Kombinatoryka] - liczby na tablicy, NWD, NWW

Post autor: norwimaj » 4 lip 2011, o 15:53

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ę.

Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[Kombinatoryka] - liczby na tablicy, NWD, NWW

Post autor: Dumel » 4 lip 2011, o 15:58

ź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ść:    

norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

[Kombinatoryka] - liczby na tablicy, NWD, NWW

Post autor: norwimaj » 4 lip 2011, o 16:05

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.

patry93
Użytkownik
Użytkownik
Posty: 1251
Rejestracja: 30 sty 2007, o 20:22
Płeć: Mężczyzna
Lokalizacja: Koziegłówki/Wrocław
Podziękował: 352 razy
Pomógł: 32 razy

[Kombinatoryka] - liczby na tablicy, NWD, NWW

Post autor: patry93 » 4 lip 2011, o 17:54

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.

norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

[Kombinatoryka] - liczby na tablicy, NWD, NWW

Post autor: norwimaj » 4 lip 2011, o 19:28

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.

Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[Kombinatoryka] - liczby na tablicy, NWD, NWW

Post autor: Dumel » 4 lip 2011, o 21:21

ok mój błąd. ale nie wzrasta tylko nie maleje, więc do dowodu trochę/sporo brakuje

norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

[Kombinatoryka] - liczby na tablicy, NWD, NWW

Post autor: norwimaj » 4 lip 2011, o 22:42

Wzrasta, bo przed zamianą jest \(\displaystyle{ a \nmid b}\) i \(\displaystyle{ b \nmid a}\), a po zamianie \(\displaystyle{ NWD(a,b) | NWW(a,b)}\)

ODPOWIEDZ