Parece un problema difícil:
¿Hay entre los primeros $100000001$ Números de Fibonacci uno $0000$ ?
(es de un entrenamiento de competición; el entrenador sugiere utilizar el principio del encasillamiento)
Consideremos los números de Fibonacci $\mod 10000$ . Comienza la secuencia: $F_0=0, 1, 1, \ldots$ y continúa hasta $F_{100000001}$ . Considere el conjunto de $100000001$ pares ordenados $(F_n, F_{n+1})$ . Por el principio de encasillamiento, al menos uno de estos pares ordenados aparece dos veces en la secuencia.
Ahora observa que toda la secuencia de números de Fibonacci $\mod 10000$ están determinados unívocamente por dos valores consecutivos cualesquiera, ya que la secuencia puede construirse tanto hacia delante como hacia atrás. ( $F_n\equiv F_{n+2}-F_{n+1} \mod 10000$ ).
Así, si el par ordenado $(F_n, F_{n+1})$ se produce tanto en $n=m$ et $n=m+t$ para $m,t \in \mathbb{N}$ entonces la secuencia es recurrente ( $F_n \equiv F_{n+t} \mod 10000$ para todos $n$ ).
Por lo tanto, el par ordenado $(F_n=0, F_{n+1}=1)$ también debe producirse en ambos $n=0$ et $n=t$ . Y como $m+t$ está entre los primeros 100000001 números de Fibonacci, entonces $t$ también debe estar entre ellos.
Hay un detalle importante que esto omite; usted muestra que la secuencia es finalmente cíclico, es decir $F_n\equiv F_{n+t}\mod 10000$ para todo lo suficientemente grande $n$ - pero luego usas que se mantiene para $n=1$ . Debe tener en cuenta que el mapa $(a,b)\mapsto (b,a+b)$ (que las transiciones $(F_{n-1},F_n)$ a $(F_n,F_{n+1})$ ) es una biyección (trabajando mod 10000) para concluir que es periódica. De lo contrario, las aplicaciones repetidas de ese mapa podrían entrar en un ciclo, pero uno que no incluya $(0,1)$ . (por ejemplo, como el mapa $f(x)=max(x-1,0)$ actúa - eventualmente cíclico, pero no una biyección)
Esto es un poco irrelevante para lo que usted está buscando, pero estoy seguro de que usted será feliz de saber que para $n = 7500$,
f(n) = 11423965231520587047220488928656904198487186633317560797959030595738263643588305263964321080516991429937628886229555340146644442744473185460778302934743807002248109695741208782411159189994651520930091202035101269350523609417276542209682261168150544790025062794209091503702088574338650460569295592498666443239807989522593072562158640947468656887645879356201301594841872491497556389555817277508349058330498007583814270123329724353233156029127910968370052734811192660492733375394472692191584489489590970254440914222778382439339334175624660291588778456250479185237898309112318829984358216337347549014336517486496643224502773380042071174360597192343056318489287038447004730922073980870072990706067508624038407888471294048912294153491398930715643640170172837379127969101176561450586945715460276780809807889664272818316865711724985646554559305334340318994612185260719042008960311269000122672589731283419608098303367260382379660402261886574952211783683104453334281684425994447306306414660032519055079504313562694958935754118796157632978970220780288168992181699708922971417067735144929461193639081445200786881549331150381216073705417531166786634690469206418611524663013854198045284806720735273715046888704916821855277543026346215355286395854263168251068150374988851620501196943905031285049077628443804052134507022504682483293396215268186620124762379744668092166035314553541731537245946256422861852573006230492322259630342294350827184840607509969289328320360093204783447860955806396350723341261564285649453007949089154165288839814442677339344794691881510389855765582716774490000,
así que hay al menos uno!
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
2 votos
Entonces ignora al entrenador. Sus consejos pueden ser útiles si te quedas atascado después de haber llegado a algún punto del problema, pero no valen para realmente Inicio el problema.
1 votos
Pista: $100000001=1\, 0000^2+1$ . No es casualidad.