Weźmy \(\displaystyle{ A= \{a_1,a_2,...,\}}\) jako zbiór dodatnich liczb całkowitych.
Zbiór ten posiada określone własności:
a: \(\displaystyle{ nwd\{a_1,a_2,...\}=1 }\)
b: jest zamknięty na dodawanie
Wtedy istnieje \(\displaystyle{ N < \infty}\), takie, że \(\displaystyle{ n \in A }\) dla każdego \(\displaystyle{ n \geq N}\).
Potrzebuję tego dowodu aby móc udowodnić fakt z łańcuchów Markowa, jednak nie wiem jak się za to za bardzo zabrać, trochę nie moja bajka.
Dowód lematu
- Gosda
- Użytkownik
- Posty: 340
- Rejestracja: 29 cze 2019, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Oulu
- Podziękował: 42 razy
- Pomógł: 60 razy
Re: Dowód lematu
To się nazywa problem monet Frobeniusa: mając nominały ze zbioru \(\displaystyle{ A}\), jaka jest największa kwota, której nie da się wypłacić? Na przykład dla \(\displaystyle{ A = \{3, 4, 3+3. 3+4, 4+4, 3+3+3, \ldots\}}\) odpowiedź brzmi \(\displaystyle{ 5}\). Twoje założenie, że zbiór jest zamknięty na dodawanie oznacza po prostu, że każdego nominału można brać dowolną ilość.
Natomiast fakt, który próbujesz udowodnić, to wg wiki kombinatoryczne twierdzenie Schura... (gdybyś chciał podrążyć temat). Explicite rozwiązanie znalazłem w : \(\displaystyle{ N = (a_1 - 1)(a_k - 1)}\), jeśli ciąg \(\displaystyle{ (a_n)}\) jest rosnący i \(\displaystyle{ \operatorname{NWD} (a_1, \ldots, a_k) = 1}\).
Natomiast fakt, który próbujesz udowodnić, to wg wiki kombinatoryczne twierdzenie Schura... (gdybyś chciał podrążyć temat). Explicite rozwiązanie znalazłem w : \(\displaystyle{ N = (a_1 - 1)(a_k - 1)}\), jeśli ciąg \(\displaystyle{ (a_n)}\) jest rosnący i \(\displaystyle{ \operatorname{NWD} (a_1, \ldots, a_k) = 1}\).