szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 mar 2016, o 21:31 
Użytkownik

Posty: 33
Lokalizacja: z daleka
Jeżeli zły dział to proszę o przeniesienie - nie byłem pewny gdzie dodać, a matematyka dyskretna najbardziej na miejscu mi się wydaje.

Mamy trzy rosnące ciągi liczbowe ( a_{i} , b_{i} , c_{i} ) - są to kolejne wartości potęg jakichś liczb.

Generujemy na podstawie ciągów a_{i} , b_{i} , c_{i} odpowiednie ciągi n_{i}, m_{i} oraz r_{i} w następujący sposób:

n_{i} = a_{i} \% k \\
 m_{i} = b_{i} \% k \\
 r_{i} = c_{i} \% k

Udowodniono, że ciągi n_{i} , m_{i} oraz r_{i} muszą być okresowe.

Należy udowodnić, że dla dowolnych ciągów wejściowych a_{i} ,  b_{i}  , c_{i} zawsze istnieje takie k, że suma dowolnego elementu z ciągu n_{i} z dowolnym elementem z ciągu m_{i} (całość modulo k) nie da jakiegokolwiek elementu z ciągu r_{i}.

Przykład:

a_{i} = 3, 9, 27, 81, 243, ... \\
 b_{i} = 2, 4, 8, 16, 32, ... \\
 c_{i} = 5, 25, 125, 625, ...

niech k = 3

n_{i} = 0, ... \\
 m_{i} = 2, 1, 2, ... \\
 r_{i} = 2, 1, 2, ...

Jak widać nie trafiliśmy ponieważ 0 + 2 = 2.

niech jednak k = 5

n_{i} = 3, 4, 2, 1, 3, ... \\
 m_{i} = 2, 4, 3, 1, 2, ... \\
 r_{i} = 0, ...

Jak widać znowu nie trafiliśmy (np. (2 + 3) \% 5 = 0).

Wybrałem akurat dość trudny przypadek, bo dla tych ciągów nie znajdziemy sumy dopiero przy k = 1632.

Jeszcze jedno uściślenie. Dobieramy pierwszy wyraz a_{i} ,  b_{i}  , c_{i} tak, że zawsze jest on większy od k (tak aby operacja modulo miała sens). Dla przykładu przy k = 1632, dostaniemy na wejściu następujące ciągi:

a_{i} = 2187, 6561, 19683, ... \\
 b_{i} = 2048, 4096, 8192, ... \\
 c_{i} = 3125, 15625, 78125, ...

a co za tym idzie:

n_{i} = 555, 33, 99, 297, 891, 1041, 1491, 1209, 363, 1089, 3, 9, 27, 81, 243, 729, 555, ... \\
 m_{i} = 416, 832, 32, 64, 128, 256, 512, 1024, 416, ... \\
 r_{i} = 1493, 937, 1421, 577, 1253, 1369, 317, 1585, 1397, 457, 653, 1, 5, 25, 125, 625, 1493, ...

Tutaj już takowa suma nie występuje.

Ciągi wejściowe ( a_{i} ,  b_{i}  , c_{i} ) są budowane z kolejnych potęg liczb, które są względnie pierwsze.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Znalezienie zwartej postaci sumy  SzalonyMjut  3
 sumy wielokrotne  stash  0
 Kwadrat sumy dwumianu Newtona  Amitiel  1
 znaleźć wzór dla sumy  bebece  1
 szansa na trzy te same karty  strefa61  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl