Tablica liczb, wymazywanie

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafó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

Tablica liczb, wymazywanie

Post autor: patry93 » 30 lis 2008, o 16:45

Witam.

Na tablicy napisane są liczby 1, 2, 3, 4, ..., 101. Dopuszcza się wymazanie dwóch spośród nich wpisując na ich miejsce ich różnicę. Powtarzając tę operację 100 razy pozostawiamy na tablicy tylko jedną liczbę. Uzasadnić, że ta liczba w żadnym przypadku nie może być równa zero.

Ok, wiem tyle, że wśród tych liczb mam 50 parzystych i 51 nieparzystych, więc suma tych wszystkich liczb na tablicy jest liczbą nieparzystą. Wiadomo też, że suma i różnica pewnych liczb są tej samej parzystości, więc bez straty ogólności mogę zamienić odejmowanie na dodawanie i muszę wykazać, że po 100 operacjach nie otrzymam 0 (czyli ogólnie liczby parzystej).
Problem mam tylko z dowodem....

Z góry dziękuję za pomoc.

Awatar użytkownika
Sylwek
Gość Specjalny
Gość Specjalny
Posty: 2711
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 155 razy
Pomógł: 654 razy

Tablica liczb, wymazywanie

Post autor: Sylwek » 30 lis 2008, o 17:15

Niezmiennikiem operacji zadania jest parzystość sumy liczb na tablicy, bo: \(\displaystyle{ |a-b| \equiv a-b \equiv a+b \ (mod \ 2)}\), na początku suma była nieparzysta, zatem nigdy nie będzie równa 0, co należało dowieść.

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

Tablica liczb, wymazywanie

Post autor: patry93 » 30 lis 2008, o 17:41

Sylwek - dziękuję
Hm... o niezmiennikach nie czytałem, ale chyba kojarzę o co chodzi
Rozumiem, że ten zapis w "języku" kongruencji w zupełności wystarczy aby udowodnić tezę?

Awatar użytkownika
Sylwek
Gość Specjalny
Gość Specjalny
Posty: 2711
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 155 razy
Pomógł: 654 razy

Tablica liczb, wymazywanie

Post autor: Sylwek » 30 lis 2008, o 17:46

Tak, ten zapis pokazuje, że liczba powstała po operacji jest tej samej parzystości co suma liczb wziętych do operacji.

ODPOWIEDZ