Powiedzmy, że mamy daną funkcję \(\displaystyle{ f(n) = \frac{W(n)}{D}}\), gdzie \(\displaystyle{ W(n)=\sum_{i=0}^{n}a_{i}n^{i},\quad a_{i}\in\mathbb{Z}}\)
Pytanie: Czy dla wszystkich argumentów \(\displaystyle{ n\in\mathbb{N}}\) jest tak, że \(\displaystyle{ f(n)}\) jest liczbą całkowitą ?
Przykłady: \(\displaystyle{ f(n)=\frac{n(n-1)}{2}}\). Jest to oczywiscie wzór na sumę \(\displaystyle{ n}\) kolejnych liczb naturalnych, więc z pewnoscią \(\displaystyle{ \forall_{n\in\mathbb{N}}f(n)\in\mathbb{Z}}\).
\(\displaystyle{ f(n)=\frac{2n^3+3n^2+n}{6}}\). Również dla tej funkcji jest spełniona własność, że dla dowolnego \(\displaystyle{ n\in\mathbb{N},\quad f(n)\in\mathbb{Z}}\).
\(\displaystyle{ f(n)=\frac{-n^{14}-11n+1}{3}}\) już tej własności nie ma.
Zadanie to pochodzi z tegorocznych finałów z mistrzostw świata w programowaniu zespołowym, link do niego ( ... lemSet.pdf , strona 3).
Już pominę to, że w zadaniu są nałożone ograniczenia na wielkość stopnia \(\displaystyle{ W(n)}\), oraz rozmiary współczynników \(\displaystyle{ a_{0},a_{1},...,a_{n},\quad D}\), bo to istotne jedynie dla rozwiązania algorytmicznego. A mi chodzi o rozwiązanie matematyczne. Czy ktoś ma pomysł jak się do teog zabrać ? Może w grę wchodzi jakaś zależnośc między wartością mianownika a licznikiem.
Równoważne postawienie problemu to oczywiście czy dla każdego \(\displaystyle{ n\in\mathbb{N},\quad W(n)\mod D=0}\).
Mi tylko się udało zauważyć, na przykładzie \(\displaystyle{ f(n)=\frac{2n^3+3n^2+n}{6}}\) taką rzecz, że jeśli dla kolejnych \(\displaystyle{ n=1,2,...}\) oblliczymy sobie \(\displaystyle{ 2n^3\mod 6, 3n^2\mod 6, n\mod 6}\), dostaniemy takie trójki:
2 3 1
4 0 2
0 3 3
2 0 4
4 3 5
2 3 1 -powtarzaja się
4 0 2
0 3 3
Okres wynosi \(\displaystyle{ D=6}\), podobnie zauwazyłem, że dla \(\displaystyle{ f(n)=\frac{n(n-1)}{2}}\) okresy bedzie wynosic 2. Również liczby w kolumnach są okresowe, ale pewnie to zupełnie zły trop, jeśli ktoś ma pomysł jak się zabrać do tego zadania to proszę o wskazówki.
