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.
Tablica liczb, wymazywanie
- Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
Tablica liczb, wymazywanie
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ść.
-
- 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ł: 33 razy
Tablica liczb, wymazywanie
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ę?
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ę?