Trzy ciągi okresowe i poszukiwanie sumy

[Morfeo]

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 \(\displaystyle{ ( a_{i} , b_{i} , c_{i} )}\) - są to kolejne wartości potęg jakichś liczb.

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

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

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

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

Przykład:

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

niech \(\displaystyle{ k = 3}\)

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

Jak widać nie trafiliśmy ponieważ \(\displaystyle{ 0 + 2 = 2}\).

niech jednak \(\displaystyle{ k = 5}\)

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

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

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

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

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

a co za tym idzie:

\(\displaystyle{ 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 \(\displaystyle{ ( a_{i} , b_{i} , c_{i} )}\) są budowane z kolejnych potęg liczb, które są względnie pierwsze.