logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Teoria liczb, zadanie nr 3954

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

kara1010
postów: 5
2015-12-07 12:40:16

Gramy w grę. wybieramy dwie dodatnie liczby całkowite (np 78, 35)
W jednym ruchu gracz od pary liczb {m,n} przy zał że m>=n, przechodzi do pary {m-kn,n}, gdzie m-kn>=0. Przychodzi gracz następny i taki sam sposób jak wyżej dosstaje kolejną parę liczb. Wygrywa ten który jako pierwszy dostanie {0,coś}.
np:
{78,35}-(1)->{43,35}-(2)->{8,35}-(1)->{8,3}-(2)->{3,5}-(1)->{2,3}-(2)->{1,2{-(1)->{1,0}
(Zastosowano Algorytm Euklidesa)
Kiedy gracz 1 ma strategię wygrywającą i opisać ją.


magda95
postów: 120
2015-12-07 16:24:58

Zakładamy, że k jest największe z możliwych czy gracz wybiera dowolne k, takie, że m-kn>=0?


tumor
postów: 8070
2015-12-07 17:17:07

Przykład, Magdo, odpowiada na Twoje pytanie. Na pewno nie musi być największe z możliwych. Zapewne musi być dodatnie, bo inaczej na pewno żaden z graczy nie ma strategii wygrywającej.

W ostatnim kroku gracz pierwszy robi
$\{kx,x\}\to \{0,x\}$
w przedostatnim kroku gracz drugi nie miał takiej radosnej sytuacji, ale był zmuszony do zostawienia graczowi pierwszemu takiej sytuacji, czyli musiał mieć
$\{kx+x,kx\}$ dla k>1.

Można tak jeszcze parę kroków zrobić, ale na razie nie widzę, jak zapisać ładnie uogólnienie następnych kroków (wstecz), żeby było widać wszystkie możliwości dające I strategię wygrywającą.



magda95
postów: 120
2015-12-07 17:46:18

tumor, racja, źle spojrzałam :(

Napisałam krótki program, który liczy czy zaczynając od pozycji (a,b) mamy strategię wygrywyjącą.

Wnioski:
Gracz I ma strategię wygrywającą jeśli:
$\cdot$ a = b (chyba oczywiste)
$\cdot$ a - dowolne, 1 <= b <= cos_dziwnego

Tu program:
http://ideone.com/JD2qwP

Mniej więcej widać jak to działa i dlatego daje takie a nie inne wyniki, ale nie do końca wiem jak ładnie opisać te "cos_dziwnego"

Wiadomość była modyfikowana 2015-12-07 17:47:46 przez magda95
strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt online: 34 drukuj