gra w numerki (pierwsze)

[Gość: grzesiek]

(trochę uproszczone zadanie z konkursu programistycznego acm.uva.es/problemset)

Dwie osoby na przemian mówią liczby pierwsze, każda następna musi być większa
od powiedzianej przez przeciwnika, ale nie większa niż jego liczba plus 10.
Rozpoczynający grę może wybrać 1, albo liczbę pierwszą nie większą niż 10.

Czy potrafisz podpowiedzieć graczowi zaczynającemu grę - których liczb
powinien unikać? Czy możesz to uzasadnić korzystając jedynie z listy liczb
pierwszych ograniczonych do 113

(1) 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73
79 83 89 97 101 103 107 109 113

(jedynkę wziąlem w nawias bo matematycy reagują bardzo nerwowo gdy jedynkę
nazywa się liczbą pierwszą).

[Gość: darekw]

A niby dlaczego 1 nie jest liczbą pierwszą?
Bo dzieli się przez 1 przez siebie, a to samo ?

[marchewa4]

Bo wg. definicji liczba pierwsza to taka liczba naturalna, ktora ma dokladnie
dwa (rozne) podzielniki. A 1 ma tylko 1 podzielnik.

Pozdrowienia
M.

[bigda]

Nie bardzo rozumiem zagadkę. Dlaczego miałby którejś unikać?
Bigda

[Gość: grzesiek]

Trochę wyjaśnień:
Widać że zaczynający ma do wyboru 1, 2, 3, 5 i 7. Chodzi o to że zaczęcie od
niektórych z nich prowadzi go do nieuchronnej przegranej. Zakladam oczywiście że
przeciwnik będzie gral dobrze.
Jeszcze jedno - gracze znają dowolnie dużo liczb pierwszych, ta lista jest
ograniczeniem jedynie dla Ciebie. Czyli że w swojej argumentacji możesz
poslugiwać się tylko tym podzbiorem.

[marchewa4]

Gość portalu: grzesiek napisał(a):

> Widać że zaczynający ma do wyboru 1, 2, 3, 5 i 7. Chodzi o to że zaczęcie od
> niektórych z nich prowadzi go do nieuchronnej przegranej.

Wyszlo mi, ze zaczecie od kazdej z nich prowadzi do porazki. Lepiej nie grac.

Pozdrowienia
M.

[Gość: taterki]

Wygrywająca scieżka to 7, 19, 31, 47, 61, 73, 89, 101, 113.
Aby wygrać należy na nią wejść i niezależnie od ruchów przeciwnika nią podążać.
Więc rozpoczynający musi wybrać 7 bo inaczej na "ścieżkę" wejdzie jego przeciwnik.
Ograniczenie liczb pierwszych do 113 chyba nie ma znaczenia...
Pozdrawiam
t.

Ważne uzupelnienie

[Gość: grzesiek]

Zapomnialem napisać, że PRZEGRYWA TEN Z GRACZY, KTÓRY NIE MOŻE JUŻ PODAĆ
NASTĘPNEJ LICZBY PIERWSZEJ.
Bez tego zdania zagadka jest rzeczywiście bez sensu. Przepraszam.

[quentin389]

odpowiedź brzmi: nie wolno na początku wybrać 1,2,3,5, można tylko 7.
Na razie potrafię uzasadnić tylko gdy wiem, że następną po 113 liczbą pierwszą
jest 127. Myślę dalej. ^^

Dowód

[quentin389]

A dowód wygląda tak:

oznaczmy jako W osobę która Wygra (był kiedyś taki program... Czy Wydra Wygra?
@_@), czyli zna prawidłowe ruchy, oraz P osobę która Przegra, czyli nie wie od
czego zacząć.
Oznaczmy n-tą liczbę pierwszą jako p_n, oraz dla porządku p_0 = 1

1) Pokażę jak W może kontrolować rozgrywkę.
Załóżmy, że p_n jest większa niż p_(n-1) + 10.
Wtedy jeśli W powie "p_(n-1)" to wygrywa, bo P nie może już podać liczby.
Będę pokazywał co W ma wybierać od tyłu, czyli przez indukcję, poczynając od
p_(n-1) którą dobrze wybrał.
Załóżmy, że p_k (k < n-1) jest dobrze wybrana przez W.
Poprzednią liczbą którą ma wybrać W jest największa liczba p_m mniejsza od p_k o
więcej niż 10. Wtedy zachodzi następujący fakt:
W wybiera p_m, P wybiera co kolwiek, ale nie może wziąć p_k, potem W wybiera
p_k. Czyli nadal kontroluje rozgrywkę.

2) Zauważam, że w liczbach p mniejszych od 113 istnieje taki ciąg: 83 89 97 101.
Charakteryzuje się on tym, że są tu tylko dwie możliwości rozgrywki:
W: "83"
P: "89"
W: "97"
albo na odwrót:
P: "83"
W: "89"
P: "97"
Wniosek z tego taki - niezależnie od tego gdzie jest ta ostatnia możliwa do
podania liczba pierwsza (oczywiście, jak można sprawdzić jest ona > 113), to są
tylko dwie możliwości wyboru "wstecz" (jak w pkt. 1), albo W mówi 83, albo 89.

3) Dla tych dwu przypadków stosuję algorytm z pkt. 1, i sprawdzam co mi wychodzi
na początku, okazuje się, że to samo.
Podam tu schemat rozgrywki pomiędzy W i P. liczby nie w nawiasach oznaczają
wybór W (on wie co robi) a liczby w nawiasach wszystkie możliwe wybory P.
wariant 1:
(1,2,3,5) 7 (11,13,17) 19 (23,29) 31 (37,41) 47 (53) 61 (67,71) 73 (79,83) 89
wariant 2:
(1,2,3,5) 7 (11,13,17) 19 (23,29) 31 (37,41) 47 (53) 59 (61,67) 71 (73,79) 83

4) Wniosek - na początku trzeba wybrać 7

To by było na tyle.

[quentin389]

> W wybiera p_m, P wybiera co kolwiek

albo nawet cokolwiek

[Gość: grzesiek]

Dowód Quentina389 jest już prawie dobry, w szczególności punkt 1)
czyli objaśnienie na czym polega wygrywający ciąg wyborów. Również
końcowy wniosek, że trzeba unikać wszystkich liczb za wyjątkiem 7 jest
poprawny. Celowo tak kluczę zamiast po prostu powiedzieć, że 7 wygrywa, ponieważ
tego tak naprawdę nie wiadomo. Dla niektórych maksymalnych kroków, różnych
od 10, zawodnik rozpoczynający ZAWSZE PRZEGRYWA! Tak jest np. dla kroków 4
albo 42, ale to już inna historia.

Dalej już jest trochę gorzej, np:

> 2) Zauważam, że w liczbach p mniejszych od 113 istnieje taki ciąg:
> 83 89 97 101.
> Charakteryzuje się on tym, że są tu tylko dwie możliwości rozgrywki:
> W: "83"
> P: "89"
> W: "97"
> albo na odwrót:
> P: "83"
> W: "89"
> P: "97"

a co z możliwością przeskoczenia od 79 od razu do 89?

> Wniosek z tego taki - niezależnie od tego gdzie jest ta ostatnia możliwa do
> podania liczba pierwsza (oczywiście, jak można sprawdzić jest ona > 113), t

ostatnia liczba akurat = 113, bo następna, 127 jest już nieosiągalna. Ale o tym
nie musimy wiedzieć w tym zadaniu.

> wariant 1:
> (1,2,3,5) 7 (11,13,17) 19 (23,29) 31 (37,41) 47 (53) 61 (67,71) 73 (79,83) 89
> wariant 2:
> (1,2,3,5) 7 (11,13,17) 19 (23,29) 31 (37,41) 47 (53) 59 (61,67) 71 (73,79) 83

to który wariant jest wygrywający? bo oba nie mogą.

Proponuję aby diagnozę Quentina na temat tego jak powinna wyglądać rozgrywka
widziana od końca zastosować do budowania gry od początku.
Obiecuję zaskakujące sytuacje (przynajmniej dla mnie tak bylo).

[quentin389]

> Celowo tak kluczę zamiast po prostu powiedzieć, że 7 wygrywa, ponieważ
> tego tak naprawdę nie wiadomo.
Ależ wiadomo, przynajmniej przy założeniu z drugiego twojego postu:
"Zakladam oczywiście że przeciwnik będzie gral dobrze."
Siedem wygrywa, jeśli po siódemce będę brał konkretne liczby, zupełnie jak kółko
i krzyżyk. Pełna gra, razem ze wszystkimi możliwościami kroków przegranego (w
nawiasie) i ruchami wygranego (bez nawiasów) wygląda tak:
(1,2,3,5) 7 (11,13,17) 19 (23,29) 31 (37,41) 47 (53) 61 (67,71) 73 (79,83) 89
(97) 101 (103,107,109) 113 i koniec, dalej jest 127
Przy takiej grze, nie da się osiągnąć liczb 43 i 59
Możesz sprawdzić, że taka konfiguracja jest poprawna.

Wynika z tego, że jeśli zacznę od 7 i wiem jak grać, lub nie zacznę od 7 (np. bo
przeciwnik zaczyna) ale po drodze będę mógł wybrać liczbę nie w nawiasie (błąd
przeciwnika) to jeśli znam to rozwiązanie to wygram.

> Dla niektórych maksymalnych kroków, różnych
> od 10, zawodnik rozpoczynający ZAWSZE PRZEGRYWA! Tak jest np. dla kroków 4
> albo 42, ale to już inna historia.
Możesz wytłumaczyć?
Co to są kroki 4 i 42?


> Dalej już jest trochę gorzej, np:
>
> > 2) Zauważam, że w liczbach p mniejszych od 113 istnieje taki ciąg:
> > 83 89 97 101.
> > Charakteryzuje się on tym, że są tu tylko dwie możliwości rozgrywki:
> > W: "83"
> > P: "89"
> > W: "97"
> > albo na odwrót:
> > P: "83"
> > W: "89"
> > P: "97"

> a co z możliwością przeskoczenia od 79 od razu do 89?
Nieszkodzi, pamiętaj, że to jest ogólny dowód, gdy nie mam pojęcia, co jest po
113 (takie były warunki zadania). Załóżmy więc że idę sobie algorytmem od tyłu.
Jakieśtam liczby są dla mnie (czyli W) dobre. W każdym przedziale liczb
naturalnych długości 10 musi się taka liczba znajdować. W szczególności w
przedziale <83, 93>. Tam są tylko liczby pierwsze 83 i 89. Czyli jedna z nich
jest dobra. W ten sposób moje ogólne rozważania zawężają się do dwóch ciągów wstecz.

> to który wariant jest wygrywający? bo oba nie mogą.
89, ale o tym nie musimy wiedzieć.


> Proponuję aby diagnozę Quentina na temat tego jak powinna wyglądać rozgrywka
> widziana od końca zastosować do budowania gry od początku.
> Obiecuję zaskakujące sytuacje (przynajmniej dla mnie tak bylo).
Ten algorytm działa tylko od tyłu, chociażby dla tego, że nie możesz wziąć ani
43 ani 59, a jak będziesz szedł od początku to się wkopiesz.

^_^

[Gość: grzesiek]

> > Celowo tak kluczę zamiast po prostu powiedzieć, że 7 wygrywa, ponieważ
> > tego tak naprawdę nie wiadomo.
> Ależ wiadomo, przynajmniej przy założeniu z drugiego twojego postu:
> "Zakladam oczywiście że przeciwnik będzie gral dobrze."

Zawodnik wie, ale my, mając listę tylko do 113 tego nie wiemy.

> Możesz wytłumaczyć?
> Co to są kroki 4 i 42?

To są inne maksymalne kroki, które moglyby by być podane w zadaniu zamiast 10.

> Ten algorytm działa tylko od tyłu, chociażby dla tego, że nie możesz wziąć ani
> 43 ani 59, a jak będziesz szedł od początku to się wkopiesz.

Wlaśnie dokladnie o to chodzi! Startując od każdej liczby innej niż 7 się
wkopiesz. Chodzilo mi o to żeby to wkopanie wskazać i objaśnić.

[quentin389]

>
> > Możesz wytłumaczyć?
> > Co to są kroki 4 i 42?
>
> To są inne maksymalne kroki, które moglyby by być podane w zadaniu zamiast 10.

A, oczywiście, mogłem się domyśleć ^^'

> Dla niektórych maksymalnych kroków, różnych
> od 10, zawodnik rozpoczynający ZAWSZE PRZEGRYWA! Tak jest np. dla kroków 4
...
Zawsze przegrywa, tak samo jak przy 10. Nie widzę różnicy.
Przy założeniu, że W ma listę liczb które ma używać (czyli "gra dobrze") dla
czwórki zrobi takie coś:
(1,2,3) 5 (7) 11 (13) 17 (19) 23 koniec
a dla 10 już podałem w poprzednim poście. NIE ma różnicy.
Natomiast jeśli W nie wie jak grać, to może się zdarzyć coś takiego:
(1,2) 3 (5) 7 (11) 13 (17) 19 (23) i P wygrał.
Rzeczywiście w tym przypadku jest pewien wyjątek - 3. Jeśli zacznę od 3 to już
nikt nie ma wyboru, ale dla 42 takiej liczby nie będzie (jeśli W nie wie jak grać)

Albo zadajesz pytanie o to jakie liczby powinienem wybierać przez cały czas
rozgrywki, żeby wygrać.
Albo pytasz o to od czego powinienem zacząć, żeby ciągle mieć szanse wygrać,
mimo tego, że W wie jak grać.

> > Ten algorytm działa tylko od tyłu, chociażby dla tego, że nie możesz wzią
> ć ani
> > 43 ani 59, a jak będziesz szedł od początku to się wkopiesz.
>
> Wlaśnie dokladnie o to chodzi! Startując od każdej liczby innej niż 7 się
> wkopiesz. Chodzilo mi o to żeby to wkopanie wskazać i objaśnić.
To właśnie zrobiłem! Pokazałem dwa ciągi które dają pewną wygraną przeciwnikowi,
niezależnie od tego co jest po 113, pod warunkiem że nie wybiorę na początku
siódemki. W dodatku udowodniłem, dlaczego te dwa ciągi na pewno zwyciężają. Co
tu jest jeszcze do pokazywania?

Nie wybieram 7, potem robie cokolwiek, a on i tak wygrywa. koniec.

O_o