szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 20 sty 2018, o 09:26 
Użytkownik

Posty: 17
Lokalizacja: Opole
Cześć, staram się udowodnić poprawność poniższego stwierdzenia jednak nie mam pojęcia jak się za nie zabrać:
na stole leży n zapałek. Gracze na przemian zabierają albo 3 albo 5 zapałek. Wygrywa osoba, która zabierze ostatnią.
Udowodnij indukcyjnie, że pierwszy gracz ma strategię wygrywającą wtw gdy początkowa liczba zapałek n dzieli się przez 8 z resztą większą od 2.
Jak rozwiązywać inne tego typu zadania?
Z góry dziękuję za wszelkie wskazówki.
Góra
Mężczyzna Offline
PostNapisane: 20 sty 2018, o 09:52 
Użytkownik

Posty: 15860
Lokalizacja: Bydgoszcz
Zastanów się? Jeżeli to twierdzenie jest prawdziwe i początkowo reszta była 0,1 lub 2, to jak będzie postępował drugi gracz?
A jeżeli reszta jest większa niż 2, to czy jesteś w stanie postawić drugiego gracza w sytuacji przegrywającej?
Góra
Kobieta Offline
PostNapisane: 20 sty 2018, o 10:34 
Użytkownik

Posty: 17
Lokalizacja: Opole
Jasne, rozumiem. Tylko jak to udowodnić za pomocą indukcji matematycznej? Bo to jest jedyna trudność w tym zadaniu.
Góra
Mężczyzna Offline
PostNapisane: 20 sty 2018, o 11:14 
Użytkownik

Posty: 15860
Lokalizacja: Bydgoszcz
Załóż prawdziwość twierdzenia dla liczb postaci 8n+k,\ k=0,1,...,7 i pokaż prawdziwość dla 8(n+1)+k. Musisz sprawdzić prawdziwość dla 0,1,2,\dots,7
Góra
Mężczyzna Offline
PostNapisane: 20 sty 2018, o 12:24 
Użytkownik
Avatar użytkownika

Posty: 13223
Lokalizacja: Wrocław
A tak z czystej ciekawości: jak wygląda strategia wygrywająca pierwszego gracza dla n=6? Jak na moje oko wówczas strategia wygrywająca nie istnieje, ale może źle rozumiem treść zadania.
Przecież:
– jeśli należy wykonywać poprawne ruchy dopóki jest to możliwe, zaś w ostatnim ruchu w grze można też zabrać jedną lub dwie zapałki, to drugi gracz na wybór trzech zapałek przez pierwszego gracza odpowie zabraniem pozostałych trzech, zaś na zabranie pięciu zapałek odpowie zabraniem ostatniej zapałki, co również daje mu wygraną;
– jeśli bezwzględnie należy wykonywać ruchy takie, jak opisane albo żadnych, to wybór trzech zapałek przez pierwszego gracza spowoduje jego przegraną (oponent weźmie trzy pozostałe i wygra), zaś wybór pięciu zapałek przez pierwszego gracza spowoduje swego rodzaju pat.
Więc gdzie tu strategia wygrywająca?
Góra
Mężczyzna Offline
PostNapisane: 20 sty 2018, o 12:56 
Użytkownik

Posty: 15860
Lokalizacja: Bydgoszcz
Ja rozumiem to tak, że wygrywa biorący ostatnią trójkę lub piątkę. Jak się nie da, to ten, co wziął ostatni wygrywa.

Przy tej interpretacji zadanie jest prawdziwe.
Góra
Mężczyzna Offline
PostNapisane: 20 sty 2018, o 13:24 
Użytkownik
Avatar użytkownika

Posty: 13223
Lokalizacja: Wrocław
Jest możliwe.

Wtedy idea jest bardzo prosta: jeśli reszta z dzielenia n przez 8 jest w \left\{ 0,1,2\right\}, to drugi gracz może wygrać, negując ruch pierwszego modulo osiem (tj. na piątkę odpowiadać trójką, a na trójkę piątką), zaś jeśli wspomniana reszta równa jest co najmniej trzy, to w zależności od tego, czy jest mniejsza od 5, czy co najmniej równa 5:
i) jeśli reszta jest równa trzy lub cztery, to pierwszy gracz zaczyna od zabrania trzech zapałek, a potem j.w. neguje ruchy drugiego, w ten sposób zawsze po jego ruchu będzie 8k+3 zabranych zapałek dla pewnego k\in \NN;
ii) jeśli jest reszta równa co najmniej pięć, to pierwszy gracz zaczyna od zabrania pięciu zapałek, a potem j.w. neguje ruchy drugiego, w ten sposób zawsze po jego ruchu będzie 8k+5 zabranych zapałek.

Aczkolwiek przynajmniej ma jakiś sens, przyznam, że o takiej interpretacji nie pomyślałem.
Góra
Kobieta Offline
PostNapisane: 20 sty 2018, o 13:39 
Użytkownik

Posty: 17
Lokalizacja: Opole
Dziękuję za odpowiedzi i przepraszam za błąd w zadaniu. Oczywiście chodzi o to, że gracz, który nie może już wykonać ruchu przegrywa. Pozdrawiam
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Transpozycje dowód  lgamon  1
 Dowód rekurencyjny  karpiuch  0
 Dowód spójnosci grafu.  Mritke  10
 Dowód na prostokąt na płaszczyźnie  Anal_Iza  2
 Dowód wykazać że graf jest Eulerowski  superes  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl